Module 13 : Bit Manipulation

Bit manipulation is the art of solving problems by operating directly on the binary representation of numbers.
It is fast, memory-efficient, and frequently tested in top product company interviews.

If a problem involves:

• parity
• toggling
• uniqueness
• subsets
• powers of two

Think in bits.

---

Binary Representation

Every integer is stored in binary (base-2).

Example:

Decimal 5  →  101
Decimal 10 →  1010
Decimal 12 →  1100

Each position represents a power of 2.

---

Signed Integers (Concept)

Most languages use 2’s complement:

• Positive numbers → normal binary
• Negative numbers → invert bits + add 1

Understanding this helps with edge cases.

---

Bitwise Operators

AND (&)

1 & 1 = 1
1 & 0 = 0

Used for:

• Checking bits
• Masking

Example:

if((x & 1) == 1) // odd number

---

OR (|)

1 | 0 = 1

Used for:

• Setting bits

x = x | (1 << i);

---

XOR (^)

1 ^ 1 = 0
1 ^ 0 = 1

Key property:

Same bits cancel each other

a ^ a = 0
a ^ 0 = a

---

NOT (~)

Flips all bits.

~5 → -(5+1) = -6

---

Left Shift (<<)

Multiply by powers of 2.

5 << 1 → 10

---

Right Shift (>>)

Divide by powers of 2.

10 >> 1 → 5

---

XOR Properties (Very Important)

XOR is associative and commutative.

a ^ b ^ a = b

Used heavily in:

• Single number problems
• Swapping without temp
• Difference detection

---

Single Number Problems

Problem 1

Every number appears twice except one.

int ans = 0;
for(int x : arr)
    ans ^= x;

Why it works:

• Duplicates cancel out
• Unique remains

Time: O(n)
Space: O(1)

---

Problem 2

Every number appears three times except one.

Approach:

• Count bits at each position
• Modulo 3

int result = 0;
for(int i = 0; i < 32; i++){
    int sum = 0;
    for(int x : arr){
        if((x & (1 << i)) != 0)
            sum++;
    }
    if(sum % 3 != 0)
        result |= (1 << i);
}

---

Counting Set Bits

Brian Kernighan’s Algorithm

Each iteration removes the lowest set bit.

int count = 0;
while(n > 0){
    n = n & (n - 1);
    count++;
}

Time: O(number of set bits)

---

Built-in Methods

Integer.bitCount(n);

---

Power of Two Check

A number is power of two if:

• Only one bit is set

boolean isPowerOfTwo(int n){
    return n > 0 && (n & (n - 1)) == 0;
}

Examples:

• 8 → true
• 10 → false

---

Subsets Using Bits

Idea

For a set of size n:

• Total subsets = 2ⁿ
• Each subset = one binary mask

Example:

[1, 2, 3]

000 → []
001 → [1]
010 → [2]
011 → [1,2]
100 → [3]

---

Code

for(int mask = 0; mask < (1 << n); mask++){
    for(int i = 0; i < n; i++){
        if((mask & (1 << i)) != 0)
            System.out.print(arr[i]);
    }
}

Used in:

• Subset problems
• Backtracking optimization
• Bitmask DP

---

Bitmasking Techniques

Check ith Bit

(x & (1 << i)) != 0

---

Set ith Bit

x = x | (1 << i);

---

Clear ith Bit

x = x & ~(1 << i);

---

Toggle ith Bit

x = x ^ (1 << i);

---

Isolate Lowest Set Bit

int lsb = n & (-n);

Used in:

• Fenwick Tree
• Subset generation
• Optimization tricks

---

Advanced Bit Tricks

Swap Without Temp

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

---

Check Odd or Even

if((n & 1) == 1) // odd

---

Multiply / Divide by 2

n << 1
n >> 1

---

Common Interview Patterns

• Unique element detection
• Missing number
• Subsets generation
• Bitmask DP
• Optimization of brute force

---

Common Mistakes

• Forgetting parentheses in shifts
• Sign bit issues with negatives
• Assuming fixed bit length
• Overusing bits where clarity is better

---

When to Use Bit Manipulation

Use when:

• Constraints are tight
• Space must be O(1)
• Pattern involves toggling or parity

Avoid when:

• Code readability matters more
• Numbers are large objects
• Problem is clearer with DP