W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Bit Manipulation

Master bitwise operators, masks, and low-level optimizations.

Topics

Minutes

O(1)

Tricks

Bitwise Operators & Basics

O(1)

Bit Manipulation works directly on binary digits (0 and 1). It's crucial for optimizing time and space.

Core Operators:
- AND (&): Both bits must be 1. (e.g. 101 & 011 = 001)
- OR (|): At least one bit is 1. (e.g. 101 | 011 = 111)
- XOR (^): Bits must be different. (e.g. 101 ^ 011 = 110)
- NOT (~): Inverts bits. (e.g. ~101 = ...11010)
- Left Shift (<<): Multiply by 2. 5 << 1 → 10.
- Right Shift (>>): Divide by 2. 5 >> 1 → 2.

Why Binary? Computers use transistors (ON/OFF), making binary the native language of hardware.

C++ Code

int a = 5, b = 3;
cout << (a & b); // 1
cout << (a | b); // 7
cout << (a ^ b); // 6
cout << (~a);    // -6
cout << (a << 1); // 10
cout << (a >> 1); // 2

Common Bit Tricks

O(1)

Essential patterns for competitive programming:

1. Check Odd/Even: if (n & 1) checks the last bit. (0=Even, 1=Odd).
2. Set Bit: n | (1 << i) forces the i-th bit to 1.
3. Unset Bit: n & ~(1 << i) forces the i-th bit to 0.
4. Toggle Bit: n ^ (1 << i) flips the i-th bit.
5. Clear Last Set Bit: n & (n - 1) removes the rightmost 1. Used in Popcount.

C++ Code

bool isOdd(int n) { return n & 1; }
int setBit(int n, int i) { return n | (1 << i); }
int clearBit(int n, int i) { return n & ~(1 << i); }
int toggleBit(int n, int i) { return n ^ (1 << i); }

Power of 2 & Counting Bits

O(No. of set bits)

Check Power of 2:
Powers of 2 have exactly one '1' bit (e.g., 4=100, 8=1000).
Trick: n > 0 && (n & (n - 1)) == 0

Count Set Bits (Brian Kernighan's Algo):
Repeat n = n & (n - 1) until n is 0. This loop runs only as many times as there are set bits (much faster than looping 32 times).

C++ Code

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

int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

XOR Magic: Single Number

O(N)

Property: x ^ x = 0 and x ^ 0 = x.

Problem 1: Single Number
Array where every element appears twice except one.
Solution: XOR all numbers. Duplicates cancel out 0, leaving the unique number.

Problem 2: Simple Swap
Swap two numbers without a temp variable:
a = a ^ b, b = a ^ b, a = a ^ b

C++ Code

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int x : nums) res ^= x;
    return res;
}

Subsets (Power Set)

O(N * 2^N)

Generate all subsets of a set using a Mask.
For size N, there are 2^N subsets, corresponding to binary numbers from 0 to 2^N - 1.

Logic:
If the j-th bit of loop counter mask is set, include arr[j] in the current subset.

C++ Code

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> res;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> sub;
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) {
                sub.push_back(nums[j]);
            }
        }
        res.push_back(sub);
    }
    return res;
}

Advanced: Maximum XOR

O(32 * N)

Problem: Find max XOR of any two elements in an array.

Greedy Strategy:
Build the answer bit by bit from MSB to LSB.
For each bit, assume it can be 1. Check if there exists a pair in the array (using a Set/HashSet of prefixes) that produces this bit.
Target = CurrentMax | (1 << i)
If Prefix ^ Target exists in set, then this bit is possible!

C++ Code

int findMaximumXOR(vector<int>& nums) {
    int maxResult = 0, mask = 0;
    for (int i = 31; i >= 0; i--) {
        mask = mask | (1 << i);
        unordered_set<int> prefixes;
        for (int num : nums) prefixes.insert(num & mask);
        
        int greedyTry = maxResult | (1 << i);
        for (int prefix : prefixes) {
            if (prefixes.count(greedyTry ^ prefix)) {
                maxResult = greedyTry;
                break;
            }
        }
    }
    return maxResult;
}

bool isPowerOfTwo(int n) { return n > 0 && ((n & (n - 1)) == 0); } int countSetBits(int n) { int count = 0; while (n > 0) { n = n & (n - 1); count++; } return count; }

vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); vector<vector<int>> res; for (int mask = 0; mask < (1 << n); mask++) { vector<int> sub; for (int j = 0; j < n; j++) { if (mask & (1 << j)) { sub.push_back(nums[j]); } } res.push_back(sub); } return res; }

int findMaximumXOR(vector<int>& nums) { int maxResult = 0, mask = 0; for (int i = 31; i >= 0; i--) { mask = mask | (1 << i); unordered_set<int> prefixes; for (int num : nums) prefixes.insert(num & mask); int greedyTry = maxResult | (1 << i); for (int prefix : prefixes) { if (prefixes.count(greedyTry ^ prefix)) { maxResult = greedyTry; break; } } } return maxResult; }