Advanced Bit Manipulation

1. Introduction: Talking to the Hardware

While standard algorithms manipulate integers and arrays at a high level, Bit Manipulation drops down to the bare metal. It allows you to manipulate the actual 0s and 1s that make up the numbers in the computer's memory.

Why is this important? Because bitwise operations (&, |, ^, <<, >>) execute in a single CPU clock cycle. They are mathematically the fastest operations a computer can perform. In competitive programming, system design, and advanced algorithms (like cryptographic hashing or network routing), bit manipulation is heavily used to optimize both memory ($O(1)$ space sets) and speed.

2. Core Concept: XOR Properties and Bitmasks

The Magic of XOR (^)

The XOR operator outputs 1 only if the bits are different. It has three magical mathematical properties that are tested in almost every tech interview:

1. Any number XOR itself is 0: X ^ X = 0
2. Any number XOR 0 is itself: X ^ 0 = X
3. Associative & Commutative: A ^ B ^ C = A ^ C ^ B

This means XOR acts as a toggle. If you XOR a number twice, it cancels out.

Bitmasks

A Bitmask is a way to represent a subset or a boolean array using a single 32-bit integer. For example, the binary number 10101 means "Items 0, 2, and 4 are included, while Items 1 and 3 are excluded."

• To Set the $i$-th bit: mask | (1 << i)
• To Clear the $i$-th bit: mask & ~(1 << i)
• To Check the $i$-th bit: (mask & (1 << i)) != 0
• To Toggle the $i$-th bit: mask ^ (1 << i)

3. Beginner Code Example: Single Number (XOR)

Problem Statement: (LeetCode 136) Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Brute Force (Suboptimal)

Use a HashMap to count frequencies. Takes $O(N)$ time and $O(N)$ space.

Optimal Bit Manipulation

Because X ^ X = 0, if we XOR every single number in the array together, all the duplicates will cancel each other out, leaving ONLY the single number!

public class SingleNumber {
    public static int findSingle(int[] nums) {
        int result = 0; // X ^ 0 = X
        
        for (int num : nums) {
            result = result ^ num; // XOR assignment
        }
        
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. Single pass.
• Space Complexity: $O(1)$. No HashMaps.

4. Intermediate Code Example: Brian Kernighan’s Algorithm

Problem Statement: (LeetCode 191) Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Naive Approach

Shift the number to the right 32 times, checking the last bit (n & 1) every time. Takes strictly 32 operations.

Brian Kernighan’s Algorithm

What if the number only has two 1s (e.g., 10000000000000000000000000000001)? Kernighan's algorithm skips the zeros and only does operations equal to the exact number of 1s.

The Insight: The operation n & (n - 1) always removes the lowest set bit (the rightmost 1) from n. Example: n = 12 (Binary 1100). n - 1 = 11 (Binary 1011). 1100 & 1011 = 1000 (The rightmost 1 disappeared!).

public class HammingWeight {
    public static int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // Erase the lowest set bit
            count++;
        }
        return count;
    }
}

Complexity Analysis:

• Time Complexity: $O(K)$, where $K$ is the number of 1 bits. (Worst case $O(32)$, which is $O(1)$).
• Space Complexity: $O(1)$.

5. Advanced Code Example: Single Number III (Two Unique Numbers)

Problem Statement: (LeetCode 260) Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

This is a very famous, difficult interview question.

The Insight:

1. If we XOR all numbers, the duplicates cancel out. The result is X ^ Y (the two unique numbers XORed together).
2. Because X and Y are different numbers, X ^ Y will have at least one bit set to 1. This 1 represents a bit position where X and Y differ!
3. We can find this differing bit (usually the lowest set bit) and use it as a filter to divide the array into two groups: numbers that have this bit set, and numbers that don't.
4. X will go to one group, Y will go to the other. The duplicates will go in pairs to whichever group they belong.
5. If we XOR the two groups separately, we will isolate X and Y!

public class TwoSingleNumbers {
    public static int[] singleNumber(int[] nums) {
        // Step 1: Get X ^ Y
        int xorAll = 0;
        for (int num : nums) {
            xorAll ^= num;
        }
        
        // Step 2: Find the lowest set bit (rightmost 1) in xorAll
        // Two's complement trick: n & (-n) isolates the lowest set bit!
        // To avoid overflow issues with Integer.MIN_VALUE, we can do:
        int lowestSetBit = (xorAll == Integer.MIN_VALUE) ? xorAll : xorAll & (-xorAll);
        
        // Step 3: Divide numbers into two groups and XOR them
        int[] result = new int[2]; // [X, Y]
        
        for (int num : nums) {
            if ((num & lowestSetBit) == 0) {
                // Group 0: The bit is NOT set
                result[0] ^= num;
            } else {
                // Group 1: The bit IS set
                result[1] ^= num;
            }
        }
        
        return result;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We iterate through the array exactly twice.
• Space Complexity: $O(1)$. Just a few integer variables.

6. Common Mistakes Beginners Make

1. Operator Precedence Issues

   • The Mistake: Writing if (mask & 1 == 0)
   • Why it's wrong: In Java, the equality operator == has higher precedence than the bitwise AND &. It evaluates as if (mask & (1 == 0)), which is mask & false (compile error).
   • The Fix: ALWAYS wrap bitwise operations in parentheses: if ((mask & 1) == 0).

2. Logical vs Bitwise Operators

   • The Mistake: Using && instead of &.
   • Why it's wrong: && is a logical operator for booleans (true && false). & is the bitwise operator for integers (5 & 3).

3. Signed vs Unsigned Right Shift (>> vs >>>)

   • The Mistake: Using >> to shift negative numbers expecting them to become 0 eventually.
   • Why it's wrong: In Java, >> is an Arithmetic Shift. It preserves the sign bit. Shifting a negative number right will fill the new bits with 1s, resulting in an infinite loop!
   • The Fix: Use >>> (Logical Shift) which always fills with 0s, regardless of the sign.

7. Interview Q&A

Q1: How do you isolate the rightmost set bit in $O(1)$ time? Answer: Use the formula n & (-n). Because computers use Two's Complement to represent negative numbers (-n = ~n + 1), the bitwise AND of n and -n will magically wipe out all 1s except the lowest one.

Q2: How do you swap two variables without using a temporary variable? Answer: You can use XOR!

a = a ^ b;
b = a ^ b; // b becomes the original 'a'
a = a ^ b; // a becomes the original 'b'

(Note: Mention to the interviewer that this is just a fun math trick and is actually slower in modern CPUs than using a temp variable due to instruction pipelining).

Q3: Can bitmasks be used to solve the Subsets/Power Set problem? Answer: Absolutely. If the array size is $N$, there are $2^N$ subsets. You can write a loop for (int mask = 0; mask < (1 << N); mask++). The mask represents a unique subset. You then loop i from $0$ to $N$, checking if ((mask & (1 << i)) != 0) to include arr[i] in the current subset.

8. Practice Problems

1. Power of Two (LeetCode 231)
   • Hint: A number is a power of two if it has exactly one 1 bit. You can use Kernighan's trick: return n > 0 && (n & (n - 1)) == 0;.
2. Missing Number (LeetCode 268)
   • Hint: Instead of Gauss's formula, XOR all indices from 0 to n, and XOR all numbers in the array. The missing number will remain!
3. Subsets (LeetCode 78)
   • Goal: Implement the $2^N$ iterative bitmask solution discussed in Q3.

9. Summary

• Speed: Bitwise operations are $O(1)$ and run natively on the CPU ALU.
• XOR Toggles: X ^ X = 0 is the key to solving pairing/duplicate removal problems.
• Brian Kernighan’s Trick: n & (n - 1) removes the rightmost 1. Perfect for counting bits.
• Isolation Trick: n & (-n) isolates the rightmost 1.
• Precedence Warning: Always heavily parenthesize your bitwise math!