Visual walkthrough — Bit manipulation — XOR tricks, LSB, counting set bits

Prerequisite you may want open in a second tab: Two's Complement Representation and Logarithms and Powers of Two. The parent is the topic note.

---

Step 1 — An integer is a row of switches

WHAT. Before any trick, agree on what an integer is. A computer stores a whole number as a fixed-length row of switches. Each switch is a bit: it is either OFF (we write $0$) or ON (we write $1$).

WHY. Every trick on this page is really "look at the switches and flip some." If you picture the number as an amount you will be lost; picture it as a row of lights and every step becomes obvious.

PICTURE. Look at the figure. Each box is one switch. The box at the far right is switch number $0$; moving left, switch number $1$, then $2$, and so on. Each switch has a place value printed under it: $2^0=1$, $2^1=2$, $2^2=4$, $2^3=8$, ...

$x={\sum }_{i=0}^{n-1}\underset{\begin{array}{c}\text{switch }i\\ \text{is }0\text{ or }1\end{array}}{\underbrace{b_i}}\cdot \underset{\begin{array}{c}\text{its}\\ \text{place value}\end{array}}{\underbrace{2^i}}$

Reading each symbol where it sits: $b_i$ is the state of switch $i$ (ON$=1$, OFF$=0$); $2^i$ is the worth of that switch; the $\sum$ (a "add-up-all" sign) just says: the number equals the total worth of every switch that is ON.

---

Step 2 — Our running example, drawn as switches

WHAT. Fix one concrete number to carry through every step: $x=12$.

WHY. A derivation with pictures needs a specimen. $12$ is small enough to draw and has its lowest ON switch above position $0$, which will make the "lowest, not zeroth" point vivid.

PICTURE. $12=8+4=2^3+2^2$. So switches $3$ and $2$ are ON, switches $1$ and $0$ are OFF.

$12=\stackrel{\text{pos }3}{1}\stackrel{\text{pos }2}{1}\stackrel{\text{pos }1}{0}\stackrel{\text{pos }0}{0}$

The lowest ON switch is at position $k=2$ (worth $2^2=4$). Our whole goal: get a machine to spit out $4$, keeping nothing else. Hold the number $4$ in your head — it is the target.

---

Step 3 — What does "negative" do to the switches? (two's complement)

WHAT. The trick uses $-x$. But a switch-row has no minus sign — so what does the machine physically store for $-12$? The rule is two's complement: $-x=\underset{\text{flip every switch}}{\underbrace{(\neg x)}}+\underset{\text{then add one}}{\underbrace{1}}$

WHY THIS TOOL. We could ask "why not just store a sign?" Because the AND trick only works because $-x$ is built by flipping and adding one — that specific recipe is what lines up a single $1$ under the lowest set bit. So we must watch the recipe act on the switches, not treat $-x$ as an abstract negative.

PICTURE. Two sub-actions, drawn as two rows.

• $\neg x$: flip every switch of $12=1100$ → $0011$.
• $+1$: add one to $0011$ → $0100$.

Term by term across the figure: the top row is $x$; the middle row is flip-all ($\neg x$), where every ON became OFF and vice-versa; the bottom row is add one, which we examine microscopically next because the "add 1" is where the magic hides.

---

Step 4 — Zoom in on the "+1": why the trailing zeros survive

WHAT. Watch the "$+1$" ripple, digit by digit, on $\neg x=0011$.

WHY. This single ripple is the entire reason the answer is the lowest bit and not some other one. If you understand this ripple you understand the trick.

PICTURE. Adding $1$ starts at the rightmost switch and carries left through every ON switch until it hits the first OFF one, which it turns ON — then it stops.

Trace it on the figure: $\underset{\neg x}{\underbrace{0011}}+1=\underset{-x}{\underbrace{0100}}$

• Position $0$: $1+1=10$, write $0$ carry $1$.
• Position $1$: $1+\text{carry }1=10$, write $0$ carry $1$.
• Position $2$: $0+\text{carry }1=1$, write $1$, carry stops.
• Position $3$: unchanged $=0$.

The key observation (green arrow in the figure): the carry marches through the region that in the original $x$ was "the lowest $1$ followed by trailing $0$s," and it plants exactly one $1$ at position $k=2$ — the same place as $x$'s lowest set bit.

---

Step 5 — The general picture (any number, split into three zones)

WHAT. Now do it for a general $x$, not just $12$, by splitting the switch-row into three zones around the lowest ON switch at position $k$.

WHY. One example is not a proof. If we name the three zones we can watch all of $x$, $\neg x$, and $-x$ at once and see the pattern must always hold.

PICTURE. Write $x$ as: $x=\underset{\text{high zone}}{\underbrace{a}}\underset{\text{the lowest ON, pos }k}{\underbrace{1}}\underset{k\text{ trailing zeros}}{\underbrace{0\cdots 0}}$ Here $a$ is whatever the high switches are (we don't care what), the lone $1$ is the lowest set bit, and below it sit $k$ zeros.

Now build $-x$ in the same three zones (read straight off the figure):

zone	$x$	$\neg x$ (flip)	$+1$ ripple	$-x$ result
high	$a$	$\bar{a}$	untouched	$\bar{a}$
pos $k$	$1$	$0$	carry lands here → $1$	$1$
trailing	$0\cdots 0$	$1\cdots 1$	all flip back to $0$	$0\cdots 0$

So: $-x=\bar{a}1\underset{k}{\underbrace{0\cdots 0}}$ where $\bar{a}$ means "$a$ with every switch flipped." Notice: $x$ and $-x$ agree at position $k$ (both $1$) and in the trailing zone (both $0$), but they are exact opposites in the high zone.

---

Step 6 — AND the two rows: everything cancels but one bit

WHAT. Apply & (AND: output $1$ only when both inputs are $1$) to $x$ and $-x$, zone by zone.

WHY THIS OPERATOR. We want to keep the position where both agree on $1$ and kill everywhere else. AND is precisely the "survives only if both are ON" filter — no other single operator does that.

PICTURE. Line $x$ over $-x$ and AND each column.

$$\begin{array}{cccc}\text{high zone: }& a\&\bar{a}& =& 0(\text{a bit and its flip are never both 1})\\ \text{position }k:& 1\&1& =& 1(\text{both ON}\Rightarrow \text{survives})\\ \text{trailing: }& 0\&0& =& 0(\text{both OFF})\end{array}$$

Every high column dies (a switch and its flip can't both be ON). The trailing columns die (both OFF). Only column $k$ survives, holding a single $1$. Therefore $\boxed{x\&-x=2^k}$ — exactly the isolated lowest set bit. For our specimen, $12\&-12=0100=4$. Target hit. ✓

---

Step 7 — The degenerate cases (never leave the reader stranded)

WHAT. Check the inputs that break naive intuition: $x=0$, a power of two, and the all-ones number.

WHY. A trick you only tested on $12$ is a trap. We must know what happens at the edges.

PICTURE. Three tiny switch-rows.

• $x=0$ (no switch ON). Then $-0=0$, and $0\&0=0$. There is no lowest set bit, and the trick correctly returns $0$. Not a crash — a meaningful "nothing here."
• $x=8=1000$ (a power of two — a single ON switch). The lowest set bit is the only set bit, so x & -x returns $8$ itself. Consistent with the "power of two has one bit" test.
• $x=7=0111$ (lowest ON at position $0$). Then $k=0$, trailing zone is empty, and x & -x $=0001=1=2^0$. The formula $2^k$ with $k=0$ still holds.

---

The one-picture summary

This single figure compresses all seven steps: the three zones of $x$, the flip-and-add-one that builds $-x$, and the AND that leaves one lonely bit.

Recall Feynman retelling — explain the whole walkthrough to a 12-year-old

Picture a row of light switches; the number is just which ones are ON. To make the number "negative," the computer flips every switch and then adds one — and adding one is like a domino: it knocks over all the ON switches at the right end until it reaches the first OFF switch, which it turns ON, and then it stops. Because of that domino, the negative version matches the original at exactly one spot: the lowest switch that was ON. Everywhere else, one row's switch is ON while the other is OFF — they disagree. Now play a game called AND: keep a switch only if it's ON in both rows. Everywhere they disagreed, that switch dies. Only the one spot where they agreed lives — the lowest ON switch. So x & -x is a flashlight that always finds the rightmost light that's on, and hands you just that one, worth $2^k$.

Connections

• Two's Complement Representation — the flip-and-add-one recipe used in Steps 3–4.
• Logarithms and Powers of Two — the highest set bit is $2^{\lfloor {\log }_{2}x\rfloor }$, contrast to Step 7.
• Hash Sets vs O(1)-space tricks — why bit tricks buy $O(1)$ space.
• Bitmask Dynamic Programming — iterating subsets uses x & -x.
• Greedy and Divide-and-Conquer (Algorithm Paradigms).