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 tricks are not so useful, this seventh trick is actually practical. It uses the sign bit in two's complement encoding. In integer encoding, the highest bit is the sign bit. Negative numbers have a sign bit of 1, while non-negative numbers have a sign bit of 0. With the help of xor, you can check if two numbers have different signs.

If you don't use bitwise operations to check the sign, you need to use if-else statements, which is more troublesome. You may also think about using multiplication to check, but this could cause integer overflow and lead to errors.

Modulo with Powers of Two

For "modulo (remainder)" operations, we usually use the % operator. But you may have seen the & (bitwise and) operator in some code (like the source code of HashMap). This is actually an optimization trick.

When the modulus m is a power of two, x % m is the same as x & (m - 1).

Bitwise & is much faster than %, so this trick is useful in performance-sensitive cases.

A common situation is a circular (ring) array. Usually, to loop the index within [0, arr.length - 1], we use the modulo operator:

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

If the array length is exactly a power of two, you can use the bitwise & to optimize the modulo operation:

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

To put it simple, & (arr.length - 1) can replace % arr.length in modulo, and it is faster.

Now, here is a question. When you keep doing index++, you can loop through the array. But what if you do index--? Can it still work as a circular array?

The answer: If you use % for modulo, when index is less than 0, the result will be negative and needs special handling. But if you use &, index will not be negative and still works as expected:

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

When writing your own code, you may not use this trick often. But you might see it in third-party libraries. Just remember it, so you won't be confused when you see it.

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.