Bit manipulation — XOR tricks, LSB, counting set bits: Foundations

This page builds every symbol the parent note leans on, from absolute zero. If the parent note said "just XOR the array" or "x & -x", we slow down and earn each piece first. Read top to bottom; nothing appears before it is defined and drawn.

0. What is a "bit"? (the switch)

Picture a single light switch on a wall. It has exactly two states. That is a bit. A computer number is a whole row of these switches sitting side by side.

Figure — Bit manipulation — XOR tricks, LSB, counting set bits

Why does the topic need this? Because every trick later ("toggle a switch", "find the lowest ON switch") is a statement about this row. If you cannot see the row, the tricks are just cryptic symbols.

1. Place value — why each switch is worth a doubling

Each switch is not worth the same. Reading the row right to left, the switches are worth $1, 2, 4, 8, 16, \dots$ i.e. each switch is worth twice the one to its right. These are the powers of two.

The value stored by a whole row is: add up the doubling-values of only the switches that are ON.

Related vault reading: Logarithms and Powers of Two — the exponent $i$ is literally the "log base 2" of the place value.

2. The summation symbol $\sum$ (writing "add them all up")

The parent note writes the number as $x = \sum_{i = 0}^{n - 1} b_{i} 2^{i}, b_{i} \in {0, 1} .$ That looks scary. It is just section 1 in shorthand. Let's earn every symbol.

So the formula reads, in English: "add up each switch's contribution, from the rightmost ( $i = 0$ ) to the leftmost ( $i = n - 1$ )." Exactly what we did to get 13.

3. Position, and the LSB / MSB names

The parent note's LSB tricks are all about position $0$ and about the lowest ON switch — so this naming has to be rock solid before section 4.

4. The core operators — one picture each

These operators act on two rows, column by column: they line the rows up and decide each output switch from the pair directly above it.

Recall Say each operator's rule in five words

AND ::: on only if both on OR ::: on if either is on XOR ::: on only if they differ NOT ::: flip every single switch

5. The symbol $\oplus$ — XOR written in maths

Programmers write XOR as ^. Mathematicians write the same thing as $\oplus$ (a plus inside a circle). The parent note uses $\oplus$ in its formulas.

Why does the topic hinge on this one operator? Because XOR-ing a value with itself gives all-zeros ( $a \oplus a = 0$ : every column has two equal switches, so none "differ"). That single fact makes duplicates self-destruct — the parent note's "cancellation engine". We earn the deep version of that in Deep Dive D2; here we just make sure you can read the symbol.

6. Shifting — `<<` and `>>` (slide the whole row)

7. Negatives and two's complement — where `-x` comes from

The parent note's star trick is x & -x, and it insists two's complement is "the secret". So we must define what a negative row even means.

Why this bizarre recipe? Because it makes ordinary addition "just work" — $x + (- x)$ rolls over to all-zeros, exactly as $- x$ should. Full justification lives in Two's Complement Representation; for our tricks you only need the recipe and one consequence, drawn below.

The picture shows the key consequence used by x & -x: below the lowest ON switch, $- x$ looks identical to $x$ (both all-OFF), and at that lowest ON switch both are ON, while everything above disagrees. That is precisely why AND-ing $x$ with $- x$ leaves only the lowest ON switch — but we build that derivation carefully in Deep Dive D3. Here you just need to trust the recipe and see the alignment.

One switch; 0 = OFF, 1 = ON.

What is the place value of switch at position

i

2^{i}

— each switch worth double the one to its right.

Evaluate the row 1011.

8 + 0 + 2 + 1 = 11

Read

\sum_{i = 0}^{n - 1} b_{i} 2^{i}

in plain English.

Add each switch's value (

2^{i}

if ON) from the rightmost to the leftmost.

Which switch is the LSB and what is it worth?

The rightmost, position 0, worth

2^{0} = 1

XOR (

\oplus

) output rule?

ON only when the two input bits differ.

What is

a \oplus a

All zeros — identical rows never differ.

What does x << k equal arithmetically?

x \cdot 2^{k}

What does x >> k equal for non-negative

x

⌊ x / 2^{k} ⌋

Give the two's complement recipe for

- x

Flip every bit (~x) then add 1.

Why isn't ~x alone equal to

- x

~x equals

- x - 1

; you must add 1.

What does

O (1)

space mean?

Memory used does not grow with input size.

Connections

Bit manipulation — parent topic — the tricks these foundations unlock.
Two's Complement Representation — full story behind the -x recipe in section 7.
Logarithms and Powers of Two — the exponent $i$ as $lo g_{2}$ of the place value.
Hash Sets vs O(1)-space tricks — why the Big-O of section 8 matters.
Bitmask Dynamic Programming — treating a whole switch-row as a set.
Greedy and Divide-and-Conquer (Algorithm Paradigms)

Foundations — Bit manipulation — XOR tricks, LSB, counting set bits