Skip to main content
Share Your Experience: Take the 2024 Developer Survey
110 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.'s user avatar
  • 161k
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 ...
AProgrammer's user avatar
  • 3,069
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 ...
Paul92's user avatar
  • 528
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 ...
James Hollis's user avatar
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 ...
user72735's user avatar
  • 121
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 ...
pjc50's user avatar
  • 411
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 ...
Cort Ammon's user avatar
  • 3,351
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,...
gnasher729's user avatar
  • 30.4k
6 votes

Why is addition as fast as bit-wise operations in modern processors?

Let me correct a few things that were not mentioned that explicitely in your existing answers: I know that bitwise operations are so fast on modern processors, because they can operate on 32 or 64 ...
AnoE's user avatar
  • 1,273
6 votes

Connection between NAND gates and Turing completeness

You are in fact correct. A combinational logic circuit is equivalent to a finite automaton. NAND gates do not make them more powerful; they are used because it is simply cheaper to build a digital ...
user628544's user avatar
4 votes

Is it possible to determine if C=A+B faster than adding A+B in logical circuits

Consider computing $\overline{a_{n-1}\ldots a_0}+\overline{b_{n-1}\ldots b_0}=\overline{c_{n-1}\ldots c_0}$. If the last $(k+1)$-bits are correctly computed, then $c_{k+1}$ is correct if and only if $$...
Wei Zhan's user avatar
  • 1,183
4 votes
Accepted

Algorithms for logical synthesis of multiple output bits?

as you realize, while universal, Quine-Mcclusky is only a "bitwise" construction method (single bit output) that does not recognize/ exploit common subpatterns for multibit outputs. multibit function ...
vzn's user avatar
  • 11k
4 votes
Accepted

Algorithm for simplifying ANF or polynomials?

The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF ...
D.W.'s user avatar
  • 161k
4 votes

Trick/insight to I implement given boolean function with minimum numbers of given gate

There is no trick. There is no efficient method. The circuit minimization problem is NP-hard (in fact $\Sigma_2^P$-hard), and I suspect that finding the smallest circuit with only NAND gates is NP-...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Proof of universality in the circuit model

I'm sure you are aware of the following problem: Turing-Machines can't compute any Boolean function. E.g. there is no such TM that prints $0$ if the input TM does not halt and $1$ if it halts (halting ...
plshelp's user avatar
  • 1,629
3 votes

What is Control ROM and Decision ROM?

This terminology is some 30 or more years old coming from the times when Read-only memory (ROM) was a way to implement functions as a cheaper alternative than a general purpose processor. In 1980s ...
Dima Chubarov's user avatar
3 votes
Accepted

Using analog values with Algebraic Normal Form?

Perhaps the most appropriate way of thinking of algebraic normal form is as the following statement: Every function from $\mathbb{Z}_2^n$ to $\mathbb{Z}_2$ can be represented uniquely as a ...
Yuval Filmus's user avatar
3 votes

Is there a canonical form that uses AND and XOR?

Yes. You want algebraic normal form. Every formula in algebraic normal form has the form of an xor of products. Because xor is the same as addition when working modulo 2 (i.e., when working in the ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Is there a canonical form that uses AND and XOR?

You're looking for Reed-Müller forms. The introduction to this paper summarizes some families of these forms: An arbitrary n-variable function $f(x_1,x_2,...,x_n)$ can be represented using the ...
Jason Baker's user avatar
3 votes
Accepted

Physical significance of Don't cares in Digital Logic design

Yes they do have physical significance.Input combinations for which value of a function ( or a device) is not specified are called don't care conditions. They are met when the number of inputs are ...
Akash Mahapatra's user avatar
2 votes

Difference between cordic algorithm and table based methods for elementary functions computation

CORDIC uses small table to work, it calculates one bit at the time and being shift and add algorithm it is preferable when there are no multipliers available. Whenever multipliers are present, table ...
Evil's user avatar
  • 9,465
2 votes

D - Latch or D Flip Flop?

This feels like a homework question, but I'll at least try to point you in the right direction. The difference between a latch and a flip-flop is that a flip-flop is clocked. At first glance, I ...
Devsman's user avatar
  • 121
2 votes

Can bar codes theoretically be considered a type of digital memory?

There is no god-given definition of (read-only) digital memory. We can think of several reasons for a writing system to be considered digital: Can be read by a computer. Cannot be read by a human. ...
Yuval Filmus's user avatar
2 votes

Is it possible to determine if C=A+B faster than adding A+B in logical circuits

In theory, there are other ways to check the result without re-generating it, using modular arithmetic. In practice, these methods probably won't be useful at all, but I'll outline what I'm talking ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Size of constant depth circuit for digital comparator?

Comparison can be implemented by subtracting twos-complement numbers and then testing whether the most significant bit is 0 or 1. Subtraction can be implemented as addition ($x-y = x + \overline{y} + ...
D.W.'s user avatar
  • 161k
2 votes

What is the behavior of the given counter?

ANS: MOD8 COUNTER It still is a mod 8 counter only. But the point where anyone can get confused is the clock speed and the nand gate delay. Basically as soon as we get 111 as the answer. the nand ...
Anonymous Developer's user avatar
2 votes

Number of literals in the given boolean expression

Does your material use the (strange) convention of notating $\neg A$ as $A'$? If so, there are 6 literals (5 without the LHS). If $A'$ is distinct from $A$, there are 9 (8 without LHS) and the ...
orlp's user avatar
  • 13.6k
2 votes
Accepted

Efficient method for generating the smoothing function

Suppose that we are substituting variable $x$. You will have a lot of zeroes and ones in the circuit, so a simple simplification function should help a lot. Additionally a potentially large part of ...
orlp's user avatar
  • 13.6k
2 votes
Accepted

Prime Implicants in Boolean Function

Hints Here are two independent hints. Try an easier case such as exercise 1 or exercise 2 below. Can you find one implicant? Can you expand that implicant to a prime implicant? Can you find more? ...
John L.'s user avatar
  • 39k

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