Bit Manipulation Technique

All data in a computer is stored as bits — just 0s and 1s. Knowing how to work with them directly is one of the most powerful skills in competitive programming. This post covers bit representations, common operations, and practical applications you'll actually use in contests. Bit Representation

An $$$n$$$-bit integer is stored as a binary number with $$$n$$$ bits. For example, int in C++ is 32-bit.

The number $$$43$$$ looks like this in binary: 00000000000000000000000000101011

Bits are indexed right to left. The conversion formula is:

$$$b_k \cdot 2^k + \ldots + b_1 \cdot 2^1 + b_0 \cdot 2^0$$$

So $$$43 = 1\cdot2^5 + 1\cdot2^3 + 1\cdot2^1 + 1\cdot2^0$$$.

Signed vs Unsigned: - A signed $$$n$$$-bit integer holds values in $$$[-2^{n-1},\ 2^{n-1}-1]$$$ - An unsigned $$$n$$$-bit integer holds values in $$$[0,\ 2^n - 1]$$$ - The signed number $$$-x$$$ equals the unsigned number $$$2^n - x$$$ - Overflow: after $$$2^{n-1}-1$$$, a signed int wraps to $$$-2^{n-1}$$$

Bit Operations

AND ( & ) — 1 only where both bits are 1

22 & 26 = 18
10110 (22)
11010 (26)
-----
10010 (18)

Useful trick: x & 1 == 0 means x is even. More generally, $$$x$$$ is divisible by $$$2^k$$$ iff [b]x & (2^k — 1) == 0[/b].

OR ( | ) — 1 where at least one bit is 1

22 | 26 = 30
10110 (22)
11010 (26)
-----
11110 (30)

XOR ( ^ ) — 1 where exactly one bit is 1

22 ^ 26 = 12
10110 (22)
11010 (26)
-----
01100 (12)

NOT ( ~ ) — flips all bits. Formula: = -x — 1 ~29 = -30

Bit Shifts:

x << k — multiply x by $$$2^k$$$ (append k zero bits) x >> k — divide x by $$$2^k$$$ rounded down (remove k last bits) 14 << 2 = 56 // 1110 → 111000 49 >> 3 = 6 // 110001 → 110

Useful Bit Tricks

x | (1 << k)     // set kth bit to 1
x & ~(1 << k)   // set kth bit to 0
x ^ (1 << k)    // flip kth bit
x & (x - 1)     // clear the lowest set bit
x & (-x)        // isolate the lowest set bit
x | (x - 1)     // set all bits after the lowest set bit
x & (x-1) == 0  // true iff x is a power of two[/code]

Print the bit representation of an int:

for (int i = 31; i >= 0; i--) {
    if (x & (1 << i)) cout << "1";
    else cout << "0";
}

Built-in GCC Functions

int x = 5328; // 00000000000000000001010011010000
__builtin_clz(x)       // 19 — leading zeros
__builtin_ctz(x)       // 4  — trailing zeros
__builtin_popcount(x)  // 5  — count of 1-bits
__builtin_parity(x)    // 1  — parity of 1-bits[/code]