Common Bit Manipulation Techniques

Bit Manipulation can involve many tricks. There's a website called Bit Twiddling Hacks that collects nearly all the advanced techniques for bit manipulation, which can be found at:

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

However, most of these techniques are quite obscure. I think they can be used as a reference dictionary, but there's no need to delve into each one deeply. Instead, I believe that the interesting and useful bit manipulation techniques are what everyone should master.

Therefore, this article will go from simple to complex, first showcasing a few interesting (but not very practical) bit manipulation tricks, and then summarizing some commonly used bit manipulation techniques in algorithm problems and engineering development.

I. 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 6 tips are not very useful, the 7th tip is quite practical. It leverages the sign bit of two's complement encoding. In integer encoding, the highest bit is the sign bit: for negative numbers, the sign bit is 1, and for non-negative numbers, the sign bit is 0. By using the properties of the XOR operation, you can determine if two numbers have different signs.

Of course, if you don't use bitwise operations to check for different signs, you would need to use if-else branches, which can be cumbersome. You might think of using the product to determine if two numbers have different signs, but this approach can easily lead to integer overflow, resulting in 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 bitwise operation & (arr.length - 1) can replace the modulus operation % arr.length, and it performs better.

Now, here's a question: if you keep incrementing index++, you achieve a cyclic traversal. But what if you keep decrementing 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 can also be negative, and you need special handling. However, with the & bitwise operation, index will not become negative and will still work 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 typically don't use this technique when writing our own code, but you might encounter it frequently when studying other code libraries. It’s good to have a basic understanding so you aren't confused when you see it.

Application of n & (n-1)

The operation n & (n-1) is quite common in algorithms. Its function is to remove the last 1 in the binary representation of the number n.

A diagram makes this easy to understand:

The core logic is that n - 1 will definitely remove the last 1 and turn all the 0s following it into 1s. Performing an & operation with n afterward will change only the last 1 to 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;
};

Application of a ^ a = 0

The properties of the XOR operation are essential to remember:

When a number is XORed with itself, the result is 0, i.e., a ^ a = 0; when a number is XORed with 0, the result is the number itself, i.e., 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 need to XOR all the numbers. Paired numbers will become 0, and the unpaired number XORed with 0 will remain unchanged. Therefore, the final result of the XOR operation will be 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 with indices ranging from [0, n), you need to fit n + 1 elements [0, n] into it. Obviously, one element won't fit. Your task is to find this missing element.

This problem isn't difficult. It's easy to think of sorting the array and then traversing it to find the missing element.

Alternatively, using the properties of data structures, you could store all the numbers in the array in a HashSet. Then, traverse the numbers from [0, n] and check against the HashSet to easily identify the missing element.

The time complexity for the sorting approach is O(NlogN), and for the HashSet approach, it is O(N), but it also requires O(N) space complexity to store the HashSet.

However, there's a much simpler solution to this problem: the arithmetic series sum formula.

The problem can be understood this way: you have an arithmetic sequence 0, 1, 2,..., n with one number missing. Your task is to find that missing number. Isn't that number 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.