Hot answers tagged

47

I assume that the task is to compute $mul(10, a)= 10a$. You don't need to do multiplication. A single binary adder is enough since $$10a = 2^3a + 2a$$ meaning you add one-time left-shifted $a$ to 3-time left-shifted $a$. For general multiplication $mul(x,y)$ please see this article.


42

Short version: it doesn't know. There's no way to tell. If 1111 represents -7, then you have a sign-magnitude representation, where the first bit is the sign and the rest of the bits are the magnitude. In this case, arithmetic is somewhat complicated, since an unsigned add and a signed add use different logic. So you'd probably have a SADD and a UADD opcode,...


18

Here is a concrete encoding that can represent each symbol in less than 1 bit on average: First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111. I've not said what happens if there is ...


16

The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $\tfrac{8}{10}$, and $B$ and $C$ with probability $\tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't ...


14

The short and simple answer is: it doesn't. No modern mainstream CPU ISA works the way you think it does. For the CPU, it's just a bit pattern. It's up to you, the programmer, to keep track of what that bit pattern means. In general, ISAs do not distinguish between different data types, when it comes to storage. (Ignoring special-purpose registers such as ...


13

Let $\mathcal{D}$ be the following distribution over $\{A,B,C\}$: if $X \sim \mathcal{D}$ then $\Pr[X=A] = 4/5$ and $\Pr[X=B]=\Pr[X=C]=1/10$. For each $n$ we can construct prefix codes $C_n\colon \{A,B,C\}^n \to \{0,1\}^*$ such that $$ \lim_{n\to\infty} \frac{\operatorname*{\mathbb{E}}_{X_1,\ldots,X_n \sim \mathcal{D}}[C_n(X_1,\ldots,X_n)]}{n} = H(\mathcal{...


11

Multiplying by 10 is the same as multiplying by $(1010)_2$. To multiply a binary number $x$ by 10, we thus just have to add $x0$ and $x000$. For example, $6 \times 10 = 60$ is implemented by $$ \begin{array}{ccccccc} &0&0&1&1&0&0 \\ +&1&1&0&0&0&0 \\\hline &1&1&1&1&0&0 \end{array} $$ ...


9

One of the great advantages of two’s-complement math, which all modern architectures use, is that the addition and subtraction instructions are exactly the same for both signed and unsigned operands. Many CPUs do not even have multiply, divide or modulus instructions. If they do, they must have separate signed and unsigned forms of the instruction, and the ...


6

Sure. You just compute $1010_\mathrm{b}\times 110_\mathrm{b}$ using the binary version of long multiplication (or some other algorithm). The nice thing about long multiplication in binary is that you never have to carry anything, except when you're adding things up at the end. 1010 110 x ------ 000 110 000 110 -------- 111100 -------- ...


6

Whether this is more efficient depends on the physical properties of the medium, not on any fundamental principle of computer science. And of course there's no reason to limit yourself to ternary systems; we can consider systems with $k$ levels, where $k$ is any integer with $k \ge 2$ (it doesn't have to be limited to $k=2$ or $k=3$). For instance, Wifi ...


6

It doesn't. The processor relies on the instruction set to tell it what type of data it is looking at and where to send it. There's nothing about 1s and 0s in the operand itself that can inherently signal to the ALU whether the data is a char, float, int, signed int, etc. If that 1111 is going to an electric circuit that's expecting a 2s complement, it's ...


4

I would like to propose my revisited version of Hiroki's answer. Currently it's been sitting in peer-review (https://cs.stackexchange.com/review/suggested-edits/66932) for a while, so it's not being of use to anyone. Credits to Hiroki for the original answer and structure. I've simply clarified the math and made every step explicit and chosen a slightly ...


4

Just see it as a perfect binary tree, where you have numbered its nodes from root downwards, level by level. What is the relationship between the number you gave an element x and the number that you gave to its children? Other useful questions: How many nodes are between an element and its children? Why is that? Does it have anything to do with powers of 2, ...


4

Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the linear span of $a_1,\ldots,a_m$. In order to determine whether $X$ is in the linear span of $a_1,\ldots,a_m$, you can use Gaussian elimination.


3

First, if we wouldn't get the same number after negating it twice, it wouldn't make much sense, right? So we just need to prove that the "complement and add 1" has indeed the effect of negation, i.e., taking $x$ into $-x$ (and thus, $-x$ to $x$). (well, maybe except for an edge case I will mention below.) A signed number of $n$ bits, $b_{n-1}, \ldots, b_1,...


3

If we look at the numbers in an unsigned way, flipping a binary number $x$ on $n+1$ bits is computing $(2^{n+1} -1) - x = M - x$. Proof for that: $x = \sum_0^n b_i2^i$. $x$ flipped : $\sum_0^n (1-b_i)2^i = \sum_0^n 2^i -\sum_0^n b_i2^i = (2^{n+1} - 1) - x$ Therefore, flip and add one : $y = (M - x) + 1$ Again : $z = (M - y) +1 = (M - ((M - x) + 1)) + 1$ $...


3

You say in the comments that we might have $c \approx 15$ or so. There should be very efficient algorithms in this case, using locality sensitive hashing. For example, here is a simple LSH. Randomly choose a set of about 10,000 indices (out of the 1,000,000). Hash each vector by computing some standard hash of the 10,000 bits in those positions (ignoring ...


3

Let's assume that each tier of the heap is an array. T1 [ 0 ] T2 [ 1, 2 ] T3 [ 3, 4, 5, 6 ] T4 [7, 8, 9, 10, 11, 12, 13, 14] It may not be clear, but I want you to imagine that $0$ is the parent of $1$ and $2$. Likewise, $1$ is the parent of $3$ and $4$. For example, the second tier's length ...


3

I'd like to give an addition to the answers already made: In most other answers it is noted that in twos-complement arithmetic the result is the same for signed and unsigned numbers: -2 + 1 = -1 1110 + 0001 = 1111 14 + 1 = 15 1110 + 0001 = 1111 However, there are exceptions: Division: -2 / 2 = -1 1110 / 0010 = 1111 14 / 2 = 7 1110 / ...


3

Yuval describes the general approach. Let the binary representation of the two numbers be $n_1,\dots,n_k$ and $m_1,\dots,m_k$, where $n_1$ is the most significant bit. Introduce fresh new boolean variables $t_1,\dots,t_k$. The intention is that these will indicate the common prefix of $n,m$. In particular, add the following clauses: $t_{i+1} \implies ...


2

Let us consider first the case in which node indices are 1-based (start at 1). The nodes in a heap are arranged so that node $1x_1x_2\ldots x_\ell$ (given in binary) is reached by starting at the root and then: If $x_1 = 0$, choose the left child; if $x_1 = 1$, choose the right child. If $x_2 = 0$, choose the left child; if $x_2 = 1$, choose the right child....


2

Suppose you didn't include that shift of $127$, i.e. your number $\nu$ would have the form $\nu = (-1)^S \cdot M \cdot 2^x$ with $x$ being the exponent. With $8$ bits for the exponent $x$ can have a value from $0$ to $255$. This means you can represent numbers from $\nu = (-1)^S \cdot M \cdot 2^0$ to $\nu = (-1)^S \cdot M \cdot 2^{255}$ . However, what if ...


2

In modern computers, assemblers do not deal directly with in-RAM machine code anymore. Their job is to translate the textual representation of the assembly language to opcode combinations, in a form that is not completely finished because exact addresses are not decided yet. Both the tetx and its translation are stored in disk files, they only reside in RAM ...


2

If you want to look for an exact match, use a hashtable. Choose a hash function that hashes a 10,000-bit string to a short hashcode. This approach will be simple and highly efficient: the running time will basically be the time to compute the hash of the 10,000-bit value that you are searching for.


2

Vector here is essentially the same as string, sequence, or array, with the possible connotation of having fixed length. Here is another way to express the same idea: Computer hardware operates on bits. Therefore we have to encode all data in bits before a computer can process it.


2

Contrary to what you think, extracing bytes by shifting and masking is completely unrelated to the storage order (both little-endian and big-endian storage schemes exist and don't influence the results). An int variable is represented by 32 bits. The least significant byte is made of the eight least significant bits and you obtain them by i & 0xFF 0b ...


2

This might not be a formal answer but give you a idea what happens when you do 2's complement. Take any binary number and do the following: Traverse binary bits from right to left Find the first 1 bit Reverse every bit after first 1 Source for shortcut method This is shortcut method to get 2's complement of a number Example: Binary number= 01000100 2's ...


2

The other answers have given rigorous mathematical answers, so I'll try to give a more intuitive way to understand 2's complement. I'll use 4-bit numbers like the original example. First principle: for a 4-bit number n, 1111 - n is the same as flipping the bits of n. If you try a few examples, hopefully this is obvious. Second principle: since we ignore ...


2

Let $a_{N-1} \cdots a_0$ be the two's complement representation of the number $a$. The more general formula is: $$a = -a_{N-1}2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i$$ (I am sure you can figure out how your formulas can be derived from this one.) Why does this hold? For $a \ge 0$, $a_{N - 1} = 0$ and then the value of $a$ is simply the value of the binary ...


2

Yes, that is correct. Your mantissa has only three magnitude bits, so you can only represent numbers from -8 to 7, multiplied of course by any power of 2 from $2^{-8}$ to $2^7$. 11 is impossible to represent, because any positive exponent gets you multiples of 2, any negative exponent gets you numbers less or equal to $7*2^{-1}=3.5$, and exponent 0 is just ...


Only top voted, non community-wiki answers of a minimum length are eligible