DSA: Bit Manipulation Algorithms

Bit manipulation is about directly operating on binary digits (bits) of numbers.

Instead of thinking in decimal (13, 42), you think in binary (1101, 101010) and use CPU-level operations that are extremely fast.

Modern CPUs are _bit machines_. Using bits correctly often turns a slow solution into a constant-time one.

Why Bit Manipulation Matters

  • Fastest operations you can perform (hardware-level)
  • Reduces memory usage
  • Common in low-level, embedded, cryptography, systems, and interview problems
  • Many “tricky” problems become trivial with bits

md 
Decimal: 13
Binary : 1101

Position: 3 2 1 0
Bits    : 1 1 0 1
Value   : 8 4 0 1

Each bit represents a power of two.

Core Bitwise Operators

AND (`&`)

Sets bit to 1 only if both bits are 1

md 
5  = 0101
3  = 0011
-----------
&  = 0001  -> 1

  • Check if a bit is set
  • Mask bits

Time Complexity: O(1)

OR (`|`)

Sets bit to 1 if any bit is 1

md 
5  = 0101
3  = 0011
-----------
|  = 0111 -> 7

  • Set a bit
  • Combine flags

Time Complexity: O(1)

NOT (`~`)

Flips all bits

md 
5  = 00000101
~5 = 11111010  (two’s complement → negative)

  • Bit inversion
  • Masks

XOR (`^`)

Sets bit to 1 if bits are different

md 
5  = 0101
3  = 0011
-----------
^  = 0110 -> 6

  • Find unique number
  • Swap numbers without temp variable

Time Complexity: O(1)

x ^ x = 0, x ^ 0 = x

Bit Shifting

Left Shift (`<<`)

Multiplies by 2

md 
x << k = x * 2^k

md 
3 << 1 = 6
0011 << 1 = 0110

Right Shift (`>>`)

Divides by 2

md 
x >> k = x / 2^k

md 
8 >> 1 = 4
1000 >> 1 = 0100

Bit Masking

Used to store multiple boolean states in one integer

md 
Bit mask: 00010100
Meaning : flags at position 2 and 4 are ON

md 
Set a bit:
mask |= (1 << k)

Clear a bit
mask &= ~(1 << k)

Toggle a bit
mask ^= (1 << k)

Check a bit
mask & (1 << k)

Bit Tricks

Check if a number is even or odd

md 
n & 1

`1` → odd
`0` → even

Check if a number is power of two

md 
n > 0 && (n & (n - 1)) == 0

Example

8  = 1000
7  = 0111
&  = 0000

Count set bits (Brian Kernighan’s Algorithm)

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

Each operation removes **one set bit**

**Time Complexity:** `O(number of set bits)`  
Worst case: `O(log n)`

Find the single number (all others appear twice)

md 
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int n : nums)
        result ^= n;
    return result;
}


Why:
x ^ x = 0
0 ^ y = y

Time: O(n)

Space: O(1)