Hot answers tagged

48

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} $$ ...


10

ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters. Nowadays people mostly ...


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 ...


5

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 ...


5

There are a few other good reasons to expand from 7-bit ASCII, but since you ask specifically about foreign languages, I want to tell you about that angle. English has words with diacritical marks, usually loan words like naïve or café. They are rare, and usually you'll get into no trouble for omitting the diacritics. Occasionally one might stumble into a ...


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.


4

Primality testing is very fast with the Miller–Rabin algorithm [1]. You can use the deterministic variant with witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 to test any 64 bit number in $O(\log^3 n)$ time. This should take less than one second with any reasonable implementation. [1] https://en.wikipedia.org/wiki/Miller%E2%80%...


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 ...


3

I don't know if this counts as an application but at least it shows up. When using a polynomial rolling hash, it's tempting to do it modulo $2^{32}$ or $2^{64}$ (depending on the word size of the computer) since on most modern architectures addition and multiplication of integers just handle overflows this way, saving time. This method will fail often on ...


3

The problem of computing $t_N$ given $N$ is famous in theoretical computer science as the PARITY problem and is a well-known example of a decision language that can be recognized by linear-size $O(\log n)$-depth circuits but cannot be recognized by polynomial-size circuits of constant depth; here $n$ is the length of the binary expansion of $N$. Parity ...


3

The question of how foreign languages justifies expanding the encoding in actual usage is well explained by earlier answers. The question of why foreign languages would affect the American Standard Code for Information Interchange is subtly different. As you all know the ASCII chart needed to be extended from 127 encoding to 256 No. The original American ...


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.


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