Bitwise Operators — Section 14: Bit Manipulation

Bit manipulation operates directly on the binary representation of integers. The operators are single CPU instructions, so bit-level algorithms can be dramatically faster than arithmetic equivalents.

The six operators

AND ( $a \& b$ ): bits set in both
OR ( $a \,|\, b$ ): bits set in either
XOR ( $a \oplus b$ ): bits set in exactly one
NOT ( $\sim a$ ): flip every bit
Left shift ( $a \ll k$ ): shift bits left by $k$ — multiplies by $2^k$
Right shift ( $a \gg k$ ): shift right by $k$ — integer-divides by $2^k$

Useful patterns

Test the $k$ -th bit: `(a >> k) & 1`
Set the $k$ -th bit: `a | (1 << k)`
Clear the $k$ -th bit: `a & ~(1 << k)`
Toggle the $k$ -th bit: `a ^ (1 << k)`
Lowest set bit: `a & -a` (gives the value of the lowest set bit)
Clear lowest set bit: `a & (a - 1)` — used to count set bits

Counting set bits (popcount)

Repeated `a &= a - 1` until $a$ is zero; each iteration clears one bit. $O(\text{number of set bits})$ . Modern CPUs have a dedicated POPCNT instruction that does this in one cycle — compilers emit it for built-in popcount functions.

Two's complement

In two's complement, negative numbers have the high bit set and represent $-2^{k-1}$ plus the value of the remaining bits. Why this matters: `-a == ~a + 1`. This is how `a & -a` extracts the lowest set bit — `-a` has all higher bits flipped, and `~a + 1` re-aligns.

Endianness

Bit manipulation operates on values, not on the byte layout in memory. Endianness affects byte-level views (casting an int* to a char*) but not the result of bitwise operators on integers.