112
votes
Accepted
Why is addition as fast as bit-wise operations in modern processors?
Addition is fast because CPU designers have put in the circuitry needed to make it fast. It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers ...
D.W.♦
- 166k
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-...
- 9,885
46
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 ...
- 7,176
43
votes
Why is addition as fast as bit-wise operations in modern processors?
There are several aspects.
The relative cost of a bitwise operation and an addition. A naive adder will have a gate-depth which depend linearly of the width of the word. There are alternative ...
- 3,109
30
votes
Accepted
Computing exam averages in less than linear time
To compute the exact mean (no confidence interval or estimate) of each exam, you must at least observe every student's exam score. This takes $\Omega(r)$ per exam. There are $c$ exams you must do this ...
- 4,523
26
votes
Why is addition as fast as bit-wise operations in modern processors?
CPUs operate in cycles. At each cycle, something happens. Usually, an instruction takes more cycles to execute, but multiple instructions are executed at the same time, in different states.
For ...
- 528
21
votes
Accepted
Time complexity of addition
If your algorithm uses asymptotically less than $n$ time, then it does not have enough time to read all the digits of the numbers it is adding. You are to imagine you are handling very large numbers (...
- 4,447
20
votes
Accepted
Inequality caused by float inaccuracy
In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number....
- 31.6k
20
votes
Accepted
How does 0 have two values in one's complement?
In 1's complement you just invert all the bits.
Consider these 2 examples (assuming 8 bits):
$4 = 00000100$, so $-4= 11111011$
$0 = 00000000$, so $-0=11111111$.
So you have 2 ways to represent ...
- 1,655
18
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 ...
- 6,298
14
votes
Usefulness of binary extension field GF(2^n)
$GF(2^n)$ is used in error correcting codes, in some elements of cryptography (e.g., message authentication with 2-universal hashing), and in the AES block cipher, which is very widely used.
D.W.♦
- 166k
13
votes
The math behind converting from any base to any base without going through base 10?
This is a refactoring (Python 3) of Andrej's code. While in Andrej's code numbers are represented through a list of digits (scalars), in the following code numbers are represented through a list of ...
- 231
13
votes
Why is addition as fast as bit-wise operations in modern processors?
Processors are clocked, so even if some instructions can clearly be done faster than others, they may well take the same number of cycles.
You'll probably find that the circuitry required to ...
- 296
12
votes
Why is addition as fast as bit-wise operations in modern processors?
Addition is important enough to not have it wait for a carry bit to ripple through a 64-bit accumulator: the term for that is a carry-lookahead adder and they are basically part of 8-bit CPUs (and ...
- 121
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{...
- 279k
10
votes
Why is addition as fast as bit-wise operations in modern processors?
I think you'd be hard pressed to find a processor that had addition taking more cycles than a bitwise operation. Partly because most processors must carry out at least one addition per instruction ...
- 411
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.
...
- 1,241
9
votes
Accepted
Complexity of Integer Division
Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The ...
- 279k
9
votes
Why is addition as fast as bit-wise operations in modern processors?
At the gate level, you are correct that it takes more work to do addition, and thus takes longer. However, that cost is sufficiently trivial that doesn't matter.
Modern processors are clocked. You ...
- 3,369
9
votes
Accepted
Arithmetic network to compute floor of binary logarithm
It can be done with a fairly simple log-depth circuit without resorting to such hacks that only really make sense in software.
The "position of most significant set bit" function ...
- 2,103
8
votes
Why is addition as fast as bit-wise operations in modern processors?
Modern processors are clocked: Every operation takes some integral number of clock cycles. The designers of the processor determine the length of a clock cycle. There are two considerations there: One,...
- 31.6k
8
votes
Accepted
Number of FLOPs (floating point operations) for exponentiation
Assuming multiplication between two numbers use one FLOP, the number of operations for $x^n$ will be $n-1$. However, is there a faster way to do this ...
There most certainly is a faster way to do ...
- 225
8
votes
DFA that accepts strings whose 10th symbol from the right end is 1
It is easy to prove that you need at least $2^{10}$ states. Suppose you need fewer states. Then after feeding $2^{10}$ different sequences of length ten, there exist two sequences ending in the same ...
- 1,000
7
votes
Time complexity of addition
In order for complexity analysis to make any formal sense at all, you have to specify a formal computational model within which the algorithm in object is being executed, or, at the very least, a cost ...
- 4,272
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 ...
- 171
7
votes
Is squaring easier than multiplication?
Observe that $ab=\frac{1}{2}\left((a+b)^2-a^2-b^2\right)$,
hence multiplication requires three squaring operations and 3 additions/subtractions (division by 2 is easy), which means squaring is ...
- 13.6k
6
votes
Is there any practical trick to mentally count in Gray code?
I have a solution that I just found looking at the patterns, and I checked the pattern up to decimal 31 or binary 11111 or Gray 10000, and it worked quite fine, and I am confident enough the answer ...
6
votes
Accepted
6
votes
Converting Polynomials into Binary form
The polynomial notation is a shortcut to write binary code while omitting the zeros, it's useful to crunch CRC communication checksum to verify electric signal quality with an XOR comparison operation....
- 61
6
votes
Accepted
Subset of numbers whose XOR has least Hamming weight
Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, ...
- 279k
Only top scored, non community-wiki answers of a minimum length are eligible