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)

Low-Level Binary Operations

Imagine a panel of simple light switches. Each switch can only be ON (1) or OFF (0). In computer systems, all data is ultimately boiled down to these binary switches (bits) because transistors only recognize two physical states: current flowing or blocked.

Bit Manipulation is the practice of performing operations directly on these individual bits. It is the fastest possible computation method because it maps directly to hardware instructions.

Core Bitwise Operators:

AND (&): Compares bits and returns 1 only if both inputs are 1.
- Example: 101 & 011 = 001
OR (|): Compares bits and returns 1 if at least one input is 1.
- Example: 101 | 011 = 111
XOR (^): Compares bits and returns 1 only if the inputs are different.
- Example: 101 ^ 011 = 110
NOT (~): Inverts all bits (flips 1 to 0 and vice versa).
- Example: ~101 = ...11010
Left Shift (<<): Shifts bits to the left, filling empty spaces on the right with 0. This effectively multiplies the number by 2 for each shift position.
- Example: 5 << 1 (binary 101 becomes 1010, which is 10).
Right Shift (>>): Shifts bits to the right, discarding truncated bits on the far right. This effectively divides the integer by 2 (rounding down).
- Example: 5 >> 1 (binary 101 becomes 10, which is 2).

C++ Code — Bitwise Operators & Basics

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)

Fast Operations

These bitwise shortcuts bypass standard conditional blocks, offering high performance in low-latency systems:

1. Odd/Even Check

Evaluating if the least significant bit (LSB) is set. Odd numbers always end in 1, while even numbers always end in 0.

Formula: n & 1 (returns 1 if odd, 0 if even).

2. Set Bit

Force the i-th bit to become 1 without altering any other bits.

Formula: n | (1 << i)

3. Unset Bit (Clear Bit)

Force the i-th bit to become 0 without altering any other bits.

Formula: n & ~(1 << i)

4. Toggle Bit

Flip the i-th bit (if it is 1 it becomes 0; if it is 0 it becomes 1).

Formula: n ^ (1 << i)

5. Clear Rightmost Set Bit

Instantly reset the lowest 1 bit to 0. This is a powerful trick used to count set bits or verify binary powers.

Formula: n & (n - 1)

C++ Code — Common Bit Tricks

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)

Binary Power Properties

Integers that represent a power of 2 (e.g., 2, 4, 8, 16, 32) have exactly one 1 bit in their binary format (e.g., 4 is 0100, 8 is 1000).

Power of Two Check (`O(1)` Time)

If you subtract 1 from a power of two, all bits to the right flip (e.g., 8 - 1 = 7, which is 0111). Performing an AND operation between n and n-1 will cancel the lone set bit:

Check: n > 0 && (n & (n - 1)) == 0

Counting Set Bits (Brian Kernighan's Algorithm)

Instead of checking all 32 bits one by one, Brian Kernighan's method jumps directly from set bit to set bit by repeatedly applying n = n & (n - 1) until n becomes 0.

Complexity: Runs in O(k) steps, where k is the exact number of set bits.

C++ Code — Power of 2 & Counting Bits

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)

Properties of Exclusive OR

The XOR (^) operator has unique algebraic properties that make it a favorite in coding interviews:

Self-Cancellation: x ^ x = 0 (XORing a value with itself yields zero).
Identity Element: x ^ 0 = x (XORing any value with zero leaves it unchanged).
Commutative & Associative: The order of operations does not affect the final result.

The Single Number Challenge

Given an array where every integer appears exactly twice except for one unique element, find that unique element.

Solution: XOR all elements in the array. Since order doesn't matter, identical pairs will cancel each other out to 0 (x ^ x = 0), leaving only the single unique value.

In-Place Swapping

You can swap two integers a and b without allocating any temporary helper variable using XOR steps:

a = a ^ b
b = a ^ b
a = a ^ b

C++ Code — XOR Magic: Single Number

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

Subsets (Power Set)

O(N * 2^N)

Bitmask Set Generation

Generating all subsets of a collection (the Power Set) is a classic problem that can be solved elegantly using bitmask counters.

The Binary Correspondence

A set containing n elements generates exactly 2ⁿ subsets. We can map each subset directly to a binary index ranging from 0 to 2ⁿ - 1.

Bitmask Strategy: We run a counter mask from 0 to 2ⁿ - 1.
For each mask, we inspect the j-th bit. If the bit is set (1), we include the j-th element in the current subset.
Example: For nums = [A, B, C], mask 5 (binary 101) represents the subset [A, C].

C++ Code — Subsets (Power Set)

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)

Greedy Bit Construction

Problem: Find the maximum XOR value that can be formed by picking any two numbers from an array.

Greedy Prefix Search (`O(32 * n)` Time)

Instead of comparing every pair (O(n²) brute force), we construct the optimal maximum XOR result bit-by-bit from the most significant bit (MSB) to the least significant bit (LSB):

We maintain a prefix mask to inspect only the leading bits.
For each bit position i, we record all prefixes in a Hash Set.
We greedily check if we can achieve a 1 at the current bit position. We assume a target maximum candidate: greedyTry = currentMax | (1 << i).
Using the XOR property (if A ^ B = C, then A ^ C = B), we check if there exists a prefix in our set such that prefix ^ greedyTry is also present in the set. If true, we update our maximum.

C++ Code — Advanced: Maximum XOR

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;
}

Low-Level Binary Operations

Bit Manipulation is the practice of performing operations directly on these individual bits. It is the fastest possible computation method because it maps directly to hardware instructions.

Core Bitwise Operators:

AND (&): Compares bits and returns 1 only if both inputs are 1.
- Example: 101 & 011 = 001
OR (|): Compares bits and returns 1 if at least one input is 1.
- Example: 101 | 011 = 111
XOR (^): Compares bits and returns 1 only if the inputs are different.
- Example: 101 ^ 011 = 110
NOT (~): Inverts all bits (flips 1 to 0 and vice versa).
- Example: ~101 = ...11010
Left Shift (<<): Shifts bits to the left, filling empty spaces on the right with 0. This effectively multiplies the number by 2 for each shift position.
- Example: 5 << 1 (binary 101 becomes 1010, which is 10).
Right Shift (>>): Shifts bits to the right, discarding truncated bits on the far right. This effectively divides the integer by 2 (rounding down).
- Example: 5 >> 1 (binary 101 becomes 10, which is 2).

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; }

Bit Manipulation

Bitwise Operators & Basics

Low-Level Binary Operations

Core Bitwise Operators:

Common Bit Tricks

Fast Operations

1. Odd/Even Check

2. Set Bit

3. Unset Bit (Clear Bit)

4. Toggle Bit

5. Clear Rightmost Set Bit

Power of 2 & Counting Bits

Binary Power Properties

Power of Two Check (O(1) Time)

Counting Set Bits (Brian Kernighan's Algorithm)

XOR Magic: Single Number

Properties of Exclusive OR

The Single Number Challenge

In-Place Swapping

Subsets (Power Set)

Bitmask Set Generation

The Binary Correspondence

Advanced: Maximum XOR

Greedy Bit Construction

Greedy Prefix Search (O(32 * n) Time)

Bit Manipulation

Bitwise Operators & Basics

Low-Level Binary Operations

Core Bitwise Operators:

Common Bit Tricks

Fast Operations

1. Odd/Even Check

2. Set Bit

3. Unset Bit (Clear Bit)

4. Toggle Bit

5. Clear Rightmost Set Bit

Power of 2 & Counting Bits

Binary Power Properties

Power of Two Check (O(1) Time)

Counting Set Bits (Brian Kernighan's Algorithm)

XOR Magic: Single Number

Properties of Exclusive OR

The Single Number Challenge

In-Place Swapping

Subsets (Power Set)

Bitmask Set Generation

The Binary Correspondence

Advanced: Maximum XOR

Greedy Bit Construction

Greedy Prefix Search (O(32 * n) Time)

Power of Two Check (`O(1)` Time)

Greedy Prefix Search (`O(32 * n)` Time)

Power of Two Check (`O(1)` Time)

Greedy Prefix Search (`O(32 * n)` Time)