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. It utilizes the sign bit of two's complement encoding. The highest bit in integer encoding is the sign bit: negative numbers have a sign bit of 1, non-negative numbers have a sign bit of 0. Using the properties of XOR, you can determine if two numbers have opposite signs.

Of course, if you don't use bitwise operations to check for opposite signs, you need to use if-else branches, which can be quite cumbersome. You might consider using the product to check if two numbers have opposite signs, but this approach can easily lead to integer overflow, resulting in errors.

Usage of index & (arr.length - 1)

In Monotonic Stack Problem Solving Pattern, I've introduced circular arrays, which essentially use modulo (remainder) to make the array appear as a continuous loop, never-ending:

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, modulo operation % is actually a relatively expensive operation 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...

Simply put, the bitwise operation & (arr.length - 1) can replace the modulo operation % arr.length, providing better performance.

Now the question arises, if you are continuously index++, you achieve circular iteration. But can you still achieve the effect of a circular array if you continuously index--?

The answer is, if you use the % modulo method, when index becomes less than 0, the modulo result can also be negative, requiring special handling. However, with the & bitwise operation, index won't become negative and can still work normally:

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 generally don't use this technique in our own code, but you might often see it when studying other code libraries. Keep this in mind so you won't be confused later.

Usage of n & (n-1)

The operation n & (n-1) is common in algorithms and serves to eliminate the last 1 in the binary representation of the number n.

It is easy to understand with a diagram:

The core logic is that n - 1 will always remove the last 1 and turn all trailing 0s into 1s. Then, performing the & operation with n will turn only the last 1 into 0.

Calculating Hamming Weight

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

It requires you to return the number of 1s in the binary representation of n. Since n & (n - 1) can eliminate the last 1, you can use a loop to continuously remove 1s and count them until n becomes 0.

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
}

#include <vector>
#include <string>

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
};

class Solution:
    def hammingWeight(self, 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) {
    let res = 0;
    while (n != 0) {
        n = n & (n - 1);
        res++;
    }
    return res;
};

Determine if a Number is a Power of Two

LeetCode Problem 231, "Power of Two", addresses this question.

A number is a power of two if its binary representation contains only one '1':

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

Using the technique n & (n-1) simplifies this (note the operator precedence, parentheses cannot be omitted):

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

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

class Solution:
    def isPowerOfTwo(self, 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:

A number XORed with itself results in 0, i.e., a ^ a = 0; a number XORed with 0 results in itself, i.e., a ^ 0 = a.

Finding the Element that Appears 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, XOR all the numbers. Pairs of numbers will result in 0, and the single number XORed with 0 will still be itself. Therefore, the final XOR result is the element that appears only once:

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

#include <vector>

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

class Solution:
    def singleNumber(self, 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) {
    let res = 0;
    for (let n of nums) {
        res ^= n;
    }
    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, its indices should be [0,n), but you need to accommodate n + 1 elements [0,n]. Hence, one element will be missing. Please find this missing element.

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

Alternatively, leveraging data structures, use a HashSet to store the numbers present in the array, then traverse the numbers in [0,n] and check the HashSet to 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 requires O(N) space complexity to store the HashSet.

There is actually a particularly simple solution to this problem: the arithmetic sequence sum formula.

The problem can be understood as: there is an arithmetic sequence 0, 1, 2,..., n, with one number missing. Find this number, which 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 rigor
    // 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 rigor
    // 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 overflow
    # 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 overflow
    // 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 rigor
    // 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.

Review the properties of the XOR operation: a number XORed with itself results in 0, and a number XORed with 0 remains unchanged.

Moreover, XOR operation is commutative and associative, meaning:

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

This problem can be solved cleverly using these properties. For instance, consider nums = [0,3,1,4]:

To make it easier to understand, let's assume we add an index and let each element correspond to its equal index:

After doing this, you can see that all indices and elements form pairs, except for the missing element. Now, if we find the single index 2, we find the missing element.

How do we find this lone number? By XORing all elements and indices, paired numbers will cancel out to 0, leaving the single element, achieving our goal:

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

#include <vector>
using namespace std;

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

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

Since XOR is commutative and associative, paired numbers will always cancel out, leaving the missing element.

At this point, most common bit manipulation techniques have been covered. These techniques are easy for those who know and difficult for those who don't. There's no need to memorize them; just having an impression is sufficient.