# Tag Info

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.

44

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

16

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} $$... 11 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 ... 10 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 ... 9 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 ... 7 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.... 7 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 ... 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 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 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 ... 6 The BOM started out as an encoding trick. It was not part of Unicode, it was something that people discovered and cleverly (ab)used. Basically, they found the U+FEFF Zero width non-breaking space character. Now, what does a space character that has a width of zero and does not induce a linebreak do at the very beginning of a document? Well, absolutely ... 5 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, ... 5 This is a complex matter. To begin with, when you move your mouse, there is so much going on at once, that I cannot even begin to explain everything here. So, I will focus on the most fundamental thing: How does the computer actually compute? As you are probably familiar with, computers have memory called RAM, and a CPU that is able to execute "commands&... 4 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 ... 4 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,... 4 The premise is wrong. Unicode encodings include UTF-16BE, UTF-16LE, UTF-32BE and UTF32-LE. Only UTF-8 has no Litte-Endian or Big-Endian variants. Fundamentally, Endian-ness is about the byte order of multi-byte words, and you're thinking of text encodings which use a single byte per character (i.e. ASCII). There's no order to a single byte. 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%... 4 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 ... 4 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 ... 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 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 ...

3

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

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

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

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