Bit Manipulation Problems

Introduction

Bit manipulation is a powerful technique that operates directly on the bits of binary representations of numbers. While often overlooked by beginners, mastering bit manipulation can lead to elegant solutions that are both time and space efficient. In LeetCode and other coding platforms, bit manipulation problems test your understanding of how data is stored and manipulated at the lowest level.

In this guide, we'll explore common bit manipulation techniques, typical problem patterns, and step-by-step solutions to popular LeetCode problems in this category.

Understanding Binary Representation

Before diving into solving problems, let's quickly refresh our understanding of binary representation.

In a computer, all data is stored as a sequence of bits (0s and 1s). For example, the decimal number 13 is represented in binary as 1101:

1    1    0    1
2³   2²   2¹   2⁰
8    4    2    1

So, 8 + 4 + 0 + 1 = 13

Basic Bit Operations

Let's review the fundamental bit operations you'll need to solve LeetCode problems:

Operation	Symbol	Description
AND	&	Sets each bit to 1 if both bits are 1
OR	|	Sets each bit to 1 if at least one bit is 1
XOR	^	Sets each bit to 1 if only one bit is 1
NOT	~	Inverts all bits
Left Shift	<<	Shifts bits left, adding zeros at right
Right Shift	>>	Shifts bits right, filling with sign bit (in most languages)

Common Bit Manipulation Techniques

1. Checking if a bit is set

To check if the ith bit is set in a number n:

java

boolean isBitSet(int n, int i) {
    return (n & (1 << i)) != 0;
}

2. Setting a bit

To set the ith bit in a number n:

java

int setBit(int n, int i) {
    return n | (1 << i);
}

3. Clearing a bit

To clear the ith bit in a number n:

java

int clearBit(int n, int i) {
    return n & ~(1 << i);
}

4. Toggling a bit

To toggle the ith bit in a number n:

java

int toggleBit(int n, int i) {
    return n ^ (1 << i);
}

LeetCode Problem Examples

Let's tackle some common bit manipulation problems from LeetCode.

Problem 1: Single Number (LeetCode #136)

Problem: Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Example:

Input: [2,2,1]
Output: 1

Solution using XOR:

The XOR operation has an interesting property: a ^ a = 0 and a ^ 0 = a. This means that if we XOR all numbers in the array, numbers that appear twice will cancel out, leaving only the single number.

java

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

Step-by-step explanation:

1. Initialize result = 0
2. Iterate through each number in the array
3. XOR the current number with result
4. Return the final result

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

Problem 2: Counting Bits (LeetCode #338)

Problem: Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 -> 0     (0 bits are 1)
1 -> 1     (1 bit is 1)
2 -> 10    (1 bit is 1)
3 -> 11    (2 bits are 1)
4 -> 100   (1 bit is 1)
5 -> 101   (2 bits are 1)

Solution using DP and Bit Manipulation:

java

public int[] countBits(int n) {
    int[] result = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // i & (i-1) drops the lowest set bit
        result[i] = result[i & (i-1)] + 1;
    }
    return result;
}

Step-by-step explanation:

1. Create an array result of size n+1
2. result[0] = 0 (as 0 has no set bits)
3. For each number i from 1 to n:
   • i & (i-1) gives us the number with the rightmost set bit removed
   • The number of set bits in i equals the number of set bits in i & (i-1) plus 1
   • Set result[i] = result[i & (i-1)] + 1

Time Complexity: O(n)
Space Complexity: O(n) for the output array

Problem 3: Power of Two (LeetCode #231)

Problem: Given an integer n, return true if it is a power of two. Otherwise, return false.

Example:

Input: n = 16
Output: true
Explanation: 16 = 2^4

Solution using Bit Manipulation:

A key observation is that powers of 2 have exactly one bit set in their binary representation:

• 1 = 2^0 = 01 (in binary)
• 2 = 2^1 = 10 (in binary)
• 4 = 2^2 = 100 (in binary)
• 8 = 2^3 = 1000 (in binary)

We can use the trick n & (n-1) to check if a number has exactly one bit set:

java

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

Step-by-step explanation:

1. Check if n is positive (powers of 2 are always positive)
2. Use the bit trick n & (n - 1) which removes the rightmost set bit
3. For powers of 2, this operation should result in 0

Time Complexity: O(1)
Space Complexity: O(1)

Problem 4: Number of 1 Bits (LeetCode #191)

Problem: Write a function that takes an unsigned integer and returns the number of '1' bits it has.

Example:

Input: n = 11 (which is 00000000000000000000000000001011 in binary)
Output: 3

Solution using Bit Shifting:

java

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count += (n & 1);
        n >>>= 1; // Unsigned right shift
    }
    return count;
}

Alternative solution using Bit Trick:

java

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1); // Clear the least significant bit set to 1
        count++;
    }
    return count;
}

Step-by-step explanation (for the second solution):

1. Initialize count to 0
2. While n is not 0:
   • Use n & (n-1) to clear the least significant set bit
   • Increment count
3. Return count

Time Complexity: O(number of set bits)
Space Complexity: O(1)

Real-world Applications of Bit Manipulation

Bit manipulation isn't just for coding interviews—it has numerous practical applications:

1. Optimizing Storage for Flags

Instead of using separate boolean variables for flags, you can use bits within a single integer:

java

public class FlagManager {
    // Flags as bit positions
    private static final int READ_PERMISSION = 1 << 0;    // 001
    private static final int WRITE_PERMISSION = 1 << 1;   // 010
    private static final int EXECUTE_PERMISSION = 1 << 2; // 100
    
    private int permissions = 0;
    
    public void grantPermission(int permission) {
        permissions |= permission;
    }
    
    public void revokePermission(int permission) {
        permissions &= ~permission;
    }
    
    public boolean hasPermission(int permission) {
        return (permissions & permission) == permission;
    }
}

2. RGB Color Manipulation

Bit manipulation is commonly used for color processing in graphics programming:

java

public class ColorUtils {
    public static int makeRGB(int r, int g, int b) {
        return ((r & 0xFF) << 16) | ((g & 0xFF) << 8) | (b & 0xFF);
    }
    
    public static int getRed(int color) {
        return (color >> 16) & 0xFF;
    }
    
    public static int getGreen(int color) {
        return (color >> 8) & 0xFF;
    }
    
    public static int getBlue(int color) {
        return color & 0xFF;
    }
}

3. Network Programming

IP addresses and subnet masks involve bit manipulation:

java

public boolean isInSubnet(int ip, int subnetAddress, int subnetMask) {
    return (ip & subnetMask) == (subnetAddress & subnetMask);
}

Advanced Bit Manipulation Techniques

Swap without temporary variable

java

public void swap(int[] arr, int i, int j) {
    if (i != j) {
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }
}

Find the rightmost set bit

java

int rightmostSetBit(int n) {
    return n & -n;
}

Turn off the rightmost set bit

java

int turnOffRightmostSetBit(int n) {
    return n & (n - 1);
}

Check if a number is a power of 4

java

boolean isPowerOfFour(int n) {
    // Check if it's a power of 2 and if set bit is at even position
    return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

Summary

Bit manipulation is a powerful technique for solving a wide range of problems efficiently. In this guide, we've covered:

• Basic bit operations (AND, OR, XOR, NOT, shifts)
• Common bit manipulation techniques and tricks
• Solutions to popular LeetCode bit manipulation problems
• Real-world applications of bit manipulation
• Advanced bit manipulation techniques

By mastering these techniques, you'll be better equipped to tackle not only LeetCode problems but also real-world programming challenges that benefit from bit-level operations.

Practice Problems

To further improve your skills, try solving these additional LeetCode problems:

1. LeetCode #137: Single Number II (medium)
2. LeetCode #260: Single Number III (medium)
3. LeetCode #78: Subsets (medium, uses bit manipulation for elegant solution)
4. LeetCode #190: Reverse Bits (easy)
5. LeetCode #201: Bitwise AND of Numbers Range (medium)
6. LeetCode #371: Sum of Two Integers (medium, addition without using + operator)
7. LeetCode #461: Hamming Distance (easy)
8. LeetCode #477: Total Hamming Distance (medium)

Additional Resources

• Bit Twiddling Hacks - Stanford collection of bit manipulation tricks
• "Hacker's Delight" by Henry S. Warren, Jr. - A comprehensive book on bit manipulation
• BitHacks - GitHub repository with bit manipulation techniques

Remember that mastering bit manipulation takes practice. Start with simple problems and work your way up to more complex ones. Good luck!