Common Bit Manipulation Techniques

Bit Manipulation can involve numerous tricks. There's a website called Bit Twiddling Hacks that has collected nearly all the advanced techniques in bit manipulation. The website is:

http://graphics.stanford.edu/~seander/bithacks.html

However, most of these techniques are quite obscure. I believe they can be used as a reference dictionary, and there is no need to delve into each one. Yet, I think mastering interesting and useful bit manipulation techniques is essential for everyone.

Therefore, this article starts with some interesting (though not very useful) bit manipulation techniques, and then summarizes some commonly used techniques in algorithm problems and engineering development.

1. Some Interesting Bit Manipulations

// Use the OR operation `|` and space to convert English characters to lowercase
('a' | ' ') = 'a'
('A' | ' ') = 'a'

// Use the AND operation `&` and underscore to convert English characters to uppercase
('b' & '_') = 'B'
('B' & '_') = 'B'

// Use the XOR operation `^` and space to toggle the case of English characters
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'

// The reason the above operations produce peculiar effects is due to ASCII encoding
// ASCII characters are actually numbers, and the numbers corresponding
// to spaces and underscores can change the case through bit operations
// Readers interested can check the ASCII table to
// calculate it themselves, I won't elaborate here


// Swap two numbers without using a temporary variable
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// Now a = 2, b = 1


// Increment by one
int n = 1;
n = -~n;
// Now n = 2


// Decrement by one
int n = 2;
n = ~-n;
// Now n = 1


// Determine if two numbers have opposite signs
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true

int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false

If the first six techniques are not very useful, the seventh technique is quite practical, utilizing the sign bit of two's complement encoding. The most significant bit of integer encoding is the sign bit; the sign bit of a negative number is 1, and for a non-negative number, it is 0. By leveraging the properties of XOR, you can determine if two numbers have opposite signs.

Of course, if you do not use bitwise operations to check if two numbers have opposite signs, you would need to use if-else branches, which can be quite cumbersome. You might consider using the product to determine if two numbers have opposite signs, but this approach can lead to integer overflow and errors.

Using index & (arr.length - 1)

In my article Monotonic Stack Solution Pattern, I introduced the concept of a circular array. This is essentially using the modulo (remainder) operation to make the array appear as if the head and tail are connected, forming a loop that never ends:

int[] arr = {1,2,3,4};
int index = 0;
while (true) {
    // looping in a circular array
    print(arr[index % arr.length]);
    index++;
}
// output: 1,2,3,4,1,2,3,4,1,2,3,4...

int arr[] = {1, 2, 3, 4};
int index = 0;
while (true) {
    // loop through the circular array
    cout << arr[index % (sizeof(arr) / sizeof(int))] << endl;
    index++;
}
// output: 1,2,3,4,1,2,3,4,1,2,3,4...

arr = [1,2,3,4]
index = 0
while True:
    # Loop through the circular array
    print(arr[index % len(arr)])
    index += 1
# Output: 1,2,3,4,1,2,3,4,1,2,3,4...

arr := []int{1, 2, 3, 4}
index := 0
for {
    // Looping in a circular array
    fmt.Print(arr[index%len(arr)])
    index++
}
// Output: 1,2,3,4,1,2,3,4,1,2,3,4...

var arr = [1, 2, 3, 4];
var index = 0;
while (true) {
    // looping in a circular array
    console.log(arr[index % arr.length]);
    index++;
}
// output: 1,2,3,4,1,2,3,4,1,2,3,4...

However, the modulo operation % is actually quite expensive for computers, so we can use the & operation to find the remainder:

int[] arr = {1,2,3,4};
int index = 0;
while (true) {
    // loop in the circular array
    print(arr[index & (arr.length - 1)]);
    index++;
}
// output: 1,2,3,4,1,2,3,4,1,2,3,4...

vector<int> arr = {1, 2, 3, 4};
int index = 0;
while (true) {
    // Looping in a circular array
    cout << arr[index & (arr.size() - 1)] << " ";
    index++;
}
// Output: 1,2,3,4,1,2,3,4,1,2,3,4...

arr = [1, 2, 3, 4]
index = 0
while True:
    # Loop in a circular array
    print(arr[index & (len(arr) - 1)], end=", ")
    index += 1
# Output: 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, ...

arr := []int{1, 2, 3, 4}
index := 0
for {
    // loop in a circular array
    fmt.Print(arr[index&(len(arr)-1)])
    index++
}
// output: 1,2,3,4,1,2,3,4,1,2,3,4...

var arr = [1,2,3,4];
var index = 0;
while (true) {
    // loop through the circular array
    console.log(arr[index & (arr.length - 1)]);
    index++;
}
// output: 1,2,3,4,1,2,3,4,1,2,3,4...

In simple terms, the bit operation & (arr.length - 1) can replace the modulus operation % arr.length, offering better performance.

Now, a question arises: if you continuously increment index++, you achieve a cyclic traversal. But what if you continuously decrement index--? Can you still achieve the effect of a circular array?

The answer is, if you use the modulus % method, when index becomes less than 0, the modulus result will also be negative, requiring special handling. However, with the & bitwise operation, index will not become negative and will still function correctly:

int[] arr = {1,2,3,4};
int index = 0;
while (true) {
    // looping in a circular array
    print(arr[index & (arr.length - 1)]);
    index--;
}
// output: 1,4,3,2,1,4,3,2,1,4,3,2,1...

int arr[] = {1,2,3,4};
int index = 0;
while (true) {
    // Loop in a circular array
    cout << arr[index & (sizeof(arr) / sizeof(*arr) - 1)] << " ";
    index--;
}
// Output: 1,4,3,2,1,4,3,2,1,4,3,2,1...

arr = [1, 2, 3, 4]
index = 0

while True:
    # Looping in a circular array
    print(arr[index & (len(arr) - 1)])
    index -= 1

arr := []int{1, 2, 3, 4}
index := 0
for {
    // looping in a circular array
    fmt.Print(arr[index&(len(arr)-1)])
    index--
}
// output: 1,4,3,2,1,4,3,2,1,4,3,2,1...

var arr = [1,2,3,4];
var index = 0;
while (true) {
    console.log(arr[index & (arr.length - 1)]);
    index--;
}
// Output: 1,4,3,2,1,4,3,2,1,4,3,2,1...

We usually don't use this technique when writing our own code, but it might often appear when studying other codebases. It's good to have an impression to avoid confusion later.

The Use of n & (n-1)

The operation n & (n-1) is common in algorithms. Its purpose is to clear the last '1' in the binary representation of the number n.

A picture makes it easy to understand:

The core logic is that n - 1 will certainly clear the last '1' and turn all subsequent '0's into '1's. Then performing an & operation with n will change only the last '1' into '0'.

Calculating Hamming Weight

This is LeetCode Problem 191: "Number of 1 Bits":

The task is to return the number of 1s in the binary representation of n. Since n & (n - 1) can remove the last 1, you can use a loop to continuously remove 1s while counting, until n becomes 0.

int hammingWeight(int n) {
    int res = 0;
    while (n != 0) {
        n = n & (n - 1);
        res++;
    }
    return res;
}

int hammingWeight(int n) {
    int res = 0;
    while (n != 0) {
        n = n & (n - 1);
        res++;
    }
    return res;
}

def hammingWeight(n: int) -> int:
    res = 0
    while n != 0:
        n = n & (n - 1)
        res += 1
    return res

func hammingWeight(n int) int {
    res := 0
    for n != 0 {
        n = n & (n - 1)
        res++
    }
    return res
}

var hammingWeight = function(n) {
    var res = 0;
    while (n != 0) {
        n = n & (n - 1);
        res++;
    }
    return res;
};

判断 2 的指数

力扣第 231 题「2 的幂」就是这个问题。

一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：

2^0 = 1 = 0b0001
2^1 = 2 = 0b0010
2^2 = 4 = 0b0100

It becomes simple if you use the trick n & (n-1) (note the operator precedence; the parentheses cannot be omitted):

boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

def isPowerOfTwo(n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 0

func isPowerOfTwo(n int) bool {
    if n <= 0 {
        return false
    }
    return (n & (n - 1)) == 0
}

var isPowerOfTwo = function(n) {
    if (n <= 0) return false;
    return (n & (n - 1)) === 0;
};

The Application of a ^ a = 0

The properties of the XOR operation should be remembered:

A number XORed with itself results in 0, that is, a ^ a = 0; a number XORed with 0 results in the number itself, that is, a ^ 0 = a.

Finding the Element that Appears Only Once

This is LeetCode problem 136, "Single Number":

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

Input: nums = [4,1,2,1,2]
Output: 4

Input: nums = [1]
Output: 1

For this problem, we simply XOR all the numbers. Pairs of numbers will become 0, and the single number XORed with 0 remains itself, so the final result of the XOR operation is the element that appears only once:

int singleNumber(int[] nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}

def singleNumber(nums: List[int]) -> int:
    res = 0
    for n in nums:
        res ^= n
    return res

func singleNumber(nums []int) int {
    res := 0
    for _, n := range nums {
        res ^= n
    }
    return res
}

var singleNumber = function(nums) {
    var res = 0;
    for (var i = 0; i < nums.length; i++) {
        res ^= nums[i];
    }
    return res;
};

Finding the Missing Element

This is LeetCode problem 268 "Missing Number":

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Given an array of length n, which should contain indices [0, n). However, you need to fit n + 1 elements [0, n] into it, so one element is definitely missing. Please find this missing element.

This problem is not difficult. We can easily think of sorting the array and then traversing it to find the missing element.

Alternatively, using the characteristics of data structures, we can use a HashSet to store the numbers that appear in the array. Then, by traversing the numbers between [0, n] and checking the HashSet, we can easily find the missing element.

The sorting solution has a time complexity of O(NlogN), while the HashSet solution has a time complexity of O(N), but it also requires O(N) space complexity to store the HashSet.

There is actually a particularly simple solution to this problem: the arithmetic series summation formula.

The problem can be understood this way: there is an arithmetic series 0, 1, 2, ..., n, missing one number. Please find it. That number is simply sum(0, 1, ..., n) - sum(nums).

int missingNumber(int[] nums) {
    int n = nums.length;
    // Although the data range given by the problem is not large, we
    // should use long type to prevent integer overflow for the sake of
    // Sum formula: (first term + last term) * number of terms / 2
    long expect = (0 + n) * (n + 1) / 2;
    long sum = 0;
    for (int x : nums) {
        sum += x;
    }
    return (int)(expect - sum);
}

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    // Although the data range given by the problem is not large, we
    // should use long type to prevent integer overflow for the sake of
    // Sum formula: (first term + last term) * number of terms / 2
    long expect = (0 + n) * (n + 1) / 2;
    long sum = 0;
    for (int x : nums) {
        sum += x;
    }
    return (int)(expect - sum);
}

from typing import List

def missingNumber(nums: List[int]) -> int:
    n = len(nums)
    # Although the data range given by the problem is not
    # large, it's rigorous to use long type to prevent integer
    # Sum formula: (first term + last term) * number of terms / 2
    expect = (0 + n) * (n + 1) / 2
    sum_ = 0
    for x in nums:
        sum_ += x
    return int(expect - sum_)

func missingNumber(nums []int) int {
    n := len(nums)
    // Although the data range given by the problem is not
    // large, to be rigorous, use long type to prevent integer
    // Sum formula: (first term + last term) * number of terms / 2
    expect := (0 + n) * (n + 1) / 2
    var sum int64
    for _, x := range nums {
        sum += int64(x)
    }
    return int(expect - sum)
}

var missingNumber = function(nums) {
    var n = nums.length;
    // Although the data range given by the problem is not large, we
    // should use long type to prevent integer overflow for the sake of
    // Sum formula: (first term + last term) * number of terms / 2
    var expect = (0 + n) * (n + 1) / 2;
    var sum = 0;
    for (var i = 0; i < n; i++) {
        sum += nums[i];
    }
    return (expect - sum);
};

However, the main topic of this article is bit manipulation. Let's discuss how to use bit manipulation techniques to solve this problem.

Let's revisit the properties of the XOR operation: a number XORed with itself results in 0, and a number XORed with 0 remains unchanged.

Moreover, the XOR operation is commutative and associative, which means:

2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3

Using these properties, we can cleverly determine the missing element in the problem, such as nums = [0,3,1,4]:

For easier understanding, let's first assume we add an additional index so that each element corresponds to the index equal to itself:

After doing this, we can see that all indices and elements form pairs except for the missing element. If we identify the single index 2, we also identify the missing element.

How do we find this single number? By performing XOR on all elements and indices, paired numbers will cancel each other out to 0, leaving only the single element, which achieves our goal:

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int res = 0;
        // first, xor with the newly added index
        res ^= n;
        // then, xor with the other elements and indices
        for (int i = 0; i < n; i++)
            res ^= i ^ nums[i];
        return res;
    }
}

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        // first XOR with the newly added index
        res ^= n;
        // then XOR with the other elements and indices
        for (int i = 0; i < n; i++)
            res ^= i ^ nums[i];
        return res;
    }
};

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        # first xor with the newly added index
        res ^= n
        # then xor with the other elements and indices
        for i in range(n):
            res ^= i ^ nums[i]
        return res

func missingNumber(nums []int) int {
    n := len(nums)
    res := 0
    // first XOR with the newly added index
    res ^= n
    // then XOR with the other elements and indices
    for i := 0; i < n; i++ {
        res ^= i ^ nums[i]
    }
    return res
}

var missingNumber = function(nums) {
    var n = nums.length;
    var res = 0;
    
    // first, XOR with the newly added index
    res ^= n;
    
    // then, XOR with the other elements and indices
    for (var i = 0; i < n; i++)
        res ^= i ^ nums[i];
        
    return res;
};

Because the XOR operation satisfies the commutative and associative laws, it can always eliminate paired numbers, leaving the missing element.

Here, we have covered the common bitwise operations. These techniques are not difficult for those who understand them, but may seem hard for others. You don't need to memorize them by heart; just having a general idea is enough.