01. Bit Manipulation

Theory

Description

Bit manipulation refers to using bitwise operators to work directly with the binary representations of numbers. These operations allow you to solve problems efficiently, often with a time complexity advantage compared to other methods. In many cases, bit manipulation can help reduce both time and space complexity, especially when working with binary data.

Common Bitwise Operators

AND (&): Sets a bit to 1 if both corresponding bits are 1.
- Example: 1101 & 1011 = 1001 (binary)
OR (|): Sets a bit to 1 if at least one of the corresponding bits is 1.
- Example: 1101 | 1011 = 1111
XOR (^): Sets a bit to 1 if the corresponding bits are different.
- Example: 1101 ^ 1011 = 0110
NOT (~): Flips all bits (inverts 0s to 1s and 1s to 0s).
- Example: ~1101 = 0010 (assuming 4-bit representation)
Left Shift (<<): Shifts bits to the left, equivalent to multiplying the number by 2.
- Example: 1010 << 1 = 10100 (multiplies by 2)
Right Shift (>>): Shifts bits to the right, equivalent to dividing the number by 2 (ignoring the remainder).
- Example: 1010 >> 1 = 0101 (divides by 2)

Key Bit Manipulation Patterns

Check if a number is even or odd:
- Use n & 1. If the result is 0, the number is even; if the result is 1, the number is odd.
- Example:
  n = 5 → 5 & 1 = 1 → Odd
  n = 6 → 6 & 1 = 0 → Even
Get the rightmost set bit:
- To isolate the rightmost set bit (1) in a number, use n & (-n).
- Example:
  n = 12 (binary 1100) → n & (-n) = 4 (binary 0100)
Set the k-th bit:
- To set (turn to 1) the k-th bit(0-indexing, right to left) of a number n, use n | (1 << k).
- Example:
  n = 4 (binary 0100), set the 3nd bit: 4 | (1 << 3) = 4 | 8 = 12 (binary 1100)
Clear the k-th bit:
- To clear (turn to 0) the k-th bit, use n & ~(1 << k).
- Example:
  n = 6 (binary 0110), clear the 2nd bit: 6 & ~(1 << 2) = 6 & ~4 = 6 & 11 = 2 (binary 0010)
Toggle the k-th bit:
- To flip (toggle) the k-th bit, use n ^ (1 << k). This changes a 1 to 0, or a 0 to 1.
- Example:
  n = 6 (binary 0110), toggle the 2nd bit: 6 ^ (1 << 2) = 6 ^ 4 = 2 (binary 0010)
Check if the k-th bit is set:
- To check if the k-th bit is 1, use (n & (1 << k)) != 0. If the result is non-zero, the k-th bit is set.
- Example:
  n = 6 (binary 0110), check if the 2nd bit is set: (6 & (1 << 2)) != 0 → True
Count the number of set bits (Hamming Weight):
- To count the number of set bits (1s) in a number, use the technique n = n & (n - 1) repeatedly. This removes the rightmost set bit in each step. Count how many times you can do this until n becomes 0.
- Example:
  n = 13 (binary 1101):
  First step: n = 13 & 12 = 1101 & 1100 = 1100
  Second step: n = 12 & 11 = 1100 & 1011 = 1000
  Third step: n = 8 & 7 = 1000 & 0111 = 0000
  Total steps: 3 set bits.
Power of 2 Check:
- A number n is a power of 2 if it has exactly one set bit. Check if n & (n - 1) == 0 (and n > 0 to exclude 0).
- Example:
  n = 8 (binary 1000), check if it's a power of 2:
  8 & (8 - 1) = 8 & 7 = 0 → True (8 is a power of 2).

Intuitive Applications of Bit Manipulation

Subset Generation:

each subset of a set can be represented as a binary number. For a set with n elements, there are \(2^n\) subsets, and each subset corresponds to a number between 0 and \(2^n - 1\).

Masking: Each number (mask) from 0 to \(2^n - 1\) is used to generate a subset. The \( i^{th} \) bit in the number indicates whether the i-th element is in the subset (1 for included, 0 for excluded).

def generate_subsets(nums):
n = len(nums)
subsets = []
for mask in range(1 << n):  # Loop over all subsets
    subset = [nums[i] for i in range(n) if mask & (1 << i)]  # Build subset
    subsets.append(subset)
return subsets

nums = [1, 2, 3]
subsets = generate_subsets(nums)

Example: For the set {1, 2, 3}, the subsets are:
- 000 → {} (empty set)
- 001 → {1}
- 010 → {2}
- 011 → {1,2}
- 100 → {3}
- 101 → {1, 3}
- 110 → {2, 3}
- 111 → {1, 2, 3}

Efficient Swapping:
- You can swap two numbers using XOR without needing a temporary variable:
  1 2 3
  a = a ^ b b = a ^ b a = a ^ b
- Example: If a = 5 and b = 3, the values of a and b will be swapped using this XOR trick.

Why Use Bit Manipulation?

Efficiency: Bitwise operations are generally faster because they directly manipulate individual bits, which is low-level and quick.
Memory Optimization: You can use fewer resources (like using a bitmask instead of an array of booleans).
Elegance: Many problems become simpler and cleaner when you think in terms of binary data and bitwise operations.

Problems

1. Total Hamming Distance (Leetcode:477)

Problem Statement

Code and Explaination

Approach 1Approach 2

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        hamming_distance = 0
        for i in range(32):
            ones = sum((num >> i) & 1 for num in nums)
            hamming_distance += ones * (len(nums) - ones)
        return hamming_distance

Explaination:
This is first approach

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        hamming_distance = 0
        mask =1 
        for i in range(32):
            zeros= sum(1 for num in nums if (num & mask)==0 )
            hamming_distance += zeros * (len(nums) - zeros)
            mask <<= 1
        return hamming_distance

Explaination:
This is second approach

2. Bitwise AND of Numbers Range (Leetcode:201)

Problem Statement

Code and Explaination

Approach 1Approach 2

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        count = 0
        while left != right:
            left >>= 1
            right >>= 1
            count += 1
        return left << count

Explaination:
This is first approach

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right = right & (right - 1)
        return right

Explaination:
This is second approach

3. Gray Code (Leetcode:89)

Problem Statement

Code and Explaination

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ i >> 1  for i in range(1 << n)]

Explaination:
This is explaination.

4. Maximum Xor Product (Leetcode:2939)

Problem Statement

5. Reverse Integer (Leetcode:7)

Problem Statement

6. Shortest Subarray With OR at Least K II (Leetcode:3097)

Problem Statement

7. Sum of Two Integers (Leetcode:371)

Problem Statement

8. XOR Queries of a Subarray (Leetcode:1310)

Problem Statement

9. Find Longest Awesome Substring (Leetcode:1542)

Problem Statement

10. Find Subarray With Bitwise OR Closest to K (Leetcode:3171)

Problem Statement

11. Minimize OR of Remaining Elements Using Operations (Leetcode:3022)

Problem Statement