Bit Manipulation — The Secret Language of Computers

Real-world analogy

What is it?

Bit manipulation is the technique of working directly with the binary (base-2) representation of numbers using bitwise operators like AND, OR, XOR, and shifts. Since computers store everything in binary, these operations are incredibly fast — often solving in one step what would normally take loops or complex math. It is a secret weapon in competitive programming!

Real-world relevance

Bit manipulation is used everywhere in real computing. File permissions in Linux use bits (read=4, write=2, execute=1). Network IP addresses use bit masking to define subnets. Video game engines use bitflags to track which items a player has collected. Compression algorithms like ZIP use bit-level operations to shrink files. Even the RGB colors on your screen are stored as bits — 8 bits for red, 8 for green, 8 for blue!

Key points

• Binary Numbers — How Computers Count — We humans count in base 10 (digits 0-9), but computers count in base 2 (digits 0 and 1). Each digit is called a bit. The number 5 in binary is 101, because 1*4 + 0*2 + 1*1 = 5. The number 13 is 1101, because 1*8 + 1*4 + 0*2 + 1*1 = 13. Each position represents a power of 2, starting from the right: 1, 2, 4, 8, 16, 32, and so on.
• Bitwise AND (&) — Both Must Be ON — The AND operator (&) compares each bit of two numbers. A bit in the result is 1 only if BOTH corresponding bits are 1. Think of it like two switches in series — the light turns on only if BOTH are ON. Example: 5 & 3 = 101 & 011 = 001 = 1. AND is super useful for checking if a specific bit is set, and for masking out bits you do not want.
• Bitwise OR (|) — Either Can Be ON — The OR operator (|) compares each bit of two numbers. A bit in the result is 1 if EITHER (or both) corresponding bits are 1. Think of it like two switches in parallel — the light turns on if ANY switch is ON. Example: 5 | 3 = 101 | 011 = 111 = 7. OR is great for setting bits — turning specific bits ON without affecting others.
• Bitwise XOR (^) — Exactly One Must Be ON — The XOR operator (^) compares each bit of two numbers. A bit in the result is 1 if the corresponding bits are DIFFERENT (one is 0 and one is 1). Same bits give 0. Example: 5 ^ 3 = 101 ^ 011 = 110 = 6. The magic of XOR: any number XOR itself equals 0, and any number XOR 0 equals itself. This leads to amazing tricks in competitive programming!
• Left Shift (>) — Left shift (>) moves bits to the right, which is like dividing by powers of 2. Example: 12 >> 2 = 3. Shifting is much faster than multiplication!
• Check Odd or Even with & 1 — Here is a super fast trick: to check if a number is odd or even, just do n & 1. If the result is 1, the number is odd. If it is 0, the number is even. Why? Because the last bit in binary represents the 1s place. Odd numbers always have their last bit set to 1 (like 3 = 11, 5 = 101, 7 = 111). Even numbers always have their last bit as 0 (like 4 = 100, 6 = 110). This is faster than using n % 2!
• Check, Set, and Clear Specific Bits — To check if bit k is set: use (n >> k) & 1. To set bit k (turn it ON): use n | (1 << k). To clear bit k (turn it OFF): use n & ~(1 << k). To toggle bit k (flip it): use n ^ (1 << k). These operations let you treat a number like an array of ON/OFF switches. This is the foundation of bitmask techniques used in advanced competitive programming!
• Power of 2 Check — One Line Magic — To check if a number is a power of 2, use: n > 0 && (n & (n - 1)) == 0. Why does this work? A power of 2 in binary is always a single 1 followed by zeros (like 8 = 1000). When you subtract 1, all those zeros become ones (7 = 0111). ANDing them gives 0 because no bits match! Non-powers of 2 will always have at least one bit in common. This trick is used everywhere in contests!
• XOR Trick — Find the Unique Element — Here is a classic contest problem: given an array where every number appears TWICE except one, find the unique number. Solution: XOR all elements together! Since a ^ a = 0 and a ^ 0 = a, all pairs cancel out and only the unique number remains. For example, XOR of [2, 3, 2] = 2^3^2 = (2^2)^3 = 0^3 = 3. This runs in O(n) time and O(1) space — you cannot beat that!

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // === Binary Representation ===
    int a = 13;  // Binary: 1101
    int b = 10;  // Binary: 1010
    cout << "a = " << a << " (binary: 1101)\n";
    cout << "b = " << b << " (binary: 1010)\n\n";

    // === Bitwise Operators ===
    cout << "a & b = " << (a & b) << " (AND: 1000 = 8)\n";
    cout << "a | b = " << (a | b) << " (OR:  1111 = 15)\n";
    cout << "a ^ b = " << (a ^ b) << " (XOR: 0111 = 7)\n";
    cout << "~a    = " << (~a) << " (NOT: flips all bits)\n\n";

    // === Shift Operators ===
    cout << "3 << 2 = " << (3 << 2) << " (multiply by 4)\n";
    cout << "20 >> 2 = " << (20 >> 2) << " (divide by 4)\n\n";

    // === Odd/Even Check ===
    for (int n = 1; n <= 6; n++) {
        cout << n << " is " << ((n & 1) ? "odd" : "even") << "\n";
    }
    cout << "\n";

    // === Check, Set, Clear, Toggle a bit ===
    int num = 10;  // Binary: 1010
    int k = 2;     // Check bit at position 2
    cout << "num = " << num << " (1010)\n";
    cout << "Bit " << k << " is: " << ((num >> k) & 1) << "\n";
    cout << "Set bit 0:    " << (num | (1 << 0)) << " (1011 = 11)\n";
    cout << "Clear bit 3:  " << (num & ~(1 << 3)) << " (0010 = 2)\n";
    cout << "Toggle bit 1: " << (num ^ (1 << 1)) << " (1000 = 8)\n\n";

    // === Power of 2 Check ===
    for (int n : {1, 2, 3, 4, 7, 8, 16, 15}) {
        bool isPow2 = (n > 0) && ((n & (n - 1)) == 0);
        cout << n << " is " << (isPow2 ? "" : "NOT ") << "a power of 2\n";
    }
    cout << "\n";

    // === XOR Trick: Find Unique Element ===
    vector<int> arr = {4, 1, 2, 1, 2};
    int unique_val = 0;
    for (int x : arr) unique_val ^= x;
    cout << "Array: 4 1 2 1 2\n";
    cout << "Unique element: " << unique_val << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. We start by defining two numbers a = 13 (binary 1101) and b = 10 (binary 1010). We will use these to demonstrate all the bitwise operators.
2. 2. a & b gives 8 (binary 1000) because AND only keeps bits where BOTH numbers have a 1. Only the leftmost bit (the 8s place) is 1 in both numbers.
3. 3. a | b gives 15 (binary 1111) because OR turns on a bit if EITHER number has a 1 there. Since a and b together cover all 4 bit positions, the result is all 1s.
4. 4. a ^ b gives 7 (binary 0111) because XOR turns on a bit where the two numbers DIFFER. The leftmost bit is the same (both 1), so it becomes 0. The other three bits differ, so they become 1.
5. 5. 3 << 2 shifts the bits of 3 (binary 11) left by 2 positions, giving 1100 = 12. Shifting left by k positions multiplies by 2^k, so 3 * 4 = 12.
6. 6. The odd/even check uses n & 1. This isolates the last bit. If it is 1, the number is odd. If it is 0, the number is even. This is faster than using the modulo operator!
7. 7. To check bit k, we shift right by k positions and AND with 1: (num >> k) & 1. This moves bit k to the last position and checks if it is 1 or 0.
8. 8. To set bit k, we OR with (1 << k). This creates a number with only bit k turned on, and ORing guarantees that bit becomes 1 without affecting other bits.
9. 9. The power-of-2 check n & (n-1) == 0 works because powers of 2 have exactly one 1-bit (like 1000), and subtracting 1 flips that bit and all below it (giving 0111). ANDing gives 0.
10. 10. The XOR trick for finding the unique element works because XOR is associative and a ^ a = 0. All paired elements cancel out, leaving only the element that appears once. Beautiful and efficient!

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Check if numbers are powers of 2
    vector<int> nums = {0, 1, 2, 3, 4, 8, 16, 15};

    for (int n : nums) {
        if ((n & (n - 1)) == 0) {
            cout << n << " is a power of 2\n";
        } else {
            cout << n << " is NOT a power of 2\n";
        }
    }
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Bit Manipulation for Competitive Programming (CP-Algorithms)
• Bit Manipulation — All You Need to Know (YouTube — Errichto)
• Bit Manipulation Practice Problems (LeetCode)