# Tag Info

### Why is 2's complement used for representing negative numbers?

The main reason is that there needs to be no special handling to perform arithmetic with negative numbers. The hardware does not need to check the sign bit and inverse the operation (add becomes ...
• 207
Accepted

### Why is 2's complement used for representing negative numbers?

As you said, one's complement wastes one configuration of bits. Moreover, it requires additional logic to handle the two representations of zero. It also requires a more complex (hardware) ...
• 29.5k
1 vote
Accepted

### Does P=BPP implies we can construct a Boolean circuit for a fair coin flip?

No, it's impossible regardless of what conjectures you might make. A deterministic circuit will always produce the same thing, when given the same inputs. A random coin flip won't. Those are ...
• 162k
1 vote

### Is there an algorithm to implement N-input-gates using smaller gates?

You can always check whether two circuits have identical behaviour, there are only a finite number of circuits of size k for every k, so you can just systematically try out all circuits ordered by ...
• 30.7k
1 vote

### $n \pmod k$ circuit

Here is some JS code that performs the n mod k operations. To visualize I generate all 8-bit representations and let them run through the function to output a truth table, outputting True if divisible ...
• 123
1 vote

### How do you compute and compare the delays between a (4:2) compressor and (3,2) counter carry save tree?

It took me a while to figure out what this circuit does: It takes 5 inputs and produces 3 outputs. (So why is it called a 4-2 compressor and not a 5-3 compressor?) One output is the sum with a value ...
• 30.7k
1 vote

### How do you compute and compare the delays between a (4:2) compressor and (3,2) counter carry save tree?

The first column list all ranges with uniform number of levels for both approaches, up to 42. One way is to start with one level, and compute how many inputs a circuit with that many outputs ...
• 1,074

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