Bit Manipulation

Core Bitwise Operators

Bitwise operators work on integers but treat them as sequences of binary digits. They are fundamental to low-level programming and solving certain algorithmic puzzles.

  0101  (5)
& 0110  (6)
------
  0100  (4)

  0101  (5)
| 0110  (6)
------
  0111  (7)

  0101  (5)
^ 0110  (6)
------
  0011  (3)

~0101 (5) -> ...11111010 (-6)

0101 (5) << 1  ->  1010 (10)
0101 (5) << 2  -> 10100 (20)

1010 (10) >> 1 -> 0101 (5)
1011 (11) >> 1 -> 0101 (5)

Bitmasking

A bitmask is an integer used to manipulate specific bits in another integer. The key idea is to create a mask with a 1 at the bit position you care about.

# k is the bit position (0-indexed from the right)
def check_bit(n, k):
  return (n & (1 << k)) != 0

def set_bit(n, k):
  return n | (1 << k)

def clear_bit(n, k):
  return n & ~(1 << k)

def toggle_bit(n, k):
  return n ^ (1 << k)

Common Tricks and Properties

• Powerful XOR Properties:
  • x ^ x = 0 (A number XORed with itself is zero)
  • x ^ 0 = x (A number XORed with zero is unchanged)
  • XOR is commutative and associative, meaning order doesn't matter: a ^ b ^ a = b ^ a ^ a = b ^ 0 = b
• Check if a number is a power of two: A positive number n is a power of two if and only if n & (n - 1) == 0.
• Counting Set Bits (Hamming Weight): Many languages have a built-in function (e.g., __builtin_popcount in C++, Integer.bitCount() in Java) which is highly optimized.

Classic Problems

Classic Problem: Single Number

Given an array where every element appears twice except for one, find that single one. This is a perfect use case for XOR's properties. By XORing all numbers in the array, all the paired numbers will cancel each other out, leaving only the unique number.

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

Classic Problem: Power of Four

Given an integer, return true if it is a power of four. This problem requires combining multiple bitwise checks:

1. It must be positive: n > 0.
2. It must be a power of two: (n & (n - 1)) == 0.
3. The single '1' bit must be in an even-indexed position: Powers of four (1, 4, 16, 64...) in binary are 1, 100, 10000, etc. The '1' is always at an even position (0-indexed from right). We can check this by ANDing with a special mask 0xaaaaaaaa which has 1s in all odd-numbered bit positions. The result must be 0.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
        # Check if it\'s a power of two
        is_power_of_two = (n & (n - 1)) == 0
        # Check if the set bit is at an even position.
        # 0xaaaaaaaa is a mask for odd-positioned bits.
        return is_power_of_two and (n & 0xaaaaaaaa) == 0

Subset Generation

A bitmask can represent a subset of a set of n items. An integer from 0 to 2ⁿ-1 can represent all possible subsets. If the j-th bit of the integer is 1, it means the j-th element is in the subset.

Classic Problem: Subsets

Given an integer array nums of unique elements, return all possible subsets. Bitmasking provides an elegant iterative solution.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        all_subsets = []
        # Iterate through all possible subset representations (0 to 2^n - 1)
        for i in range(1 << n):
            current_subset = []
            # Check each bit of \'i\' to see which elements to include
            for j in range(n):
                if ((i >> j) & 1):
                    current_subset.append(nums[j])
            all_subsets.append(current_subset)
        return all_subsets