Skip to main content

Bit Operations

Master the fundamental bit operations and techniques used in competitive programming and system design.

Basic Bit Operations​

AND (&)​

  • Purpose: Bitwise AND operation
  • Result: 1 only if both bits are 1
  • Common uses: Masking, checking if bit is set
  • Example: 5 & 3 = 1 (101 & 011 = 001)

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)

XOR (^)​

  • Purpose: Bitwise XOR (exclusive OR) operation
  • Result: 1 if bits are different
  • Common uses: Toggling bits, finding unique elements
  • Example: 5 ^ 3 = 6 (101 ^ 011 = 110)

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)

Bit Shifting​

Left Shift (<<)​

  • Purpose: Shifts bits to the left
  • Effect: Multiplies by 2^n
  • Example: 5 << 2 = 20 (101 becomes 10100)
  • Use cases: Fast multiplication, creating masks

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

Arithmetic vs Logical Right Shift​

  • Arithmetic: Preserves sign bit (signed integers)
  • Logical: Fills with zeros (unsigned integers)

Bit Masking​

Setting Bits​

// Set bit at position i
num |= (1 `<<` i);

Clearing Bits​

// Clear bit at position i
num &= ~(1 `<<` i);

Toggling Bits​

// Toggle bit at position i
num ^= (1 `<<` i);

Checking Bits​

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

Bit Counting​

Count Set Bits (Population Count)​

// Method 1: Loop through bits
int count = 0;
while (n) {
    count += n & 1;
    n >>= 1;
}

// Method 2: Brian Kernighan's algorithm
int count = 0;
while (n) {
    n &= (n - 1);
    count++;
}

Count Leading/Trailing Zeros​

  • Leading zeros: Number of zeros before the first 1
  • Trailing zeros: Number of zeros after the last 1
  • Built-in functions: __builtin_clz(), __builtin_ctz()

Common Bit Manipulation Tricks​

Power of 2 Check​

// Check if n is a power of 2
bool isPowerOfTwo = (n & (n - 1)) == 0;

Get Rightmost Set Bit​

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

Remove Rightmost Set Bit​

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

Swap Without Temporary Variable​

// Swap two numbers using XOR
a ^= b;
b ^= a;
a ^= b;

Absolute Value​

// Get absolute value without branching
int abs = (n + (n `>>` 31)) ^ (n `>>` 31);

Bit Manipulation in Arrays​

Finding Missing Number​

  • Problem: Array of n-1 numbers from 1 to n, find missing
  • Solution: XOR all numbers with 1 to n

Finding Single Number​

  • Problem: Array where every number appears twice except one
  • Solution: XOR all numbers

Finding Two Single Numbers​

  • Problem: Array where every number appears twice except two
  • Solution: XOR to get difference, then separate groups

Bit Manipulation in Strings​

Character to Bit Position​

// Convert character to bit position
int bitPos = c - 'a';  // for lowercase letters

Check if All Characters Unique​

// Using bitmask to check uniqueness
int mask = 0;
for (char c : str) {
    int bit = 1 `<<` (c - 'a');
    if (mask & bit) return false;
    mask |= bit;
}

Performance Tips​

  1. Use bitwise operations for faster arithmetic
  2. Prefer bitmasks over boolean arrays for small sets
  3. Use built-in functions when available
  4. Be careful with signed integers and right shifts
  5. Consider endianness in multi-byte operations

Common Patterns​

  • Subset generation: Use bitmasks to represent subsets
  • State compression: Use bits to represent states
  • Flag combinations: Use OR to combine multiple flags
  • Bit manipulation in DP: Use bits to represent visited states