Sum of Two Integers
XOR adds the columns, AND-then-shift carries them
Column addition does two things at once: it writes a digit and it may push a carry to the next column left. Split them and the plus sign disappears. XOR writes the digit — it is 1 exactly when one of the two bits is 1, which is binary addition with the carry thrown away. AND finds the columns where both bits are 1, and those are precisely the columns that overflow, so shifting that pattern one place left is the carry. Feed the carry back in as the new b and repeat: each pass moves weight out of the carry and into the sum without changing the total, and once b reaches 0 there is nothing left to carry and a holds the answer.
Details
Animated on: a = 11, b = 7 — return their sum without using + or -. Cells are the six bit columns of a, MSB on the left; pointers mark the bits still set in b.
Problem:Sum of Two IntegersMedium
XOR adds the columns, AND-then-shift carries them
step 1 / 10
The cells are the bits of a = 11 (001011), MSB on the left; the pointers mark the bits still set in b = 7 (000111). Adding by hand is really two jobs — write the column digit, then push a carry one column left — and each job has its own bitwise operator, so neither needs a plus sign.
- b0=5· arr[5] = 1
- b1=4· arr[4] = 1
- b2=3· arr[3] = 0
1FUNCTION getSum(a, b)2 WHILE b != 03 carry <- (a AND b) SHIFTED LEFT 14 a <- a XOR b5 b <- carry6 RETURN a
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- The cells are the bits of a = 11 (001011), MSB on the left; the pointers mark the bits still set in b = 7 (000111). Adding by hand is really two jobs — write the column digit, then push a carry one column left — and each job has its own bitwise operator, so neither needs a plus sign.
- a AND b = 3 (000011) lights up bit 0 and bit 1 — the only columns where both numbers hold a 1, which is exactly where a hand-written sum would overflow. Sliding that pattern one column left turns it into the carry 6 (000110), because a carry out of bit k is worth twice as much and belongs in bit k+1.
- XOR keeps a 1 only where exactly one of the two had one, so a becomes 12 (001100) — the addition with every carry ignored — and the carry 6 takes over as the new b. The pair still totals 18, the same as 11 and 7 did, so the loop never loses value, it only moves weight out of the carry and into the sum.
- a AND b = 4 (000100) lights up bit 2 — the only column where both numbers hold a 1, which is exactly where a hand-written sum would overflow. Sliding that pattern one column left turns it into the carry 8 (001000), because a carry out of bit k is worth twice as much and belongs in bit k+1.
- XOR keeps a 1 only where exactly one of the two had one, so a becomes 10 (001010) — the addition with every carry ignored — and the carry 8 takes over as the new b. The pair still totals 18, the same as 12 and 6 did, so the loop never loses value, it only moves weight out of the carry and into the sum.
- a AND b = 8 (001000) lights up bit 3 — the only column where both numbers hold a 1, which is exactly where a hand-written sum would overflow. Sliding that pattern one column left turns it into the carry 16 (010000), because a carry out of bit k is worth twice as much and belongs in bit k+1.
- XOR keeps a 1 only where exactly one of the two had one, so a becomes 2 (000010) — the addition with every carry ignored — and the carry 16 takes over as the new b. The pair still totals 18, the same as 10 and 8 did, so the loop never loses value, it only moves weight out of the carry and into the sum.
- a AND b = 0: no column holds a 1 in both numbers, so no column can overflow and the carry is 0. Every remaining 1 lands straight into the answer on this pass.
- XOR keeps a 1 only where exactly one of the two had one, so a becomes 18 (010010) — the addition with every carry ignored — and the carry 0 takes over as the new b. The pair still totals 18, the same as 2 and 16 did, so the loop never loses value, it only moves weight out of the carry and into the sum.
- b is 0, so no carry is left with anywhere to go and the loop stops: a = 18 (010010) is the answer. 11 and 7 needed 4 passes, one for each round of carries — the loop runs once per carry chain, never once per bit.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.