如何通過(guò)位運(yùn)算巧解編程題
概念
位運(yùn)算是一種針對(duì)于小于一個(gè)字節(jié)數(shù)據(jù)進(jìn)行的數(shù)學(xué)運(yùn)算。計(jì)算機(jī)編程中歉提，需要進(jìn)行位運(yùn)算的操作包括底層硬件控制态兴，錯(cuò)誤檢測(cè)與修正算法狠持，數(shù)據(jù)壓縮，加密算法瞻润，優(yōu)化等喘垂。對(duì)于大多數(shù)其他任務(wù)來(lái)講，現(xiàn)代編程語(yǔ)言使得程序員可以直接對(duì)高層次的抽象進(jìn)行操作而不用直接進(jìn)行位操作绍撞。在源碼中正勒，主要用到的位操作包括了：AND，OR傻铣，XOR章贞，NOT,和按位移。
由于位運(yùn)算中對(duì)位的處理是并行的矾柜，所以位操作在某些情況下可以省去某些操作中對(duì)于數(shù)據(jù)結(jié)構(gòu)的循環(huán)便利從而提高運(yùn)算效率阱驾。但同時(shí)，位操作使得代碼變得難以理解與維護(hù)怪蔑。
基礎(chǔ)
位運(yùn)算中包括了一些不同的作用于位級(jí)別的操作里覆，這些操作非常快缆瓣，可以用于優(yōu)化時(shí)間復(fù)雜度喧枷。一些基本的位操作包括了以下一些：
NOT(~) : 按位取反返回一個(gè)數(shù)字的補(bǔ)數(shù)，例如如果某一位是0，它會(huì)將其變成1隧甚，反之亦然车荔。
N = 5 = (101)2
~N = ~5 = ~(101)2 = (010)2 = 2
AND(&) : 按位與是一個(gè)作用于相同長(zhǎng)度位模式的二元操作符。只在參與比較的兩個(gè)位同為1時(shí)戚扳，返回1忧便，否則返回0。
A = 5 = (101)2 , B = 3 = (011)2
A & B = (101)2 & (011)2= (001)2 = 1
OR(|) : 按位或同樣也是作用于兩個(gè)相同位長(zhǎng)度數(shù)字的二元操作符帽借，當(dāng)參與比較的兩個(gè)位其中有一個(gè)為1時(shí)珠增，返回1，當(dāng)兩個(gè)位都是0時(shí)砍艾，返回0蒂教。
A = 5 = (101)2 , B = 3 = (011)2
A | B = (101)2 | (011)2 = (111)2 = 7
XOR(^) : 異或同為二元操作符，當(dāng)兩個(gè)參與比較的位不同時(shí)返回1脆荷，否則返回0凝垛。
A = 5 = (101)2 , B = 3 = (011)2
A ^ B = (101)2 ^ (011)2 = (110)2 = 6
Left Shift (<<) : 左移操作符是一個(gè)二元操作符，其將操作數(shù)字按位左移一定位數(shù)并在末尾補(bǔ)0蜓谋。左移操作相當(dāng)于操作數(shù)與2k相乘（k為左移位數(shù)）梦皮。
1 << 1 = 2 = 21
1 << 2 = 4 = 22
1 << 3 = 8 = 23
…
1 << n = 2n
Right Shift (>>) : 右移操作符同為二元操作符，其將作用數(shù)字按位向右移動(dòng)桃焕，并在末端補(bǔ)首位補(bǔ)0届氢。右移操作相當(dāng)于操作數(shù)與2k相除（k為右移位數(shù)）。
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 |
應(yīng)用示例
-
計(jì)算一個(gè)數(shù)字的二進(jìn)制表示中有多少個(gè)一
//每一次n&(n-1)操作 都從末尾向前去掉一個(gè)1 直到數(shù)字減少為0 int count_one(int n) { while(n) { n = n&(n-1); count++; } return count; } -
判斷是否是為4次冪
//!(n&(n-1))確定二進(jìn)制中只有一個(gè)1覆旭，n&0x55555555確定1的位置 bool isPowerOfFour(int n) { return !(n&(n-1)) && (n&0x55555555); //check the 1-bit location; } -
使用^與&運(yùn)算將兩個(gè)數(shù)字相加
// 通過(guò)a^b得到?jīng)]有進(jìn)位的結(jié)果，通過(guò)a&b得到進(jìn)位岖妄，遞歸相加 int getSum(int a, int b) { return b==0? a:getSum(a^b, (a&b)<<1); //be careful about the terminating condition; } -
從一個(gè)連續(xù)數(shù)組0,1,2,3,...,n中型将，找出缺少的一個(gè)數(shù)字，例如num=[0,1,3],則返回2荐虐。
//由于相同的數(shù)字會(huì)因?yàn)閊抵消七兜，所以ret最后返回的是缺少數(shù)字與數(shù)組中最大數(shù)的^，這時(shí)候在與數(shù)組中最大數(shù)做^福扬，很自然的得到缺少的數(shù)字腕铸。 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(); } -
找到最接近給定數(shù)字N的2的n詞冪
//實(shí)際就是定位數(shù)字最大端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)后
-
將一個(gè)無(wú)符號(hào)32位數(shù)字的所有位取反
//從左到右遍歷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,返回范圍內(nèi)所有整數(shù)按位與的結(jié)果汽烦，如給定范圍[5,7]涛菠，則返回4。
int rangeBitwiseAnd(int m, int n) { int a = 0; while(m != n) { m >>= 1; n >>= 1; a++; } return m<<a; } -
驗(yàn)證一個(gè)給定數(shù)字是否是2的n次方
//2的n次方的二進(jìn)制表達(dá)中只會(huì)有1個(gè)1，而-1操作會(huì)將從左向右遇到的第一個(gè)變成0俗冻，而這一位之前的數(shù)字變成1 //所以如果X只有一個(gè)1礁叔，那么-1后，除了1的那一位迄薄，其他都會(huì)變?yōu)?琅关，這樣兩個(gè)數(shù)字求與，應(yīng)該得到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))); } -
寫(xiě)一個(gè)程序返回?zé)o符號(hào)數(shù)里有多少個(gè)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; } 如果得到一個(gè)集合的所有子集
一個(gè)大小為N的集合都毒，有2n個(gè)可能的子集，如果把每一個(gè)元素當(dāng)做一個(gè)位碰缔，2N的二進(jìn)制表達(dá)正好有N位账劲，把某一位值為1當(dāng)做存在，值為0時(shí)當(dāng)做不存在金抡，以此正好可以通過(guò)二進(jìn)制表達(dá)來(lái)確定每一個(gè)子集的元素瀑焦。
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二進(jìn)制表示中最靠右的一個(gè)1
//x-1 將最靠右的一個(gè)1置0，并將從這個(gè)1一直到最右的位置1梗肝，與x進(jìn)行與操作后榛瓮，實(shí)際上是將最右的一個(gè)1置0，與原數(shù)字異或操作后巫击，得到這個(gè)1禀晓。
int rightMostOne(int x){
return x^x&(x-1)；
}
// -x = ~x + 1 所以 -x 除了最右的一個(gè)1坝锰，和這個(gè)1往右的所有數(shù)字與原數(shù)相等粹懒，
int rightMostOne(int x){
return x&(-x);
}
