如何通過(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)₂

~N = ~5 = ~(101)₂ = (010)₂ = 2

AND(&) : 按位與是一個(gè)作用于相同長(zhǎng)度位模式的二元操作符。只在參與比較的兩個(gè)位同為1時(shí)，返回1，否則返回0。

A = 5 = (101)₂ , B = 3 = (011)₂

A & B = (101)₂ & (011)₂= (001)₂ = 1

OR(|) : 按位或同樣也是作用于兩個(gè)相同位長(zhǎng)度數(shù)字的二元操作符，當(dāng)參與比較的兩個(gè)位其中有一個(gè)為1時(shí)，返回1，當(dāng)兩個(gè)位都是0時(shí)，返回0。

A = 5 = (101)₂ , B = 3 = (011)₂

A | B = (101)₂ | (011)2 = (111)₂ = 7

XOR(^) : 異或同為二元操作符，當(dāng)兩個(gè)參與比較的位不同時(shí)返回1，否則返回0。

A = 5 = (101)₂ , B = 3 = (011)₂

A ^ B = (101)₂ ^ (011)₂ = (110)₂ = 6

Left Shift (<<) : 左移操作符是一個(gè)二元操作符，其將操作數(shù)字按位左移一定位數(shù)并在末尾補(bǔ)0。左移操作相當(dāng)于操作數(shù)與2^k相乘（k為左移位數(shù)）。

1 << 1 = 2 = 2¹

1 << 2 = 4 = 2²

1 << 3 = 8 = 2³

…

1 << n = 2ⁿ

Right Shift (>>) : 右移操作符同為二元操作符，其將作用數(shù)字按位向右移動(dòng)，并在末端補(bǔ)首位補(bǔ)0。右移操作相當(dāng)于操作數(shù)與2^k相除（k為右移位數(shù)）。

4 >> 1 = 2

6 >> 1 = 3

5 >> 1 = 2

16 >> 4 = 1

應(yīng)用示例

1. 計(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;
     }
   

2. 判斷是否是為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;
   }
   

3. 使用^與&運(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;
   }
   

4. 從一個(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();
   }
   

5. 找到最接近給定數(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)后

6. 將一個(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);
   

7. 給定范圍[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; 
   }
   

8. 驗(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)));
   }
   

9. 寫(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;
   }
   

10. 如果得到一個(gè)集合的所有子集
    一個(gè)大小為N的集合，有2ⁿ個(gè)可能的子集，如果把每一個(gè)元素當(dāng)做一個(gè)位，2^N的二進(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’

11. 返回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);
}