Week 5: Bit Manipulation

1. Bitwise Operators & Masks

An int is just 32 bits sitting in memory, and C++ gives you direct operators on those bits: & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift) and >> (right shift). A mask is just an integer whose bit pattern you build on purpose so that combining it with another integer isolates, sets, or clears the bits you care about.

// 1 << k  is an int with only bit k set -- the building block for every mask below
int mask = 1 << 3;              // 0b00001000

// Check if bit k is set
bool isSet(int n, int k) {
    return (n & (1 << k)) != 0;
}

// Set bit k to 1
int setBit(int n, int k) {
    return n | (1 << k);
}

// Clear bit k to 0
int clearBit(int n, int k) {
    return n & ~(1 << k);
}

// Toggle bit k
int toggleBit(int n, int k) {
    return n ^ (1 << k);
}

// n << 1 doubles n; n >> 1 halves n (integer division, rounding toward negative infinity
// for signed types) -- both run in O(1), which is why shifting beats *2 or /2 in tight loops

Reading these back in English builds the intuition you'll lean on constantly: n & (n - 1) clears the lowest set bit, n & -n isolates it, and n & 1 tells you if n is odd. None of these need a loop — each is a single O(1) CPU instruction.

2. The XOR Trick Family

XOR has two properties that make it the single most reused operator in interview bit tricks: x ^ x == 0 (a value cancels itself out) and x ^ 0 == x (zero is the identity element). Combined with the fact that XOR is commutative and associative — order and grouping don't matter — you can XOR a whole collection together and every value that appears an even number of times disappears.

#include <vector>
using namespace std;

// Every value appears twice except one -- find the one that appears once.
// O(n) time, O(1) space -- no hash set needed.
int singleNumber(const vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;   // pairs cancel to 0, the lone value survives
    return result;
}

// nums contains n distinct values from 0..n, one is missing -- find it.
// XOR every index 0..n with every value in nums; every present value cancels
// with its index-twin, leaving only the missing number.
int missingNumber(const vector<int>& nums) {
    int result = nums.size();          // account for index n up front
    for (int i = 0; i < (int)nums.size(); i++) {
        result ^= i;
        result ^= nums[i];
    }
    return result;
}

The same idea extends further: to find two numbers that each appear once while every other number appears twice, XOR the whole array first — the result is a ^ b for the two lone values. Because a != b, that XOR has at least one set bit; picking any one set bit and splitting the array into "bit set" and "bit clear" groups puts a and b in different groups, and XOR-ing each group separately recovers both values in a second O(n) pass.

3. Counting Set Bits: Brian Kernighan's Algorithm

The naive way to count how many bits are set in an integer checks all 32 bit positions one at a time — O(32), effectively O(1) but wasteful. Brian Kernighan's algorithm does better by only doing work proportional to the number of set bits: repeatedly clear the lowest set bit with n & (n - 1) until n becomes zero, counting how many clears it took.

// n & (n - 1) always clears exactly the lowest set bit of n.
// Example: n = 0b1011000, n - 1 = 0b1010111, n & (n-1) = 0b1010000
int countSetBits(unsigned int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // drop the lowest set bit
        count++;
    }
    return count;   // O(number of set bits), not O(32)
}

// GCC/Clang also expose a built-in that compiles to a single hardware instruction
// where available -- use it directly in real code, but know how to derive
// countSetBits by hand for an interview.
int countSetBitsBuiltin(unsigned int n) {
    return __builtin_popcount(n);
}

Why does n & (n - 1) clear exactly the lowest set bit? Subtracting 1 flips every trailing zero to a 1 and flips the lowest set bit to a 0; ANDing that with the original n keeps every higher bit unchanged but zeroes out that lowest set bit and all the trailing zeros beneath it, which were already zero.

4. Subset Enumeration via Bitmasking

A set of n elements has exactly 2ᵃ subsets, and every one of them can be represented as an n-bit number: bit i is 1 if element i is included, 0 if it's excluded. That means looping a mask from 0 to (1 << n) - 1 and reading off which bits are set visits every subset exactly once — no recursion required.

#include <vector>
using namespace std;

// Generate the power set of nums (all 2^n subsets) via bitmasking.
// O(2^n * n) time: 2^n masks, O(n) work to build each subset.
vector<vector<int>> powerSet(const vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;

    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {      // is bit i set in this mask?
                subset.push_back(nums[i]);
            }
        }
        result.push_back(subset);
    }
    return result;
}

// Bitmask DP building block you'll reuse starting Week 13: iterate over every
// SUBMASK of a given mask -- useful for "assign these items to groups" DP.
void forEachSubmask(int mask) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        // process sub -- a proper subset (or all) of mask's set bits
    }
    // process 0 separately if the empty submask counts
}

Bitmasking only stays practical while 2ᵃ fits comfortably in an int or long long and finishes within your time limit — in practice that means n up to roughly 20–22 for an O(2ᵃ) enumeration. Beyond that, you need the backtracking-with-pruning approach Week 8 covers instead.

5. Hands-on Exercise

6. Knowledge Check

Four quick questions. Expand each to check your answer.