Bit Manipulation for Competitive Programming

Bit manipulation is one of the most powerful tools in competitive programming. Many problems that seem difficult at first can be solved elegantly by thinking in terms of bits.

In this blog, we'll cover the most useful bit tricks every competitive programmer should know.

1. Binary Representation

Every integer can be represented as a sequence of bits.

Example:

13 = 1101₂

Position of bits (from right to left):

Bit:  3 2 1 0
      1 1 0 1

Value:

13 = 1×2³ + 1×2² + 0×2¹ + 1×2⁰

2. Basic Bitwise Operators

AND (&)

A bit is 1 only if both bits are 1.

5 = 101
3 = 011
---------
& = 001 = 1

OR (|)

A bit is 1 if at least one bit is 1.

5 = 101
3 = 011
---------
| = 111 = 7

XOR (^)

A bit is 1 if bits are different.

5 = 101
3 = 011
---------
^ = 110 = 6

Useful property:

a ^ a = 0
a ^ 0 = a

NOT (~)

Flips all bits.

~5

Be careful with signed integers.

3. Left and Right Shift

Left Shift

x << k

Multiplies by 2ᵏ.

Example:

5 << 2 = 20

Right Shift

x >> k

Divides by 2ᵏ (for positive numbers).

Example:

20 >> 2 = 5

4. Check if the i-th Bit is Set

if (x & (1 << i))
{
    // i-th bit is set
}

Example:

x = 13; // 1101
i = 2;

Bit 2 is set.

5. Set the i-th Bit

x |= (1 << i);

Example:

x = 8; // 1000
set bit 1

Result:

1010 = 10

6. Unset the i-th Bit

x &= ~(1 << i);

Example:

x = 13; // 1101
unset bit 2

Result:

1001 = 9

7. Toggle the i-th Bit

x ^= (1 << i);

If bit is set → unset.

If bit is unset → set.

8. Count Set Bits

Built-in Function

__builtin_popcount(x);

For long long:

__builtin_popcountll(x);

Example:

__builtin_popcount(13);

Output:

3

because

13 = 1101

contains three 1s.

9. Check if a Number is Power of Two

A power of two has exactly one set bit.

bool isPowerOfTwo(int x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

Examples:

1  -> Yes
2  -> Yes
4  -> Yes
8  -> Yes
12 -> No

10. Remove the Lowest Set Bit

x = x & (x - 1);

Example:

x = 12
1100

x-1 = 1011

Result:
1000

One set bit is removed.

This trick is commonly used in popcount implementations.

11. Extract the Lowest Set Bit

x & (-x)

Example:

12 = 1100

1100
0100

Answer:

4

Useful in Fenwick Trees.

12. XOR Tricks

Find Unique Element

Given:

1 2 3 2 1

Every number appears twice except one.

int ans = 0;
for(int x : a)
    ans ^= x;

Answer:

3

because

a ^ a = 0

13. Generate All Subsets

For an array of size n:

for(int mask = 0; mask < (1 << n); mask++)
{
    for(int i = 0; i < n; i++)
    {
        if(mask & (1 << i))
        {
            // take element i
        }
    }
}

Complexity:

O(n * 2^n)

A fundamental technique for brute-force and DP over subsets.

14. Useful Competitive Programming Problems

Try solving:

1. Missing Number
2. Single Number
3. Subset Sum (Bitmasking Version)
4. Travelling Salesman DP
5. Hamiltonian Path DP
6. SOS DP Problems
7. Maximum XOR Pair
8. Gray Code

Common Mistakes

1. Overflow

Avoid:

1 << 31

Use:

1LL << 31

2. Operator Precedence

Wrong:

if(x & 1 == 0)

Correct:

if((x & 1) == 0)

3. Using int for Large Masks

For up to 60 bits:

long long

or

uint64_t

Final Thoughts

Bit manipulation often turns an O(n²) solution into O(n) or O(log n). Many advanced topics such as Bitmask DP, SOS DP, XOR Basis, Fenwick Trees, and Segment Trees rely heavily on bitwise operations.

The best way to master bit manipulation is to practice. Start with simple bit tricks, then move to subset generation and DP over bitmasks.

Happy Coding!