位操作

发表于   |  

  • 计算二进制中1的个数

    实质是求该二进制数与0的hamming距离，详见wiki。其分治解法 按位分片 统计1的个数：

      count 1s in each  2-bit piece
  count 1s in each  4-bit piece
  count 1s in each  8-bit piece
  count 1s in each 16-bit piece
  count 1s in each 32-bit piece

    The best solutions known are based on adding counts in a tree pattern.

      /*
   * For example, to count the number of 1 bits in the 8-bit binary number A=01101100
   * | Expression            | Binary   | Decimal | Comment                          |
   * | A                     | 01101100 |         | the original number              |
   * | B = A & 01010101      | 01000100 | 1,0,1,0 | every other bit from A           |
   * | C = (A>>1) & 01010101 | 00010100 | 0,1,1,0 | remaining bits from A            |
   * | D = B + C             | 01011000 | 1,1,2,0 | # of 1s in each 2-bit piece of A | 
   * | E = D & 00110011      | 00010000 | 1,0     | every other count from D         |
   * | F = (D>>2) & 00110011 | 00010010 | 1,2     | remaining counts from D          |
   * | G = E + F             | 00100010 | 2,2     | # of 1s in each 4-bit piece of A |
   * | H = G & 00001111      | 00000010 | 2       | every other count from G         |
   * | I = (G>>4) & 00001111 | 00000010 | 2       | remaining counts from G          |
   * | J = H + I             | 00000100 | 4       | the final answer                 |

  typedef unsigned int uint32;
  const uint32 m1  = 0x55555555; //binary: 0101...
  const uint32 m2  = 0x33333333; //binary: 00110011..
  const uint32 m4  = 0x0f0f0f0f; //binary: 0000111100001111..
  const uint32 m8  = 0x00ff00ff; //binary: 00000000111111110000000011111111
  const uint32 m16 = 0x0000ffff; //binary: 00000000000000001111111111111111

  int population_count(uint32 x) {
      x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
      x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
      x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
      x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
      x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
      return x;
  }

    平时常见的解法：

    This better when most bits in x are 0.

      int population_count(uint32 x) {
      int count;
      for (count = 0; x; count++) {
         x &= x-1; // zero out the least significant bit
      }
      return count;
  }

least significant bit

  • -x # == ~x+1, 末位1前头的按位取反

  • x&-x # 末位1

  • x-1 # 末位1起按位取反

  • x&(x-1) # 去掉末位1

  • (x&(x-1)) == 0 # 是2的幂

most significant bit

  • 首位1起全置1

      inline uint32 set_bits_from_msb(uint32 x) {
      x |= (x >> 1);
      x |= (x >> 2);
      x |= (x >> 4);
      x |= (x >> 8);
      x |= (x >> 16);
      return x;
  }

  • 首位1

      uint32 msb(uint32 x) {
      x = set_bits_from_msb(x);
      return x & ~(x >> 1);
  }

  • 下个最近2的幂

      uint32 next_largest_power_of_2(uint32 x) {
      x = set_bits_from_msb(x);
      return x+1;
  }

  • log2的floor

      uint32 floor_of_log2(uint32 x) {
      x = set_bits_from_msb(x);
      return population_count(x) - 1;
  }

Reference