Hot answers tagged

48 votes
Accepted

How can I multiply a binary representation by ten using logic gates?

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-...
user avatar
  • 9,612
45 votes

Signed and unsigned numbers

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 ...
user avatar
  • 6,940
18 votes

Shannon Entropy of 0.922, 3 Distinct Values

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). ...
user avatar
17 votes
Accepted

Signed and unsigned numbers

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 ...
user avatar
16 votes
Accepted

Shannon Entropy of 0.922, 3 Distinct Values

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 ...
user avatar
13 votes

Shannon Entropy of 0.922, 3 Distinct Values

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,...
user avatar
11 votes

How can I multiply a binary representation by ten using logic gates?

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{...
user avatar
11 votes

Why the 127 encodings of ASCII needed to be extended to 256?

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 ...
user avatar
  • 25.2k
10 votes

Signed and unsigned numbers

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. ...
user avatar
  • 1,121
9 votes

Why does the formula 2n + 1 find the child node in a binary heap?

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 ...
user avatar
  • 91
7 votes

Why does the formula 2n + 1 find the child node in a binary heap?

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 ...
user avatar
7 votes

Signed and unsigned numbers

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 ...
user avatar
6 votes
Accepted

Could a standardized ternary system be more efficient than the binary system?

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 ...
user avatar
  • 141k
6 votes

How can I multiply a binary representation by ten using logic gates?

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 ...
user avatar
6 votes

Why the 127 encodings of ASCII needed to be extended to 256?

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, ...
user avatar
  • 1,035
6 votes
Accepted

Why does the BOM consist of two bytes instead of one for example in encoding utf-16

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 ...
user avatar
5 votes

Why does the formula 2n + 1 find the child node in a binary heap?

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 ...
user avatar
  • 1,914
5 votes
Accepted

How do computers *really* work? (at the most basic level)

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 ...
user avatar
  • 10.8k
4 votes

Why does the formula 2n + 1 find the child node in a binary heap?

Let's assume that each tier of the heap is an array. ...
user avatar
  • 141
4 votes
Accepted

Two's complement general formula

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 ...
user avatar
  • 4,899
4 votes
Accepted

Binary 2s Compliment Applied Twice Gives Original - How?

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.,...
user avatar
  • 20.4k
4 votes
Accepted

Why does little endian apply to numbers and not to text strings?

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 ...
user avatar
  • 809
4 votes

Is is possible to determine if a given number is xor combination of some numbers?

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 ...
user avatar
4 votes

How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?

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(\...
user avatar
  • 1,319
4 votes

What are some uses of the Thue-Morse sequence in computer science?

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 ...
user avatar
  • 428
4 votes

Why the 127 encodings of ASCII needed to be extended to 256?

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 ...
user avatar
  • 108
3 votes

Binary 2s Compliment Applied Twice Gives Original - How?

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: ...
user avatar
3 votes

Binary 2s Compliment Applied Twice Gives Original - How?

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)...
user avatar
  • 620
3 votes
Accepted

Computing Hamming Distance Between Binary Vectors

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 ...
user avatar
  • 141k
3 votes

Signed and unsigned numbers

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: ...
user avatar

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