106 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 ...
user avatar
  • 141k
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
42 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 ...
user avatar
  • 3,004
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 ...
user avatar
  • 4,371
25 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 ...
user avatar
  • 508
21 votes

Represent a real number without loss of precision

There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's ...
user avatar
21 votes
Accepted

Confused about XORing and addition modulo $2$

The confusion here stems from a missing word. A correct statement is "The result of XORing two bits is the same as that of adding those two bits mod 2." For example, $(0+1)\bmod 2 = 1\bmod 2 = 1=(0\...
user avatar
  • 14.6k
20 votes
Accepted

Represent a real number without loss of precision

It all depends what you want to do. For example, what you show is a great way of representing rational numbers. But it still can't represent something like $\pi$ or $e$ perfectly. In fact, many ...
user avatar
  • 29.1k
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....
user avatar
  • 25.2k
19 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 (...
user avatar
19 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 ...
user avatar
  • 1,615
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
15 votes

Standard constructive definitions of integers, rationals, and reals?

Gilles answer is a good one, except for the paragraph on the real numbers, which is completely false, except for the fact that the real numbers are indeed a different kettle of fish. Because this sort ...
user avatar
  • 28.2k
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 ...
user avatar
12 votes

How can I compute an exponential modulo a large integer?

Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha. When making computations modulo a ...
user avatar
12 votes
Accepted

Standard constructive definitions of integers, rationals, and reals?

There are multiple ways to define a mathematical structure, depending on what properties you consider to be the definition. Between equivalent characterizations, which one you take to be the ...
user avatar
12 votes

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 ...
user avatar
  • 141k
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 ...
user avatar
  • 121
11 votes
Accepted

Minimal basis for set of binary vectors using XOR

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear ...
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
10 votes
Accepted

Proving a language (ir)regular (standard methods have failed)

This can be proven, but you need some nontrivial tools to do it. Start with the set S = {0,3,5,6, ...} of non-negative integers having an even number of 1's in their base-2 expansion. It is well-...
user avatar
10 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 ...
user avatar
  • 201
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 ...
user avatar
  • 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. ...
user avatar
  • 1,121
9 votes

What is most efficient for GCD?

For numbers that are small, the binary GCD algorithm is sufficient. GMP, a well maintained and real-world tested library, will switch to a special half GCD algorithm after passing a special threshold,...
user avatar
  • 543
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 ...
user avatar
  • 3,085
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 ...
user avatar
  • 1,813
8 votes
Accepted

Why addition algorithm is not pseudo- polynomial?

The reason is that the runtime of addition is proportional to the number of digits, not the value of the numbers, as it is for subset sum. Remember that the number of digits is the size of the input.
user avatar
  • 6,519
8 votes
Accepted

Optimal Algorithm for checking if a number is a multiple of three

If an algorithm that takes less than $O(n)$ time, this means that the algorithm won't be able to look at all the digits of the number. Thus you can prove a lower bound of $O(n)$ by showing that you ...
user avatar
  • 6,519

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