CATEGORY 10 OF 13

Bit Manipulation Basics

Master the fundamental bitwise operators (AND, OR, XOR, NOT, shifts) and learn to check, set, clear, and toggle individual bits, apply bit masking, and use classic tricks like n & (n-1) and XOR cancellation.

Time: O(1) for single bit operations, O(k) for k-bit numbers

Space: O(1)

Learn & Reference

Understanding the Pattern

Bit Manipulation Basics

At the hardware level, all data is stored as sequences of bits (0s and 1s). Bitwise operations manipulate these bits directly, giving you constant-time tricks that bypass arithmetic overhead. Many interview problems have elegant bit-manipulation solutions that are faster and use less memory than their arithmetic counterparts.

Bitwise Operators

Every language provides the same core set of bitwise operators:

| Operator | Symbol | Description | |----------|--------|-------------| | AND | & | 1 only when both bits are 1 | | OR | \| | 1 when at least one bit is 1 | | XOR | ^ | 1 when bits differ | | NOT | ~ | Flips every bit (bitwise complement) | | Left Shift | << | Shifts bits left, fills with 0s (multiply by 2) | | Right Shift | >> | Shifts bits right (divide by 2, arithmetic shift preserves sign) |

  1 0 1 1  (11)          1 0 1 1  (11)          1 0 1 1  (11)
& 1 1 0 1  (13)        | 1 1 0 1  (13)        ^ 1 1 0 1  (13)
---------             ---------             ---------
  1 0 0 1  (9)           1 1 1 1  (15)          0 1 1 0  (6)

Bit Masking

A mask is an integer whose binary representation isolates specific bits. Common masks:

1 << k — a single 1-bit at position k (0-indexed from the right)
(1 << k) - 1 — all 1s in the lowest k positions
~0 or -1 — all bits set to 1

Checking, Setting, Clearing, and Toggling Bits

These four operations form the foundation of bit manipulation:

Check bit k:    (n >> k) & 1          — returns 0 or 1
Set bit k:      n | (1 << k)          — forces bit k to 1
Clear bit k:    n & ~(1 << k)         — forces bit k to 0
Toggle bit k:   n ^ (1 << k)          — flips bit k

Essential Tricks

n & (n - 1): Clear the Lowest Set Bit

Subtracting 1 from n flips the lowest set bit and all bits below it. ANDing with n clears just that lowest set bit:

n     = 1 0 1 0 0 0  (40)
n - 1 = 1 0 0 1 1 1  (39)
n & (n-1) = 1 0 0 0 0 0  (32)   — lowest set bit cleared

Applications: counting set bits (Brian Kernighan's algorithm), checking power of two (n & (n-1) == 0).

n & (-n): Isolate the Lowest Set Bit

In two's complement, -n flips all bits of n and adds 1. ANDing gives you only the lowest set bit:

n      = 1 0 1 0 0 0  (40)
-n     = 0 1 1 0 0 0  (in two's complement)
n & -n = 0 0 1 0 0 0  (8)   — lowest set bit isolated

XOR Properties

XOR has three critical properties:

Self-cancellation: a ^ a = 0
Identity: a ^ 0 = a
Commutativity/Associativity: order doesn't matter

These let you find the single unique element in a list of pairs by XOR-ing everything together.

XOR Swap

You can swap two values without a temporary variable:

a = a ^ b
b = a ^ b    // now b = original a
a = a ^ b    // now a = original b

Two's Complement Basics

Most languages represent negative integers using two's complement:

Positive n: standard binary
Negative n: invert all bits of |n|, then add 1
The most significant bit (MSB) is the sign bit (1 = negative)
Range for k bits: -2^(k-1) to 2^(k-1) - 1

 5 in 8-bit: 0000 0101
-5 in 8-bit: 1111 1011  (invert: 1111 1010, add 1: 1111 1011)

Python caveat: Python integers have arbitrary precision (no fixed bit width), so bitwise NOT and negative number operations require explicit masking to simulate 32-bit behavior.

Common Mistakes

Confusing logical and bitwise operators: &&/|| are logical (short-circuit), &/| are bitwise. In Python, and/or are logical, while &/| are bitwise
Operator precedence: Bitwise operators have lower precedence than comparison operators in most languages. n & 1 == 0 is parsed as n & (1 == 0). Always use parentheses: (n & 1) == 0
Signed right shift vs unsigned right shift: In Java, >> is arithmetic (preserves sign), >>> is logical (fills with 0s). JavaScript has both. Python only has >> (arithmetic)
Python arbitrary precision: Python integers are not fixed-width, so ~n gives -(n+1), not a 32-bit complement. Use n ^ 0xFFFFFFFF to simulate 32-bit NOT
Off-by-one in bit positions: Bit positions are 0-indexed from the right. Bit 0 is the least significant bit (rightmost)
Forgetting edge case n = 0: Many bit tricks behave differently when n is 0. Always test with 0
Integer overflow with left shift: Shifting a large number left can overflow in fixed-width languages (Java, Go, C). Check bounds before shifting

When to Use

Check if a number is even or odd (n & 1)

Determine if a number is a power of two

Count the number of set bits (1s) in a binary representation

Find the single element that appears once when all others appear twice

Swap two values without a temporary variable

Toggle or flip specific bits in a number

Work with flags, permissions, or feature toggles stored as bit fields

Optimize arithmetic operations (multiply/divide by powers of 2)

Problems that mention binary representation or XOR

Find a missing number in a sequence

Template

1# --- Count Set Bits (Brian Kernighan's Algorithm) ---
2def count_set_bits(n):
3    """Count the number of 1-bits in n"""
4    count = 0
5    while n:
6        n &= n - 1   # clear the lowest set bit
7        count += 1
8    return count
9
10# --- Check / Set / Clear / Toggle Bit ---
11def get_bit(n, k):
12    """Return the value of bit k (0 or 1)"""
13    return (n >> k) & 1
14
15def set_bit(n, k):
16    """Set bit k to 1"""
17    return n | (1 << k)
18
19def clear_bit(n, k):
20    """Clear bit k to 0"""
21    return n & ~(1 << k)
22
23def toggle_bit(n, k):
24    """Flip bit k"""
25    return n ^ (1 << k)
26
27# --- XOR Trick: Find Single Number ---
28def find_single(nums):
29    """All elements appear twice except one — find it"""
30    result = 0
31    for num in nums:
32        result ^= num
33    return result

{ }

Syntax Reference

1# === Bitwise Operators ===
2a & b          # AND
3a | b          # OR
4a ^ b          # XOR
5~a             # NOT (bitwise complement, gives -(a+1))
6a << k         # Left shift by k positions
7a >> k         # Right shift by k positions (arithmetic)
8
9# === Built-in Helpers ===
10bin(n)         # Binary string: bin(10) -> '0b1010'
11n.bit_length() # Number of bits needed: (10).bit_length() -> 4
12int('1010', 2) # Parse binary string to int -> 10
13
14# === Check / Set / Clear / Toggle Bit k ===
15(n >> k) & 1           # Check bit k (0 or 1)
16n | (1 << k)           # Set bit k to 1
17n & ~(1 << k)          # Clear bit k to 0
18n ^ (1 << k)           # Toggle bit k
19
20# === Common Tricks ===
21n & (n - 1)            # Clear lowest set bit
22n & (-n)               # Isolate lowest set bit
23n & 1                  # Check if odd (1) or even (0)
24
25# === 32-bit Masking (for Python) ===
26mask = 0xFFFFFFFF
27n & mask               # Treat as unsigned 32-bit

📋

Common Recipes

1# --- Count Set Bits (Brian Kernighan) ---
2def count_bits(n):
3    count = 0
4    while n:
5        n &= n - 1   # clear lowest set bit
6        count += 1
7    return count
8
9# --- Check Power of Two ---
10def is_power_of_two(n):
11    return n > 0 and (n & (n - 1)) == 0
12
13# --- Single Number (XOR all) ---
14def single_number(nums):
15    result = 0
16    for num in nums:
17        result ^= num
18    return result
19
20# --- Reverse Bits (32-bit) ---
21def reverse_bits(n):
22    result = 0
23    for _ in range(32):
24        result = (result << 1) | (n & 1)
25        n >>= 1
26    return result
27
28# --- Swap Without Temp ---
29def swap(a, b):
30    a ^= b
31    b ^= a
32    a ^= b
33    return a, b
34
35# --- Get / Set / Clear / Toggle ---
36def get_bit(n, k):   return (n >> k) & 1
37def set_bit(n, k):   return n | (1 << k)
38def clear_bit(n, k): return n & ~(1 << k)
39def toggle_bit(n, k): return n ^ (1 << k)

O(n)

Complexity

Operation	Time	Notes
AND / OR / XOR / NOT	O(1)	Single CPU instruction on fixed-width integers
Left / Right Shift	O(1)	Equivalent to multiply/divide by 2^k
Check / Set / Clear / Toggle bit	O(1)	Single shift + single bitwise op
Count set bits (Kernighan)	O(k)	k = number of set bits, at most O(log n)
Count set bits (built-in)	O(1)	Hardware popcount instruction
n & (n-1)	O(1)	Clears lowest set bit
n & (-n)	O(1)	Isolates lowest set bit
Reverse bits (loop)	O(32)	32 iterations for 32-bit integer
XOR all elements	O(n)	Linear scan of n elements

Watch Out

✗Confusing logical and bitwise operators: `&&`/`||` are logical (short-circuit), `&`/`|` are bitwise. In Python, `and`/`or` are logical, while `&`/`|` are bitwise
✗Operator precedence: Bitwise operators have lower precedence than comparison operators in most languages. `n & 1 == 0` is parsed as `n & (1 == 0)`. Always use parentheses: `(n & 1) == 0`
✗Signed right shift vs unsigned right shift: In Java, `>>` is arithmetic (preserves sign), `>>>` is logical (fills with 0s). JavaScript has both. Python only has `>>` (arithmetic)
✗Python arbitrary precision: Python integers are not fixed-width, so `~n` gives `-(n+1)`, not a 32-bit complement. Use `n ^ 0xFFFFFFFF` to simulate 32-bit NOT
✗Off-by-one in bit positions: Bit positions are 0-indexed from the right. Bit 0 is the least significant bit (rightmost)
✗Forgetting edge case n = 0: Many bit tricks behave differently when n is 0. Always test with 0
✗Integer overflow with left shift: Shifting a large number left can overflow in fixed-width languages (Java, Go, C). Check bounds before shifting

PRACTICE PROBLEMS

Matrix / 2D Basics

Edge Cases & Parsing