Bit Manipulation

Computers store integers in binary. Many competitive and systems problems become fast or elegant once you think in bits: set/clear flags, count ones, test powers of two, or represent subsets as integers.

This lesson follows CP-Algorithms — Bit Manipulation.

Binary numbers

A binary number (aₖ aₖ₋₁ … a₁ a₀)₂ represents

aₖ·2ᵏ + aₖ₋₁·2ᵏ⁻¹ + … + a₁·2¹ + a₀·2⁰

Example: 1101₂ = 8 + 4 + 0 + 1 = 13.

A bit is set if it is 1, cleared if it is 0.

unsigned int u = 13;
assert(u == 0b1101);

int positive = 13;
assert(positive == 0b1101);

int negative = -13; // two's complement on typical 32-bit int
assert(negative == 0b1111'1111'1111'1111'1111'1111'1111'0011);

CPUs execute fixed-width bit ops in roughly constant time — often faster than division.

Bitwise operators

Op	Name	Rule
&	AND	1 only if both bits are 1
|	OR	1 if either bit is 1
^	XOR	1 if bits differ
~	NOT	flip every bit

Example with n = 01011000₂:

n         = 01011000
n-1       = 01010111
--------------------
n & (n-1) = 01010000   ← clears rightmost set bit
n | (n-1) = 01011111
n ^ (n-1) = 00001111
~n        = 10100111

Shift operators

Op	Meaning
>> k	Shift right by k (integer divide by 2ᵏ for unsigned)
<< k	Shift left by k (multiply by 2ᵏ; drops high bits on fixed width)

Examples: 5 >> 2 = 1, 5 << 3 = 40.

Interactive playground

Step through Brian Kernighan's popcount or inspect classic bit tricks on 8-bit examples.

Useful tricks

Set / flip / clear bit x

1 << x has only bit x set. ~(1 << x) has every bit set except x.

n |  (1 << x)   set bit x
n ^  (1 << x)   flip bit x
n & ~(1 << x)   clear bit x

Test if bit x is set

bool is_set(unsigned int n, int x) {
    return (n >> x) & 1;
}

Divisible by 2ᵏ?

n & (2ᵏ − 1) == 0. Example: even ⇔ n & 1 == 0.

bool isDivisibleByPowerOf2(int n, int k) {
    int mask = (1 << k) - 1;
    return (n & mask) == 0;
}

2ᵏ − 1 is k low ones; divisibility by 2ᵏ forces those bits to zero.

Power of two?

A power of two has exactly one set bit. Its predecessor has that bit cleared and all lower bits set, so they share no 1 bits:

bool isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

(0 fails the n && guard.)

Clear rightmost set bit

n & (n - 1) turns off the lowest 1. Example: 52 = 00110100₂ → 00110000₂.

Brian Kernighan's popcount

Count set bits by repeatedly clearing the rightmost one:

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

Runs once per set bit — O(popcount(n)).

🧪 Bit tricks in action

Count set bits up to n (fast)

Summing Kernighan on every 1..n is too slow. Use: for numbers < 2ˣ, total set bits = x · 2^(x−1). Recurse on the remainder after stripping the top block.

More identities

Expression	Effect
n & (n + 1)	clear trailing ones
n | (n + 1)	set last cleared bit
n & -n	isolate lowest set bit

Check: operators & tricks

Quiz

Bit operators

1 / 5

n & (n - 1) does what (for n > 0)?

Pick an answer to see if you are right.

Subsets as integers

With n ≤ 20 objects, an n-bit mask represents a subset: bit i is 1 if object i is chosen. Iterate all masks with for (int m = 0; m < (1 << n); m++). This pattern appears in DP and brute force.

Language support

C++20 <bit>: popcount, countl_zero, has_single_bit, bit_floor, bit_ceil, rotl, rotr, …

GCC builtins (also useful pre-C++20):

Builtin	Meaning
__builtin_popcount(x)	number of set bits
__builtin_ffs(x)	index of lowest set bit (1-based)
__builtin_clz(x)	leading zeros
__builtin_ctz(x)	trailing zeros
__builtin_parity(x)	parity of popcount

Some targets need #pragma GCC target("popcnt") for fast hardware popcount.

Check: applications

Quiz

Bit applications

1 / 4

Brian Kernighan popcount loop runs…

Pick an answer to see if you are right.

Practice drills

Activity: Popcount

Count set bits in nonnegative n using n &= n - 1 (Brian Kernighan). Do not use bin(n).count.

Contest problems

A. Raising Bacteria

Judge: Codeforces 579A — Raising Bacteria

Each morning add any number of bacteria; each night every bacterium doubles. What is the minimum number of bacteria you must add (across mornings) to reach exactly x?

Why this lesson?

Each 1 in binary x is one manual add; overnight doubling fills gaps between them. Answer = popcount(x).

Sample

Input
5

Output
2

(101₂ has two ones.)

Cheat sheet

Goal	Trick
Clear lowest 1	n & (n-1)
Popcount	Kernighan loop
Power of two?	n && !(n & (n-1))
Lowest 1	n & -n
Set bit x	n | (1<<x)
Clear bit x	n & ~(1<<x)
Bit x of n	(n>>x) & 1
Diff count	popcount(a^b)
Subset mask	1<<n masks, loop m

Previous: Binary Search · Basic Geometry

Source: CP-Algorithms — Bit Manipulation