Bit Operations

The core idioms

x & (1 << i)          // test bit i (non-zero if set)
x >> i & 1            // test bit i (gives 0 or 1)
x | (1 << i)          // set bit i
x & ~(1 << i)         // clear bit i
x ^ (1 << i)          // toggle bit i
 
x & (x - 1)           // clear the lowest set bit
x & (-x)              // isolate the lowest set bit  (== x & (~x + 1))
x | (x + 1)           // set the lowest clear bit
x & (x + 1)           // clear all trailing ones
~x & (x + 1)          // isolate the lowest clear bit
 
x == (x & -x)         // is x a power of two? (plus x != 0)
(x & (x - 1)) == 0    // same test

Shift pitfalls

• 1 << i is an int. For $i\ge 31$ this is undefined behaviour — write 1LL << i.
• Shifting by $\ge$ the type’s width is undefined, not zero.
• -x on the minimum value of a signed type is undefined; use unsigned for bit twiddling.

Builtin functions

__builtin_popcount(x)      // number of set bits          (ll: __builtin_popcountll)
__builtin_clz(x)           // count leading zeros         — UNDEFINED for x == 0
__builtin_ctz(x)           // count trailing zeros        — UNDEFINED for x == 0
__builtin_parity(x)        // popcount & 1
__lg(x)                    // floor(log2(x)) = 31 - clz(x)

C++20 offers portable equivalents in <bit>: popcount, countl_zero, countr_zero, bit_width, bit_ceil, has_single_bit, rotl, rotr. See Builtin Bit Functions.

Derived quantities

Want	Expression
$\lfloor {\log }_{2}x\rfloor$	31 - __builtin_clz(x) or __lg(x)
Highest power of 2 $\le x$	1 << __lg(x)
Smallest power of 2 $\ge x$	x <= 1 ? 1 : 1 << (__lg(x-1) + 1)
Is $x$ a power of 2	x && !(x & (x-1))
Round down to a multiple of $2^k$	x & ~((1<<k)-1)
Round up to a multiple of $2^k$	(x + (1<<k) - 1) & ~((1<<k)-1)
Swap without a temporary	a ^= b; b ^= a; a ^= b; (fails if &a == &b)
Absolute value, branchless	(x ^ (x>>31)) - (x>>31)
Min, branchless	b ^ ((a ^ b) & -(a < b))
Sign	(x > 0) - (x < 0)

The branchless forms are curiosities on modern CPUs — the compiler generates cmov from the obvious code. Write the readable version.

Set semantics

Treating an integer as a set over $\{\mathrm{0..}n-1\}$:

Set operation	Bit operation
Union $A\cup B$	a | b
Intersection $A\cap B$	a & b
Difference $A\setminus B$	a & ~b
Symmetric difference	a ^ b
Complement	~a & ((1<<n)-1)
Is $A\subseteq B$?	(a & b) == a
Are $A,B$ disjoint?	(a & b) == 0
$|A|$	__builtin_popcount(a)
Add element $i$	a | (1<<i)
Remove element $i$	a & ~(1<<i)
Full set	(1<<n) - 1

See Set Theory.

Iterating

// over the set bits of x
for (int t = x; t; t &= t - 1) {
    int i = __builtin_ctz(t);
    // ...
}
 
// over all submasks of mask (including 0)
for (int s = mask; ; s = (s - 1) & mask) {
    // ...
    if (s == 0) break;
}
 
// over all supermasks of mask within n bits
for (int s = mask; s < (1 << n); s = (s + 1) | mask) { /* ... */ }

The submask loop is $O(3^n)$ summed over all masks — see Enumerating Submasks.

XOR facts worth memorising

Fact
$x\oplus x=0$, $x\oplus 0=x$	self-inverse
XOR is associative and commutative	order does not matter
$a\oplus b\oplus b=a$	undo by repeating
$1\oplus 2\oplus \cdots \oplus n$ has period 4 in $n$	$n\mathrm{mod}4=0,1,2,3\to n,1,n+1,0$
$a+b=(a\oplus b)+2(a\&b)$	XOR is addition without carries
$a+b=(a|b)+(a\&b)$
$a\oplus b\le a+b$
Find the single non-repeating element	XOR everything

The prefix-XOR period-4 identity computes ${⨁}_{i=l}^{r}i$ in $O(1)$, which is the standard trick for XOR-range problems.

See also: General · Builtin Functions · Bitset Optimization