06. 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

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^9
The answer for the given input will fit in a 32-bit integer.

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

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 2^31 - 1

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

An n-bit gray code sequence is a sequence of 2^n integers where:

Every integer is in the inclusive range [0, 2n - 1],
The first integer is 0,
An integer appears no more than once in the sequence,
The binary representation of every pair of adjacent integers differs by exactly one bit, and
The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].

00 and 01 differ by one bit

01 and 11 differ by one bit

11 and 10 differ by one bit

10 and 00 differ by one bit

[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].

00 and 10 differ by one bit

10 and 11 differ by one bit

11 and 01 differ by one bit

01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

Constraints:

1 <= n <= 16

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

Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2n.

Since the answer may be too large, return it modulo 10^9 + 7.

Note that XOR is the bitwise XOR operation.

Example 1:

Input: a = 12, b = 5, n = 4
Output: 98
Explanation: For x = 2, (a XOR x) = 14 and (b XOR x) = 7. Hence, (a XOR x) * (b XOR x) = 98.
It can be shown that 98 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.

Example 2:

Input: a = 6, b = 7 , n = 5
Output: 930
Explanation: For x = 25, (a XOR x) = 31 and (b XOR x) = 30. Hence, (a XOR x) * (b XOR x) = 930.
It can be shown that 930 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2^n.

Example 3:

Input: a = 1, b = 6, n = 3
Output: 12
Explanation: For x = 5, (a XOR x) = 4 and (b XOR x) = 3. Hence, (a XOR x) * (b XOR x) = 12.
It can be shown that 12 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.

Constraints:

0 <= a, b < 250
0 <= n <= 50

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

5. Reverse Integer (Leetcode:7)

Problem Statement

Given a signed 32-bit integer x, return x with its digits reversed.
If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

-2^31 <= x <= 2^31 - 1

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

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

Problem Statement

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

Example 1:

Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The subarray [3] has OR value of 3. Hence, we return 1.

Example 2:

Input: nums = [2,1,8], k = 10
Output: 3
Explanation:
The subarray [2,1,8] has OR value of 11. Hence, we return 3.

Example 3:

Input: nums = [1,2], k = 0
Output: 1
Explanation:
The subarray [1] has OR value of 1. Hence, we return 1.

Constraints:

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 10^9
0 <= k <= 10^9

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

7. Sum of Two Integers (Leetcode:371)

Problem Statement

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

-1000 <= a, b <= 1000

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

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

Problem Statement

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith query.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

Example 2:
Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

1 <= arr.length, queries.length <= 3 * 10^4
1 <= arr[i] <= 10^9
queries[i].length == 2
0 <= lefti <= righti < arr.length

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

9. Find Longest Awesome Substring (Leetcode:1542)

Problem Statement

You are given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it a palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

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

Problem Statement

You are given an array nums and an integer k. You need to find a subarray of nums such that the absolute difference between k and the bitwise OR of the subarray elements is as small as possible. In other words, select a subarray nums[l..r] such that |k - (nums[l] OR nums[l + 1] ... OR nums[r])| is minimum.

Return the minimum possible value of the absolute difference.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,4,5], k = 3
Output: 0
Explanation:
The subarray nums[0..1] has OR value 3, which gives the minimum absolute difference |3 - 3| = 0.

Example 2:

Input: nums = [1,3,1,3], k = 2
Output: 1
Explanation:
The subarray nums[1..1] has OR value 3, which gives the minimum absolute difference |3 - 2| = 1.

Example 3:

Input: nums = [1], k = 10
Output: 9
Explanation:
There is a single subarray with OR value 1, which gives the minimum absolute difference |10 - 1| = 9.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

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

Problem Statement

You are given a 0-indexed integer array nums and an integer k.

In one operation, you can pick any index i of nums such that 0 <= i < nums.length - 1 and replace nums[i] and nums[i + 1] with a single occurrence of nums[i] & nums[i + 1], where & represents the bitwise AND operator.

Return the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.

Example 1:

Input: nums = [3,5,3,2,7], k = 2
Output: 3
Explanation: Let's do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [1,3,2,7].
2. Replace nums[2] and nums[3] with (nums[2] & nums[3]) so that nums becomes equal to [1,3,2].
The bitwise-or of the final array is 3.
It can be shown that 3 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k

Example 2:

Input: nums = [7,3,15,14,2,8], k = 4
Output: 2
Explanation: Let's do the following operations:
1. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,15,14,2,8].
2. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,14,2,8].
3. Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [2,2,8].
4. Replace nums[1] and nums[2] with (nums[1] & nums[2]) so that nums becomes equal to [2,0].
The bitwise-or of the final array is 2.
It can be shown that 2 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.

Example 3:

Input: nums = [10,7,10,3,9,14,9,4], k = 1
Output: 15
Explanation: Without applying any operations, the bitwise-or of nums is 15.
It can be shown that 15 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] < 2^30
0 <= k < nums.length

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

Problem 12: Single Number III (Leetcode:260)

Problem Statement

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 can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Constraints:

2 <= nums.length <= 3 * 104

-231 <= nums[i] <= 231 - 1

Each integer in nums will appear twice, only two integers will appear once.

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach