Digital Logic
What is ones' complement? Flip the bits, get the max minus n
The ones' complement of a binary number is the number with every bit flipped: each 0 becomes 1 and each 1 becomes 0. Flipping all n bits of x always gives the largest n-bit number minus x:
In three bits, the largest number is 7, so the ones' complement of 2 (010) is 101, which is 5: 7 − 2. In hardware it costs one NOT gate per bit, and a flip-flop gives it away for free on its Q̄ output.
Why flipping subtracts from the top
Add a number to its own ones' complement, column by column. In every column exactly one of the two bits is 1, so no column ever carries and every bit of the sum is 1:
| 4s | 2s | 1s | Value | |
|---|---|---|---|---|
| x | 0 | 1 | 0 | 2 |
| flipped | 1 | 0 | 1 | 5 |
| sum | 1 | 1 | 1 | 7 |
The sum is always all 1s, the largest number, so the flipped value must be the largest minus x.
A counter that reads both ways
Every flip-flop has two outputs: Q and its opposite, Q̄. Build a three-bit counter and wire one display to the Qs and another to the Q̄s. When the Qs say 3 (011), the Q̄s say 100, which is 4. As the Qs count up 0, 1, 2 … 7, the Q̄s count down 7, 6, 5 … 0. The two displays always add to 7.
Live experiment
One counter, two readings
Three toggling flip-flops count, and two displays read them: one from the Qs, one from the Q̄s, which always shows 7 minus the first. Clock each stage from Q and the count runs down from 7 to 0; from Q̄ it runs up. Either way, the two displays add up to 7.
“Count down” is lesson 2 of 6 in Toggle Tides, Digital Logic World 3. Free with an account. Lessons unlock in order, so you’ll do the 15 before it first.
Clock each stage of a ripple counter from the previous stage's Q instead of its Q̄ and the Qs themselves count down. From 0, the first tick borrows through every bit and wraps to 111, which is 7.
Flip on command with XOR
A NOT gate always flips. An XOR flips only when told: x XOR 1 is NOT x, and x XOR 0 is x. Put an XOR on each bit with a shared control line and the circuit passes a number through or hands back its ones' complement, one control wire deciding which.
From ones' to two's complement
Add 1 to the ones' complement and you get the two's complement, which is how computers store negative numbers. In four bits, −3 is the ones' complement of 0011, 1100, plus 1: 1101. That's why an ALU subtracts with the same adder it adds with: A − B = A + (NOT B) + 1, the NOT done by XORs and the +1 by the adder's carry-in.
Ones' complement on its own has a quirk that kept it out of modern processors: it has two zeros, 000 and 111, which read as +0 and −0. It survives in the checksums inside every IPv4, TCP and UDP packet.
Free lesson
Now build it yourself
Each lesson comes in three short parts: see the idea, try it on a live board, then build it yourself, with quick checks as you go.
“Count down” is lesson 2 of 6 in Toggle Tides, Digital Logic World 3. Free with an account. Lessons unlock in order, so you’ll do the 15 before it first.
Or start from the very first lesson, no account neededWork it out
Practice questions
Three quick questions from the lessons. Pick an answer to check it.
Show the answer
Answer: The Q of the stage before. From Q, a stage flips when the one before rises from 0 to 1. Counting down, that's exactly when a borrow is needed.
- Why not “Its own D”? D is the flip-flop's data input, not its clock. Each stage's clock comes from the stage before.
- Why not “The Q̄ of the stage before”? Clocked from Q̄, a stage flips when the one before falls from 1 to 0, which is a carry: that chain counts up.
- Why not “CLK, every stage”? With every toggling stage on the same clock they all flip together, which doesn't count at all.
Show the answer
Answer: Its inputs differ. Different in, 1 out. That's exactly the sum bit of 1 + 0.
- Why not “Either is 1”? Either input at 1 is the OR rule. XOR leaves out the case where both are 1.
- Why not “Both are 1”? Both at 1 makes an XOR give 0, which is exactly what lets x XOR 1 flip a bit.
- Why not “Both are 0”? Both at 0 gives 0. An XOR is 1 only when exactly one input is 1.
Show the answer
Answer: Q: FF1 copies itself and holds. Anything XOR 0 is itself. D is FF1's own Q, so each tick copies what it already holds.
- Why not “Always 1”? An XOR with one input at 0 just copies its other input, Q.
- Why not “Q̄: FF1 toggles”? XOR with 1 gives Q̄. With GO at 0, the XOR passes Q through unchanged.
- Why not “Always 0”? The output follows Q, which may be 0 or 1. It isn't forced to 0.
“Count down” is lesson 2 of 6 in Toggle Tides, Digital Logic World 3. Free with an account. Lessons unlock in order, so you’ll do the 15 before it first.
Questions people ask
How do you find the ones' complement of a binary number?
Flip every bit: each 0 becomes 1 and each 1 becomes 0. The ones' complement of 0110 is 1001. In hardware it's one NOT gate per bit, or an XOR per bit if you want to switch the flipping on and off.
What is the difference between ones' complement and two's complement?
Two's complement is the ones' complement plus 1. In four bits, the ones' complement of 3 (0011) is 1100, and the two's complement is 1101. Two's complement is how almost every modern computer stores negative numbers, because it has a single zero and lets one adder do subtraction.
Is ones' complement still used anywhere?
Yes. The checksums in IPv4, TCP and UDP headers are ones' complement sums, chosen because they're quick to compute and work the same on any byte order. Some early computers, such as the CDC 6600, stored signed numbers in ones' complement too.
Related topics
- Binary numbers explainedPlaces worth 1, 2, 4 and 8: add up the bits that are on, and four wires count to 15.
- How a binary counter divides a clock by 2, 4, 8 and 16Flip-flops that toggle, chained: each one halves the clock, together they count.
- Synchronous vs asynchronous countersBits that wait for each other, or bits that change on the same tick.
- What is an ALU, and how does it work?Work out every answer at once, then let the opcode pick one: the heart of a CPU.