Skip to main content

Bit Operations

Basic bit operations, shifting, masking, and common bit manipulation tricks

Master the fundamental bit operations and techniques used in competitive programming, systems design, and performance-critical applications.

TL;DR​

Bit operations are fundamental for performance optimization, flags/permissions, and solving tricky algorithm problems. Master AND, OR, XOR, shifts, and masking. These operations run in constant time (O(1)) and enable elegant solutions to subset/state problems. Use bitmasks to represent sets compactly, bit tricks to find unique elements, and shifts for fast multiplication/division.

Learning Objectives​

  • Understand all bitwise operations and their applications
  • Use bit masks for efficient flag representation
  • Apply bit tricks to solve common algorithm problems
  • Optimize performance using bit operations
  • Recognize when bit manipulation is the right approach

Basic Bit Operations​

AND (&)​

  • Purpose: Bitwise AND operation
  • Result: 1 only if both bits are 1
  • Common uses: Masking, checking if bit is set, clearing bits
  • Example: 5 & 3 = 1 (101 & 011 = 001)
  • Real-world: Check file permissions, extract bit ranges

OR (|)​

  • Purpose: Bitwise OR operation
  • Result: 1 if at least one bit is 1
  • Common uses: Setting bits, combining flags
  • Example: 5 | 3 = 7 (101 | 011 = 111)
  • Real-world: Combine multiple permission flags into one integer

XOR (^)​

  • Purpose: Bitwise XOR (exclusive OR) operation
  • Result: 1 if bits are different
  • Common uses: Toggling bits, finding unique elements, checksums
  • Example: 5 ^ 3 = 6 (101 ^ 011 = 110)
  • Real-world: Detect changes, error detection, encryption (one-time pad)

NOT (~)​

  • Purpose: Bitwise NOT (complement) operation
  • Result: Flips all bits
  • Common uses: Creating masks, bit inversion
  • Example: ~5 = -6 (in 32-bit: ~000...101 = 111...010)
  • Important: Depends on integer width; watch for sign extension

Bit Shifting​

Left Shift (<<)​

  • Purpose: Shifts bits to the left, fills right with zeros
  • Effect: Multiplies by 2^n (very fast)
  • Example: 5 << 2 = 20 (101 becomes 10100)
  • Use cases: Fast multiplication, creating masks, iterating through bits

Right Shift (>>)​

  • Purpose: Shifts bits to the right
  • Effect: Divides by 2^n (integer division)
  • Example: 20 >> 2 = 5 (10100 becomes 101)
  • Use cases: Fast division, extracting bits, isolating bit ranges

Arithmetic vs Logical Right Shift​

  • Arithmetic (>>>): Preserves sign bit (signed integers) — fills left with sign bit
  • Logical (>>): Fills with zeros (unsigned integers) — standard in most languages
  • Note: C++ and Python default to arithmetic for signed types

Bit Masking Techniques​

// Setting a bit at position i
num |= (1 << i);

// Clearing a bit at position i
num &= ~(1 << i);

// Toggling a bit at position i
num ^= (1 << i);

// Checking if bit at position i is set
bool isSet = (num & (1 << i)) != 0;

// Getting the last set bit (rightmost)
int lastBit = num & -num;

// Clearing the last set bit
num &= (num - 1);

// Example: Check if bit 3 is set in number 13 (1101 in binary)
int n = 13;  // 1101
bool bit3 = (n & (1 << 3)) != 0;  // 1101 & 1000 = 1000, so true

Bit Counting and Analysis​

Count Set Bits (Population Count)​

// Method 1: Simple loop (O(k) where k = number of set bits)
int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// Method 2: Brian Kernighan's algorithm (O(k), faster in practice)
// Clears rightmost set bit each iteration
int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // Clear rightmost set bit
        count++;
    }
    return count;
}

// Method 3: Built-in function (usually hardware-accelerated)
int count = __builtin_popcount(n);      // 32-bit
int count = __builtin_popcountll(n);    // 64-bit

// Example:
// n = 13 (1101)
// Iteration 1: 1101 & 1100 = 1100, count = 1
// Iteration 2: 1100 & 1011 = 1000, count = 2
// Iteration 3: 1000 & 0111 = 0000, count = 3
// Result: 3 set bits (correct!)

Common Bit Manipulation Tricks​

Power of 2 Check​

// A power of 2 has exactly one bit set
// n & (n-1) clears the rightmost set bit
// If result is 0, n was a power of 2
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// Examples:
// 8 (1000): 8 & 7 = 1000 & 0111 = 0000 → true
// 6 (0110): 6 & 5 = 0110 & 0101 = 0100 → false

Get Rightmost Set Bit​

// Isolate the rightmost set bit
int rightmost = n & (-n);

// Why it works:
// -n in two's complement: flip all bits + 1
// n = 12 (01100), -n = -12 (10100 in two's complement)
// n & (-n) = 01100 & 10100 = 00100 (4, the rightmost set bit)

Remove Rightmost Set Bit​

// Clear the rightmost set bit
n &= (n - 1);

// Used in: counting set bits, power of 2 check, subset enumeration
// n = 12 (1100), n-1 = 11 (1011)
// 1100 & 1011 = 1000 (result is 8)

Check if Number is Subset of Another​

// Check if a is a subset of b (all bits in a are also in b)
bool isSubset(int a, int b) {
    return (a & b) == a;
}

// Examples:
// a = 5 (0101), b = 13 (1101)
// 5 & 13 = 0101 & 1101 = 0101 = 5 → true (5 is subset of 13)
// a = 6 (0110), b = 13 (1101)
// 6 & 13 = 0110 & 1101 = 0100 ≠ 6 → false

Swap Without Temporary Variable​

// Using XOR (works for both integers and pointers)
a ^= b;
b ^= a;
a ^= b;

// Or more concise:
a ^= b ^= a ^= b;

// Why it works:
// After a ^= b: a = a^b, b = b
// After b ^= a: b = b^(a^b) = a, a = a^b
// After a ^= b: a = (a^b)^a = b, b = a

Absolute Value Without Branching​

// For 32-bit signed integers
int absolute(int n) {
    int mask = n >> 31;  // All 0s if n >= 0, all 1s if n < 0
    return (n + mask) ^ mask;
}

// Alternative method (often faster)
int absolute(int n) {
    return (n ^ (n >> 31)) - (n >> 31);
}

// Examples:
// n = 5: mask = 0, (5+0)^0 = 5
// n = -5: mask = -1, (-5-1)^-1 = (-6)^(-1) = 5

Bit Manipulation in Array Problems​

// 1. Find Missing Number in array [1..n]
int findMissing(vector<int> arr) {
    int result = 0;
    for (int i = 0; i < arr.size(); i++) {
        result ^= arr[i] ^ (i + 1);
    }
    return result ^ arr.size();
}

// 2. Find Single Number (all others appear twice)
int findSingle(vector<int> arr) {
    int result = 0;
    for (int num : arr) {
        result ^= num;  // Duplicates cancel out
    }
    return result;
}

// 3. Find Two Single Numbers (all others appear twice)
int findTwoSingle(vector<int> arr) {
    int xorAll = 0;
    for (int num : arr) xorAll ^= num;
    
    // Find any set bit (rightmost)
    int setBit = xorAll & (-xorAll);
    
    int num1 = 0, num2 = 0;
    for (int num : arr) {
        if (num & setBit) num1 ^= num;
        else num2 ^= num;
    }
    return num1;  // or num2
}

// 4. Count set bits in all numbers 1 to n
int countSetBits(int n) {
    int count = 0;
    int powerOf2 = 1;
    
    while (powerOf2 <= n) {
        // Pairs of (0s, 1s)
        int pairsCount = (n + 1) / (powerOf2 * 2);
        count += pairsCount * powerOf2;
        
        // Remaining bits
        int remainder = (n + 1) % (powerOf2 * 2);
        if (remainder > powerOf2) {
            count += remainder - powerOf2;
        }
        
        powerOf2 *= 2;
    }
    return count;
}

Advanced Patterns: Dynamic Programming with Bitmask​

// Traveling Salesman Problem (TSP) using bitmask DP
// dp[mask][i] = minimum cost to visit cities in mask, ending at city i

vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
dp[1][0] = 0;  // Start at city 0

for (int mask = 1; mask < (1 << n); mask++) {
    for (int u = 0; u < n; u++) {
        if (!(mask & (1 << u))) continue;  // City u not in mask
        if (dp[mask][u] == INT_MAX) continue;
        
        for (int v = 0; v < n; v++) {
            if (mask & (1 << v)) continue;  // City v already visited
            
            int newMask = mask | (1 << v);
            dp[newMask][v] = min(dp[newMask][v], 
                                  dp[mask][u] + cost[u][v]);
        }
    }
}

// Find minimum cost to visit all cities and return to start
int result = INT_MAX;
for (int i = 0; i < n; i++) {
    result = min(result, dp[(1 << n) - 1][i] + cost[i][0]);
}

Performance Comparison​

// Bit operation vs alternatives (approximate timings on modern CPU)
// Operation              | Time (ns)
// n & (1 << i)          | 0.5-1
// n & ~(1 << i)         | 0.5-1
// n << 1                | 0.5-1 (much faster than n * 2)
// n >> 1                | 0.5-1 (much faster than n / 2)
// __builtin_popcount(n) | 1-2 (hardware-accelerated via POPCNT)
// __builtin_clz(n)      | 1-2 (hardware-accelerated)

// Optimization tip: Use built-in functions when available
// They map to CPU instructions (POPCNT, CLZ, CTZ on modern x86/ARM)

Common Mistakes and Pitfalls​

  • Sign extension with right shift: Arithmetic right shift (>>) on signed types fills with sign bit, not zero. Use unsigned types or logical shift.
  • Forgetting operator precedence: n & 1 << i is n & (1 << i) ✓, not (n & 1) << i ✗
  • Off-by-one in bit positions: Bit positions are 0-indexed. Bit i is at position i (value 2^i).
  • Overflow in shifts: shifting by 32 on a 32-bit int is undefined behavior. Use 64-bit integers for large shifts.
  • Assuming shift fills with specific value: Right shift behavior depends on signedness.
  • Not checking for negative numbers in bit tricks: Many tricks assume non-negative integers.

Decision Tree: When to Use Bit Operations​

Problem involves:
├─ Flags/Permissions? → Use bitmask (compact, O(1) operations)
├─ Finding duplicates in array? → Try XOR (elegant, O(1) space)
├─ Subset generation? → Use bitmask + iteration (2^n subsets)
├─ Performance critical? → Consider bit shifts (faster than *, /)
├─ State compression in DP? → Bitmask DP (TSP, subset sum)
├─ Character/bit counting? → Use __builtin_popcount, clz, ctz
└─ Set operations (union, intersection)? → Use bitwise AND, OR, XOR

Self-Check​

  • What is the difference between arithmetic and logical right shift?
  • How does XOR solve the "find single number" problem?
  • Why does n & (n-1) clear the rightmost set bit?
  • When would you use bitmask instead of a boolean array?
  • How do you extract bits from position i to j?
info

Bit operations are O(1), deterministic, and enable elegant solutions to algorithm problems. Master them for interviews and performance-critical code.

One Takeaway​

Bit operations enable elegant, O(1) solutions to many algorithm problems. Master masking, shifting, and common tricks like power-of-2 check and finding unique elements. Use built-in functions for counting/analyzing bits.

Next Steps​

  • Practice bit manipulation problems on LeetCode (bit-manipulation tag)
  • Study bitmask DP for combinatorial optimization
  • Explore bitwise algorithms in cryptography and compression
  • Learn about SIMD (Single Instruction Multiple Data) for parallel bit operations

References​

  • "Bit Twiddling Hacks" by Sean Eron Anderson
  • "Hackers Delight" by Henry Warren
  • NIST Fundamentals of Bit Operations
  • Competitive Programming: Halim & Halim