104

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 have judged it to be worth it. See https://en.wikipedia.org/wiki/Adder_(electronics). Both can be made fast enough to execute within a single CPU cycle. They'...


38

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 approaches, more costly in terms of gates, which reduce the depth (IIRC the depth then depend logarithmically of the width of the word). Others have given ...


24

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 example, a simple processor might have 3 steps for each instruction: fetch, execute and store. At any time, 3 instructions are being processed: one is being fetched, ...


12

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 transport data between registers and execution units is significantly more complicated than the adders. Note that the simple MOV (register to register) instruction ...


12

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 their ALUs) and upwards. Indeed, modern processors tend to need not much more execution time for a full multiplication either: carry-lookahead is actually a ...


9

There is indeed little connection. For a thorough understanding, let me explain the connection between programs and circuits. A program (or algorithm, or machine) is a mechanism for computing a function. For definiteness, let us assume that the input is a binary string $x$, and the output is a Boolean output $b$. The size of the input is potentially ...


9

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 cycle simply to increment the program counter. Mere bitwise operations aren't all that useful. (Instruction cycle, not clock cycle - e.g. the 6502 takes a minimum ...


8

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 cannot do instructions at anything except multiples of this clock rate. If the clock rates were pushed higher, to maximize the speed of the bitwise operations, ...


7

The C's are not the same, but your statement about the AND gate is right. Unfortunately, the people who drew your full-adder decided to save space instead of maximizing readability. This image does a better job of showing the relationship between half adders and full adders, even though the circuit is identical to the one above: If they'd just put the ...


7

As far as I understand, the difference is indeed the clock/enable. A flip-flop samples the inputs only at a clock event (rising edge, etc.) A Latch samples the inputs continuously whenever it is enabled, that is, only when the enable signal is on. (or otherwise, it would be a wire, not a latch).


7

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, the speed of the hardware, for example measured as the delay of a single NAND-gate. This depends on the technology used, and on tradeoffs like speed vs. power ...


6

In multiplier design an (n,k) counter takes an n bit input and produces a k bit output which is the binary representation of the number of input bits that are 1s. That is: it counts the number of input bits set to 1. A (3,2) counter is just a full adder. A (7,3) counter is a circuit with 7 input bits and 3 output bits. The 3 output bits tell you (in ...


6

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 bits on parallel, This is true. Labeling a CPU as "XX" bit usually (not always) means that most of its common structures (register widths, addressable RAM etc....


5

You're misinterpreting the action of a ripple-carry adder. Each of the two boxed circuits takes in two 1-bit numbers (the top two inputs) and a carry bit (the left input) and returns a sum bit (the lower output) and a carry (the right output). In this example, you are adding $a_0+b_0$ (the 1, 1 left pair of inputs) and $a_1+b_1$ (the 1, 0 right pair of ...


4

You're confusing classical and quantum computation, so let me ignore the quantum aspects for now. If you forbid the unary NOT gate then you can use a binary NOT gate, say $g(a,b) = \lnot a$. You can also simulate NOT using natural gates: $XOR(a,1) = \lnot a$ (and this gate can even be made reversible!). So this kind of restriction is not really meaningful. ...


4

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 $$\big((a_k\wedge b_k)\vee((a_k\oplus b_k)\wedge \neg c_k)\big)\oplus a_{k+1}\oplus b_{k+1}=c_{k+1}.$$ That is because the first part, $(a_k\wedge b_k)\vee((a_k\...


4

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 multilinear polynomial. Here $\mathbb{Z}_2$ is the field with two elements, and a polynomial is multilinear if all monomials are products of distinct variables (so you ...


3

Use one of the standard techniques for circuit minimization. As far as I know, verifying that a candidate circuit is minimal is as hard as finding the minimal circuit in the first place (I know of no faster algorithm for verifying minimality than finding a minimal circuit in the first place). Circuit minimzation is NP-hard (in fact it's even harder than ...


3

This is called "sign-magnitide" or "signed-magnitude" representation. A Google search for "sign-magnitude adder" gives lots of useful results. I know this doesn't answer your question directly (I don't have enough reputation to simply comment your post), but you will find the answer there. As for only having AND and XOR, this is the classic result that any ...


3

It looks like you're missing the overlap case, if I understand your diagram correctly. This does the trick: A // goto B if read 0 else stay B // goto C if read 1 else stay C // goto D if read 1 else goto B D // goto E if read 0 else goto A E // emit rising edge, goto B assuming that you have a falling edge after every read.


3

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 for the same formula. Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates. In general, that circuit ...


3

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 finite field $\mathbb{F}_2$), this basically comes down to expressing the function as a multivariate polynomial over $\mathbb{F}_2[x_1,x_2,\dots,x_n]$ -- in ...


3

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 positive polarity Reed-Muller form (PPRM) $f(x_1,x_2,...,x_n) = a_0\oplus a_1x_1\oplus a_2x_2\oplus\ldots\oplus a_{12}x_1x_2\oplus a_{13}x_1x_3\oplus\ldots\...


3

Registers can be thought of as collections of flip-flops. These have inputs which, when activated, change the stored value. When not activated, the stored value stays the same. Look at the truth tables in the Wikipedia article.


3

A combinatorial circuit corresponds to a "straight-line program" that computes the outputs of the circuit given its inputs. (It has to satisfy some constraints that will exclude circuit (f) among others.) As an example, if we denote the inputs of circuit (c) by $x_1,x_2,x_3,x_4$ (top to bottom) and the output by $o$, then using $g_1,g_2$ for the ...


3

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 construction optimization is a very broad area handled by EE type papers/ applications/ algorithms, there are very many published. the general topic is "logic ...


3

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 logic circuit with only one kind of gate than it is to build it with all different gates. In fact, a NAND gate can be constructed from just an AND gate and a ...


3

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 more than expected. For example, conversion of binary to BCD. Both are 4 bits long but using 4 bits 16 binary numbers are possible whereas only 10 BCD numbers. ...


3

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 hardware many functions would be implemented as ROM modules. For example, below is a diagram from a 1991 patent US US5072291. Here one can see different ...


2

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 thought it was a latch since there was no clock labelled as such, but this might not actually be the case. The clock is an input that will determine when the state ...


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