# 常用的位操作

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

136. Single Number | 🟢 |

191. Number of 1 Bits | 🟢 |

231. Power of Two | 🟢 |

268. Missing Number | 🟢 |

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

重要

Note that this technique only works when the array length is a power of 2, such as 2, 4, 8, 16, 32, and so on. As for how to extend the array length to a power of 2, there are clever bit manipulation algorithms for this, which you can refer to at https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2

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

## Application of `n & (n-1)`

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

A picture can help you understand this easily:

The core logic is that `n - 1`

will always remove the last `1`

and turn all the zeros after it into ones. When you perform an `&`

operation with `n`

, it will only change the last `1`

to `0`

.

### Calculating Hamming Weight

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

**191. Number of 1 Bits** | 力扣 | LeetCode |

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

**Example 1:**

**Input:** n = 11

**Output:** 3

**Explanation:**

The input binary string **1011** has a total of three set bits.

**Example 2:**

**Input:** n = 128

**Output:** 1

**Explanation:**

The input binary string **10000000** has a total of one set bit.

**Example 3:**

**Input:** n = 2147483645

**Output:** 30

**Explanation:**

The input binary string **1111111111111111111111111111101** has a total of thirty set bits.

**Constraints:**

`1 <= n <= 2`

^{31}- 1

**Follow up:**If this function is called many times, how would you optimize it?

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":

**136. Single Number** | 力扣 | LeetCode |

Given a **non-empty** array of integers `nums`

, every element appears *twice* except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

Input:nums = [1]Output:1

**Constraints:**

`1 <= nums.length <= 3 * 10`

^{4}`-3 * 10`

^{4}<= nums[i] <= 3 * 10^{4}- Each element in the array appears twice except for one element which appears only once.

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":

**268. Missing Number** | 力扣 | LeetCode |

Given an array `nums`

containing `n`

distinct numbers in the range `[0, n]`

, return *the only number in the range that is missing from the array.*

**Example 1:**

Input:nums = [3,0,1]Output:2Explanation: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.

**Example 2:**

Input:nums = [0,1]Output:2Explanation: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.

**Example 3:**

Input:nums = [9,6,4,2,3,5,7,0,1]Output:8Explanation: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.

**Constraints:**

`n == nums.length`

`1 <= n <= 10`

^{4}`0 <= nums[i] <= n`

- All the numbers of
`nums`

are**unique**.

**Follow up:** Could you implement a solution using only `O(1)`

extra space complexity and `O(n)`

runtime complexity?

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 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 bitwise operations. Let's talk about how to use bitwise operation techniques to solve this problem.

Let's review the properties of the XOR operation: the result of XORing a number with itself is 0, and XORing a number with 0 yields the number itself.

Moreover, the XOR operation satisfies the commutative and associative laws, which means:

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

These properties can be cleverly used to find the missing element in this problem. For example, consider `nums = [0,3,1,4]`

:

To make it easier to understand, let's assume we first add an extra bit to the indices, and then pair each element with its corresponding index:

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

How do we find this unpaired number? **Simply XOR all the elements and indices together. The paired numbers will cancel out to 0, leaving only the unpaired 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.

**引用本文的题目**

**安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：**

LeetCode | 力扣 |
---|---|

1457. Pseudo-Palindromic Paths in a Binary Tree | 1457. 二叉树中的伪回文路径 |

389. Find the Difference | 389. 找不同 |

- | 剑指 Offer 15. 二进制中1的个数 |