Bit manipulation is a technique for solving problems efficiently using bitwise operations. It is useful for optimization and low-level programming tasks.

Applications

Counting set bits
XOR problems
Subset generation

Theory

In Competitive Programming (CP), bit manipulation is a “superpower.” It allows you to solve problems in $O(1)$ or $O(K)$ (where $K$ is the number of bits, usually 30 or 60) that would otherwise take $O(N)$ loops.

CP Module 1: Bit Manipulation Mastery

1. The Core Operators

Computers store integers as sequences of bits (0s and 1s).

Integer (32-bit): int (up to $\approx 2 \times 10^9$)
Long Long (64-bit): long long (up to $\approx 9 \times 10^{18}$)

Operator	Symbol	Mnemonic	Logic
AND	`&`	“Both must be 1”	$1 \& 1 = 1$, else $0$
OR	`\\|`	“At least one 1”	$0 \mid 0 = 0$, else $1$
XOR	`^`	“Must be different”	$1 \oplus 0 = 1$, $0 \oplus 1 = 1$, else $0$
NOT	`~`	“Flip everything”	$\sim 1 = 0$, $\sim 0 = 1$
Left Shift	`<<`	“Multiply by 2”	$a \ll b$ means $a \times 2^{b}$
Right Shift	`>>`	“Divide by 2”	$a \gg b$ means $a / 2^{b}$

2. The “Magic” of XOR (`^`)

XOR is the most important bitwise operator in competitive programming.

Key Properties:

Self-Inverse: $x \oplus x = 0$ (Anything XORed with itself vanishes).
Identity: $x \oplus 0 = x$ (XORing with 0 changes nothing).
Commutative and Associative: $a \oplus b \oplus c = c \oplus a \oplus b$ (Order doesn’t matter).

Classic Problem:

Given an array where every number appears twice except one number. Find that unique number.
Solution: XOR all numbers together. The duplicates cancel out ($a \oplus a = 0$), leaving only the unique number.

3. Essential “One-Liner” Tricks

These are standard patterns you will use in almost every bitwise problem.

A. Checking Bits

How do I know if the $i$-th bit is set (1) or unset (0)?

Logic: Create a “mask” with a 1 at position $i$ ($1 \ll i$) and AND it.

bool isSet = (n & (1 << i)) != 0;

B. Setting Bits

How do I turn the $i$-th bit ON?

Logic: OR it with the mask.

n = n | (1 << i);

C. Unsetting Bits

How do I turn the $i$-th bit OFF?

Logic: AND it with the inverse of the mask.

n = n & ~(1 << i);

D. Toggling Bits

How do I flip the $i$-th bit ($0 \to 1$, $1 \to 0$)?

Logic: XOR it with the mask.

n = n ^ (1 << i);

E. Checking Odd/Even

Checking $n \% 2$ is slow. Checking the last bit is fast.

if (n & 1) { /* It's Odd */ }
else       { /* It's Even */ }

F. Checking Power of 2

A power of 2 (like 2, 4, 8, 16) has exactly one bit set.

Property: If $n$ is a power of 2, then $n \& (n-1)$ is always $0$.

bool isPowerOfTwo = (n > 0) && ((n & (n - 1)) == 0);

4. Built-in Functions (GCC)

C++ has extremely fast built-in functions for counting bits. Use these instead of writing loops.

Function	Description	Example $x = 5$ ($101$)	Returns
`__builtin_popcount(x)`	Count number of 1s	$101$	$2$
`__builtin_clz(x)`	Count Leading Zeros	$101$ (32-bit int)	$29$
`__builtin_ctz(x)`	Count Trailing Zeros	$101$	$0$

Important Note: For long long, append ll (e.g., __builtin_popcountll(x)).

Interactive Practice

Let’s try a quick mental exercise to verify your understanding.

Problem: You have the number $n = 5$ (binary $101$).

What is $n \ll 1$?
What is $n \oplus n$?
What is $n \& (n - 1)$?

Think about it, then scroll down for the answer.

Click to Reveal Answers

10: 101 shifted left becomes 1010 (Decimal 10). This is $5 \times 2$.
0: Anything XOR itself is 0.
4: 5 (101) AND 4 (100) = 100 (Decimal 4). This operation "clears the lowest set bit."