# Tag Info

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 ...
• 162k
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,847

### 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,168

### 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,079
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,511

### 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
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....
• 31k
Accepted

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,372
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,645
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,270

### 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.
• 162k

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

### 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 ...
• 221

### How to calculate sum of binomial coefficients efficiently?

Hint: Use Lucas's theorem. In general, any time a programming contest problem wants you to compute something mod $p$, check for opportunities to reduce everything mod $p$ before doing any further ...
• 162k