引言

一个引例:怎样最快的把 2 变成 8 。答案并不是 2×4 。由于计算机是二进制工作的,2 的二进制代码为 0000 0010 而 8 的二进制代码为 0000 0100。 最简单的方式便是把 1 向左边移动一个单位,即位运算。

最近在知乎上看到了一个关于位运算的话题,我便一时兴起对位运算有关的算法技巧进行了整理。位操作是一种很底层的操作二进制数据的方法。我们先介绍其在程序中的奇技淫巧的应用,最后根据几道LeetCode的算法题来总结升华。此外,位运算(Bit Manipulation)一直是程序员面试中的一个必须准备的主题, 不过现在面试中位运算出现的次数并不多,主要原因还是位运算太考察技巧了,很多时候很难在面试的短时间内想出来,所以作为面试的题目显得有点太花时间了。位运算的主要思想是五种运算:与(&),或(|),异或(^),左移(<<),右移(>>)。位运算的常用技巧可叙述如下:

  • n &(n-1)能够消灭n中最右侧的一个1。
  • 右移:除以2, 左移:乘以2。
  • 异或性质:交换律,0^a=a, a^a=0;

这些性质看起来都很简单,我们在C语言课程中都接触过,但是当位运算与算法结合,就会有一系列奇妙的应用。我们先来看几个十分典型的例子,再来看对应的LeetCode习题。

位运算的奇技淫巧

判断奇偶数

判断一个数是基于还是偶数,相信很多人都做过,一般的做法的代码如下

1
2
3
if( n % 2) == 1{
// n 是个奇数
}

如果把 n 以二进制的形式展示的话,其实我们只需要判断最后一个二进制位是 1 还是 0 就行了,如果是 1 的话,代表是奇数,如果是 0 则代表是偶数,所以采用位运算的方式的话,代码如下:

1
2
3
if(n & 1 == 1){
// n 是个奇数。
}

值得指出的是,当我们写成 n % 2 的形式,一部分编译器也会自动帮我们优化成位运算。这种运算效率高于之前的n%2的形式。

变换符号

变换符号显然很简单,根据类似补码的知识,对原数取反加一就可以了。不再赘述。

两数交换

交换两个数相信很多人在接触C语言时就写过,教科书上的思路是使用一个额外来变量来辅助交换,例如,我们要交换 x 与 y 值,传统代码如下:

1
2
3
int tmp = x;
x = y;
y = tmp;

这样写有问题吗?没问题,通俗易懂,万一哪天有人要为难你,不允许你使用额外的辅助变量来完成交换呢?你还别说,有人面试确实被问过,这个时候,位运算大法就来了。代码如下:

1
2
3
x = x ^ y   // (1)
y = x ^ y // (2)
x = x ^ y // (3)

只要三个 x ^ y,就莫名交换成功了。简单解释如下:我们知道,两个相同的数异或之后结果会等于 0,即 n ^ n = 0。并且任何数与 0 异或等于它本身,即 n ^ 0 = n。所以,解释如下:

把(1)中的 x 带入 (2)中的 x,有

y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。

对于(3),推导如下:

x = x^y = (x^y)^x = (x^x)^y = 0^y = y。

这里补充说明一下,异或运算是支持运算的交换律和结合律的。

找出没有重复的数

有一组整型数据,其中有一个数只出现了一次,其他的数都出现了两次,设计算法找出这个数 。

教科书式的思路是用一个哈希表来存储,每次存储的时候,记录某个数出现的次数,最后再遍历哈希表,看看哪个数只出现了一次。这种方法的时间复杂度为 O(n),空间复杂度也为 O(n)了。然而这道题也是可以采用位运算来处理的。不难知道,两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,所以我们把这一组整型全部异或一下,例如这组数据是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,由于异或支持交换律和结合律,所以把他们全部异或一下,结果如下:1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。也就是说,那些出现了两次的数异或之后会变成0,那个出现一次的数,和 0 异或之后就等于它本身。这个解法对应代码如下:

1
2
3
4
5
6
7
int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
tmp = tmp ^ arr[i];
}
return tmp;
}

时间复杂度为 O(n),空间复杂度为 O(1)。

不借助pow函数计算乘方

例如求解 3 的 n 次方,并且不能使用系统自带的 pow 函数,你会怎么做呢?题目与 LeetCode 上231号题:2 的幂有异曲同工之妙:给定一个整数,编写一个函数来判断它是否是 2 的幂次方。回到这道题目上来,也许你会让连续 n 个 3 相乘。不过这样做时间复杂度为 O(n) ,如果用位运算来做,又会怎么样呢?例如 令n = 13,则 n 的二进制表示为 1101, 那么 3 的 13 次方可以拆解为:3^1101 = 3^0001 * 3^0100 * 3^1000。也就是说我们可以通过 & 1和 >>1 来逐位读取 1101,为1时将该位代表的乘数累乘到最终结果。代码如下,时间复杂度优化为 O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
int pow(int n){
int sum = 1;
int tmp = 3;
while(n != 0){
if(n & 1 == 1){
sum *= tmp;
}
tmp *= tmp;
n = n >> 1;
}

return sum;
}

我们已经看出,位运算很多情况下都与二进制密切相关,所以我们要判断是否位运算,很多情况下都会把他们拆分成二进制,观察特性,或者就是利用与,或,异或的特性来观察,总之,多看一些例子并多动手,就比较容易上手了。

找出不大于N的最大的2的幂指数

传统的做法就是让 1 不断着乘以 2,代码如下:

1
2
3
4
5
6
7
8
9
int findN(int N){
int sum = 1;
while(true){
if(sum * 2 > N){
return sum;
}
sum = sum * 2;
}
}

这样做时间复杂度是 O(logn),如果改成位运算呢?如果要使用位运算,很多时候我们把某个数拆成二进制,然后看看有哪些发现。例如令 N = 19,那么转换成二进制就是 00010011。不难看出,我们要找的数就是,把二进制中最左边的 1 保留,后面的 1 全部变为 0。即我们的目标数是 00010000。问题就变成了如何获得这个数。相应解法为:首先找到最左边的 1,然后把它右边的所有 0 变成 1;其次把得到的数值加 1,可以得到 00100000即 00011111 + 1 = 00100000;最后把得到的 00100000 向右移动一位,即可得到 00010000,即 00100000 >> 1 = 00010000。找到了思路,新的问题来了,第一步中把最左边 1 中后面的 0 转化为 1 该怎么处理呢?我们来看代码:

1
2
3
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;

就是通过把 n 右移并且做运算即可得到。例如:我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后,那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算,那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理,再次把 n 右移两位,那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算,那么就能得到第 k, k+1, k+2, k+3 都是 1,如此往复下去….最终的代码如下

1
2
3
4
5
6
7
int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8 // 整型一般是 32 位,上面我是假设 8 位。
return (n + 1) >> 1;
}

这种做法的时间复杂度近似 O(1)。

n 皇后问题的再探讨

这一部分我主要学习了一篇知乎文章:用位运算速解 n 皇后问题,受篇幅所限,这里不重复搬运这篇文章,有兴趣的读者可以通过链接进入这篇文章进行阅读。在这个案例中,作者介绍了n皇后问题的五种越来越快的解法。 位运算对提高速度起了关键作用。

下面我们来看几个LeetCode中的位运算题目。

LeetCode习题 | 位运算之数学运算与位运算

29.Divide Two Integers

Divide two integers without using multiplication, division and mod operator.If it is overflow, return MAX_INT.

题目要求:这道题让我们求两数相除,而且规定我们不能用乘法,除法和取余操作。

不借助位运算的解法

题目分析:使用减法和ln函数。。就是$e^{(lna-lnb)}=e^{ln(a/b)}= a/b$.似乎也符合题目要求

题目解答:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int divide(int dividend, int divisor) {
if(divisor == 0 || dividend == INT_MIN && divisor == -1) return INT_MAX;
int sign = ((dividend >> 31) ^ (divisor >> 31)) == 0 ? 1 : -1;
long a = abs((long)dividend);
long b = abs((long)divisor);
double c = exp(log(a) - log(b)) + 0.0000000001;
return (int)(sign * c);
}
};

借助位运算的解法

题目分析:上面的解法多少有些投机取巧的嫌疑,下面我们借助位操作,如果被除数大于或等于除数,则进行如下循环,定义变量m等于除数,定义计数n,当m的两倍小于等于被除数时,进行如下循环,m扩大一倍,n扩大一倍,然后更新res和dvd。然后我们还要根据被除数和除数的正负来确定返回值的正负,这里我们采用长整型long long来完成所有的计算,最后返回值乘以符号即可。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int divide(int dividend, int divisor) {
long long dvd = abs((long long)dividend), dvs = abs((long long)divisor), res = 0;
if (dvd < dvs) return 0;
while(dvd >= dvs){
long long m = dvs, n = 1;
while(dvd > (m << 1)){
m <<= 1;
n <<= 1;
}
res += n;
dvd -= m;
}
if((dividend < 0)^(divisor < 0)) res = -res;
return res > INT_MAX ? INT_MAX : res;
}
};

201.Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.For example, given the range [5, 7], you should return 4

题目要求:给一个范围,返回这个范围中所有的数按位相与最后的结果。

题目分析:直觉上我们需要对所有的[m,n]范围内的数字进行遍历。其实并不需要这样,考虑到数组的数字是连续的,那么m,n范围内的二进制表示的末尾相同位置一定会出现不同的0,1。只要找出m,n的左边起的最长相同的二进制头部即可。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int res = 0, i = 0;
while(m != n){
m >>= 1;
n >>= 1;
i++;
}
res = m << i;
return res;
}
};

371.Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example:Given a = 1 and b = 2, return 3.

题目要求:实现两数相加,但是不能用加号或者其他什么数学运算符号。

题目分析:借助位运算。首先,已知异或(就是这个“^”符号)可以得到:
0^0 = 0;0^1 = 1;1^1 = 0
正是位相加时该位的结果(只不过还有个进位没加罢了),所以对于还没有加进位的result,result可以暂时等于a^b。其次,已知与运算(就是这个“&”符号)可以得到:0&0 = 0;0&1 = 0;1&1 = 1。正是位相加时候有进位的那一位标注为了1,但是进位是往前一个位相加上去的呀。,所以carry = (a & b) << 1。现在处理要把result加上进位的事情:如果进位carry等于0,那么不用加,直接等于result的值就好了。如果进位不等于0,那么就要把result和carry的值按位相加。按位相加的结果也可能导致进位,所以先用个临时变量temp把carry的值保存,然后令carry = (result & temp) << 1(也就是result和原来carry按位相加后进位的结果),然后result = result ^ temp(也就是result和原来carry按位相加的结果),不断循环往复,直到有一次carry等于0,不再需要进位了。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int getSum(int a, int b) {
int carry = (a & b) << 1;
int result = (a ^ b);
while(carry != 0) {
int temp = carry;
carry = (result & temp) << 1;
result = result ^ temp;
};
return result;
}
};

318.Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:
Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]
Return 16
The two words can be “abcw”, “xtfn”.
Example 2:
Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]
Return 4
The two words can be “ab”, “cd”.
Example 3:
Given [“a”, “aa”, “aaa”, “aaaa”]
Return 0
No such pair of words.

题目要求:给我们一个单词数组,求两个没有相同字母的单词的长度之积的最大值。

题目分析:网上的解法大多用了mask,因为题目中说都是小写字母,那么只有26位,一个整型数int有32位,我们可以用后26位来对应26个字母,若为1,说明该对应位置的字母出现过,那么每个单词的都可由一个int数字表示,两个单词没有共同字母的条件是这两个int数相与为0。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> v(words.size());
int result = 0;
for(int i = 0; i < words.size(); i++)
for(int j = 0; j < words[i].length(); j++)
v[i] = v[i] | 1 << (words[i][j] - 'a');
for(int i = 0; i < words.size(); i++)
for(int j = i + 1; j < words.size(); j++)
if((v[i] & v[j]) == 0)
result = max(result, (int)(words[i].length() * words[j].length()));
return result;
}
};

下面再看两道题,与前面的数学运算案例不同,前面的数学运算案例没有明显要求使用位运算的痕迹,而这里的题目明显可以看出需要使用位运算解决。

190.Reverse Bits

Reverse bits of a given 32 bits unsigned integer.For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

题目要求:把一个无符号int数字,按二进制位反转过来。

题目分析:通过移位操作,一位一位来处理。目的是反转,所以先处理最右位。最右位(末端)一个一个地往res的左边推。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for(int i = 0; i < 32; i++){
uint32_t temp = (n>>i) & 1;
res |= (temp<<(31-i));
}
return res;
}
};

476.Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

题目要求:给一个正整数,输出其补码数。 补码策略是反转其二进制表示的位。

题目分析:mask – 1为和num二进制位等长的所有位数为1的数,与num取^可以得到和num相反的数字。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int findComplement(int num) {
int temp = num, mask = 1;
while(temp != 0) {
temp = temp >> 1;
mask = mask << 1;
}
return num ^ (mask - 1);
}
};

LeetCode习题 | 位运算之Single Number系列

136.Single Number

Given an array of integers, every element appears twice except for one. Find that single one.Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目要求:给定一个整数数组,除了一个元素出现1次外,其他每个元素都会出现2次。 找到那个出现1次的整数。注意:时间复杂度必须是O(n),并且空间复杂度为O(1)

题目分析:由于题目对时间复杂度和空间复杂度有严格要求,因此不能使用sort排序方法,也不能使用map结构,只能另辟蹊径。把数组中所有的数字都异或起来,则每对相同的数字都会得0,然后最后剩下来的数字就是那个只有1次的数字。

题目解答:略,参见前文案例中代码

137.Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目要求:给定一个整数数组,除了一个元素出现3次外,其他每个元素都会出现2次。 找到那个出现3次的整数。注意:时间复杂度必须是O(n),并且空间复杂度为O(1)

题目分析:仿效前文的mask方法,我们可以建立一个32位的数字,来统计每一位上数字出现的个数,最后我们把每个数的对应位都加起来对3取余,最终剩下来的那个数就是单独的数字。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i < 32; i++){
int temp = 0;
for(auto n : nums){
temp += (n>>i) & 1;
}
temp %= 3;
res |= (temp<<i);
}
return res;
}
};

260.Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

题目要求:给定一个整数数组,除了两个元素各出现1次外,其他每个元素都会出现2次。 找到那两个出现1次的整数。

题目分析:我们先把原数组全部异或起来,得到一个数字,这个数字是两个不相同的数字异或的结果,我们取出其中任意一位为‘1’的位,为了方便起见,我们用 temp^(temp&(temp-1)) 来取出最右端为‘1’的位,然后和原数组中的数字挨个相与,那么我们要求的两个不同的数字就被分到了两个小组中,分别将两个小组中的数字都异或起来,就可以得到最终结果了。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res(2, 0);
int temp = 0;
for(auto n : nums){
temp ^= n;
}
int flag = temp^(temp&(temp-1));
for(auto n : nums){
if(flag & n) res[0] ^= n;
else res[1] ^= n;
}
return res;
}
};

LeetCode习题 | 位运算之Hamming weight系列

191.Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight). For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

题目要求:编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

题目分析:当然,可以利用for循环,统计整数二进制表达式32位中1的个数;但是,有一种更高效的方法:使用n&(n-1)的方法,去除bit位的最后1个1,发现有几个1,就循环几次n&(n-1),直到n等于0。

题目解答:

位运算版解法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while(n){
res++;
n = n & (n-1);
}
return res;
}
};

不借助位运算的解法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while(n != 0) {
ans = ans + n % 2;
n = n / 2;
}
return ans;
}
};

461.Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 2^31.

Example: Input: x = 1, y = 4 Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑The above arrows point to positions where the corresponding bits are different.

题目要求:求两个数字之间的汉明距离,即两个数二进制数对应位不同的个数。

题目分析:将两个数字异或,遍历异或结果的每一位,统计为1的个数。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingDistance(int x, int y) {
int res = 0, temp = x ^ y;
while(temp){
res++;
temp = temp & (temp-1);
}
return res;
}
};

477.Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example: Input: 4, 14, 2 Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note: Elements of the given array are in the range of 0 to 10^9. Length of the array will not exceed 10^4.

题目要求:给定一个int数组,求出数组中所有数值对汉明距离中总和。

题目分析:对数组中所有数字的同一个bit位,统计这个bit位上出现的1的次数count,那么这个bit位上出现的0的次数n-count,则总的汉明距离为count*(n-count),n是数组中元素的个数。

题目解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int res = 0;
for(int i = 0; i < 31; i++){
int cnt = 0;
for(auto n : nums){
if(n & 1<<i) cnt++;
}
res += cnt * (nums.size() - cnt);
}
return res;
}
};

总结

通过这些题目可以看到,很多位运算可以解决的题目其实不借助位运算也可以得到解决,但是利用位运算的方法不仅开阔了我们的思路,也会提高我们的算法效率。如果面试中遇到能提出位运算的解法也能加分不少,所以位运算的思想值得我们好好掌握。