如何通过位运算巧解编程题
概念
位运算是一种针对于小于一个字节数据进行的数学运算。计算机编程中，需要进行位运算的操作包括底层硬件控制，错误检测与修正算法，数据压缩，加密算法，优化等。对于大多数其他任务来讲，现代编程语言使得程序员可以直接对高层次的抽象进行操作而不用直接进行位操作。在源码中，主要用到的位操作包括了：AND，OR，XOR，NOT,和按位移。
由于位运算中对位的处理是并行的，所以位操作在某些情况下可以省去某些操作中对于数据结构的循环便利从而提高运算效率。但同时，位操作使得代码变得难以理解与维护。
基础
位运算中包括了一些不同的作用于位级别的操作，这些操作非常快，可以用于优化时间复杂度。一些基本的位操作包括了以下一些：
NOT(~) : 按位取反返回一个数字的补数，例如如果某一位是0，它会将其变成1，反之亦然。
N = 5 = (101)2
~N = ~5 = ~(101)2 = (010)2 = 2
AND(&) : 按位与是一个作用于相同长度位模式的二元操作符。只在参与比较的两个位同为1时，返回1，否则返回0。
A = 5 = (101)2 , B = 3 = (011)2
A & B = (101)2 & (011)2= (001)2 = 1
OR(|) : 按位或同样也是作用于两个相同位长度数字的二元操作符，当参与比较的两个位其中有一个为1时，返回1，当两个位都是0时，返回0。
A = 5 = (101)2 , B = 3 = (011)2
A | B = (101)2 | (011)2 = (111)2 = 7
XOR(^) : 异或同为二元操作符，当两个参与比较的位不同时返回1，否则返回0。
A = 5 = (101)2 , B = 3 = (011)2
A ^ B = (101)2 ^ (011)2 = (110)2 = 6
Left Shift (<<) : 左移操作符是一个二元操作符，其将操作数字按位左移一定位数并在末尾补0。左移操作相当于操作数与2k相乘（k为左移位数）。
1 << 1 = 2 = 21
1 << 2 = 4 = 22
1 << 3 = 8 = 23
…
1 << n = 2n
Right Shift (>>) : 右移操作符同为二元操作符，其将作用数字按位向右移动，并在末端补首位补0。右移操作相当于操作数与2k相除（k为右移位数）。
4 >> 1 = 2
6 >> 1 = 3
5 >> 1 = 2
16 >> 4 = 1
| X | Y | X&Y | X/ | Y | X^Y |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
应用示例
-
计算一个数字的二进制表示中有多少个一
//每一次n&(n-1)操作 都从末尾向前去掉一个1 直到数字减少为0 int count_one(int n) { while(n) { n = n&(n-1); count++; } return count; } -
判断是否是为4次冪
//!(n&(n-1))确定二进制中只有一个1，n&0x55555555确定1的位置 bool isPowerOfFour(int n) { return !(n&(n-1)) && (n&0x55555555); //check the 1-bit location; } -
使用^与&运算将两个数字相加
// 通过a^b得到没有进位的结果，通过a&b得到进位，递归相加 int getSum(int a, int b) { return b==0? a:getSum(a^b, (a&b)<<1); //be careful about the terminating condition; } -
从一个连续数组0,1,2,3,...,n中，找出缺少的一个数字，例如num=[0,1,3],则返回2。
//由于相同的数字会因为^抵消，所以ret最后返回的是缺少数字与数组中最大数的^，这时候在与数组中最大数做^，很自然的得到缺少的数字。 int missingNumber(vector<int>& nums) { int ret = 0; for(int i = 0; i < nums.size(); ++i) { ret ^= i; ret ^= nums[i]; } return ret^=nums.size(); } -
找到最接近给定数字N的2的n词幂
//实际就是定位数字最大端1的位置，将所有位置1后加一右移，即得到答案 long largest_power(long N) { //changing all right side bits to 1. N = N | (N>>1); N = N | (N>>2); N = N | (N>>4); N = N | (N>>8); N = N | (N>>16); return (N+1)>>1; }N | (N>>1）后
N | (N>>4) 后
N | (N>>4) 后
N | (N>>8)后
-
将一个无符号32位数字的所有位取反
//从左到右遍历N并从右到左置res中的1，或者相反方向。 uint32_t reverseBits(uint32_t n) { unsigned int mask = 1<<31, res = 0; for(int i = 0; i < 32; ++i) { if(n & 1) res |= mask; mask >>= 1; n >>= 1; } return res; } uint32_t reverseBits(uint32_t n) { uint32_t mask = 1, ret = 0; for(int i = 0; i < 32; ++i){ ret <<= 1; if(mask & n) ret |= 1; mask <<= 1; } return ret; } x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); -
给定范围[m,n],且0<=m<=n<=2147483647,返回范围内所有整数按位与的结果，如给定范围[5,7]，则返回4。
int rangeBitwiseAnd(int m, int n) { int a = 0; while(m != n) { m >>= 1; n >>= 1; a++; } return m<<a; } -
验证一个给定数字是否是2的n次方
//2的n次方的二进制表达中只会有1个1，而-1操作会将从左向右遇到的第一个变成0，而这一位之前的数字变成1 //所以如果X只有一个1，那么-1后，除了1的那一位，其他都会变为1，这样两个数字求与，应该得到0. bool isPowerOfTwo(int x) { // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not return (x && !(x & (x - 1))); } -
写一个程序返回无符号数里有多少个1
//参照上一题，只要N&(N-1)仍然大于0，即可知，N中仍然有1存在。 int hammingWeight(uint32_t n) { int count = 0; while(n) { n = n&(n-1); count++; } return count; }int hammingWeight(uint32_t n) { ulong mask = 1; int count = 0; for(int i = 0; i < 32; ++i){ //31 will not do, delicate; if(mask & n) count++; mask <<= 1; } return count; } -
如果得到一个集合的所有子集
一个大小为N的集合，有2n个可能的子集，如果把每一个元素当做一个位，2N的二进制表达正好有N位，把某一位值为1当做存在，值为0时当做不存在，以此正好可以通过二进制表达来确定每一个子集的元素。
possibleSubsets(A, N):
for i = 0 to 2^N:
for j = 0 to N:
if jth bit is set in i:
print A[j]
print ‘\n’
- 返回X二进制表示中最靠右的一个1
//x-1 将最靠右的一个1置0，并将从这个1一直到最右的位置1，与x进行与操作后，实际上是将最右的一个1置0，与原数字异或操作后，得到这个1。
int rightMostOne(int x){
return x^x&(x-1)；
}
// -x = ~x + 1 所以 -x 除了最右的一个1，和这个1往右的所有数字与原数相等，
int rightMostOne(int x){
return x&(-x);
}
网友评论