二进制下去掉数字最后一个1

1

x &= x-1;

计算数的二进制表示中有多少个1

略蠢一些的遍历方法

1
2
3
4
5
6
7
8
9

int BitCount(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&(n-1)操作 都从末尾向前去掉一个1 直到数字减少为0

1
2
3
4
5
6
7

int BitCount(int n) {
  while(n) {
      n = n&(n-1);
      count++;
  }
  return count;
}

分治

算法思路是先求得局部个数在整合：

| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 0 1 | 1 0 | 0 0 | 0 1 |
| 0 0 1 1 | 0 0 0 1 |
| 0 0 0 0 0 1 0 0 |

① 第一次按1-bit划分，将成对相邻的两个1-bit相加即为每2-bit中’1’的个数。由于两位中’1’的个数最多为2所以2-bit可以表示；
② 按2-bit划分，相邻两个2-bit相加即为每4-bit中’1’的个数。同样不会溢出。
③ 按4-bit划分…
④ 最后就能得到整个二进制中’1’的个数。

以32位为例的代码如下，计算时间复杂度常数且不需临时变量。

1
2
3
4
5
6
7
8

int BitCount(int n)  {  
    n=(n & 0x55555555) + ((n>>1) & 0x55555555);  
    n=(n & 0x33333333) + ((n>>2) & 0x33333333);  
    n=(n & 0x0f0f0f0f) + ((n>>4) & 0x0f0f0f0f);  
    n=(n & 0x00ff00ff) + ((n>>8) & 0x00ff00ff);  
    n=(n & 0x0000ffff) + ((n>>16) & 0x0000ffff);  
    return n;  
}

使用^与&运算将两个数字相加

异或运算又被称为半加运算，即没有进位的加法

1
2
3
4
5

// 通过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;
}

找到最接近给定数字的2ⁿ

1
2
3
4
5
6
7
8
9
10

//实际就是定位数字最大端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;
}

判断数字是否是2ⁿ

1
2
3
4
5
6

//如果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)));
}

判断数字是否是4ⁿ

1
2
3
4
5

//!(n&(n-1))确定二进制中只有一个1，n&0x55555555确定1的位置
bool isPowerOfFour(int n) {
    return !(n&(n-1)) && (n&0x55555555);
    //check the 1-bit location;
}

返回数字二进制表示中最右侧的1

1
2
3
4
5
6
7
8
9

//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);
}

将二进制逆序

算法原理是先局部交换整合完成整体交换：

| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 0 1 | 1 1 | 0 0 | 0 1 |
| 1 1 0 1 | 0 1 0 0 |
| 0 1 0 0 1 1 0 1 |

① 第一次按1-bit划分，将成对相邻的两个1-bit交换。
② 按2-bit划分，相邻两个2-bit交换。
③ 按4-bit划分…
④ 最后就能得到逆序二进制。

以32位为例的代码如下，计算时间复杂度常数且不需临时变量。

1
2
3
4
5
6
7
8

int BitReverse(usigned int n)  {  
    n=((n & 0x55555555)<<1) | ((n & 0xaaaaaaaa)>>1);  
    n=((n & 0x33333333)<<2) | ((n & 0xcccccccc)>>2);  
    n=((n & 0x0f0f0f0f)<<4) | ((n & 0xf0f0f0f0)>>4);  
    n=((n & 0x00ff00ff)<<8) | ((n & 0xff00ff00)>>8);  
    n=((n & 0x0000ffff)<<16) | ((n & 0xffff0000)>>16);  
    return n;  
}

计算绝对值

1
2
3
4
5
6
7
8

 //因为i为0或-1，所以减i即是要么加0要么加1  
int my_abs(int a) //正数的时候，比较好理解  
{  
    int i = a >> 31;  
    //负数的时候，右移数值位补进符号位，导致32个bit都是1，也就是-1，此时 i 为-1  
    return ((a ^ i) - i);   
    //与 -1 即0xFFFFFFFF异或就相当于取反，然后减去-1，就相当于加1，也就是取反加1,  
    }

不用temp交换两个整数

1
2
3
4
5

void swap(int x , int y)  {  
    x = x ^ y;  
    y = y ^ x;  
    x = x ^ y;  
}

求二进制表示数的长度

建表+二分搜索

注意到输入n是32位整数，所以其二进制长度至多有32种可能，这种小规模数据很适合查表，另外，处于某一区间的所有值具有相同的二进制长度，比如，若x 属于[4, 8)，则其二进制长度为3，若x属于[16, 32)，则其二进制长度为5，不失一般性，对于任意的x属于[2^(k-1), 2^k)，其二进制长度为k，那么我们可以分如下两步完成

1. 用Binary Search找到x所在地区间

2. 返回其对应区间的二进制长度

先建立区间表，请参看下面代码中的powof2数组，这里用数组元素值来表示区间，用下标来表示二进制长度，比如powof2[10] = 1024, powof2[11] = 2048, 则区间[1024, 2048)之内所有数值的二进制长度都是11。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

int BitLength2(unsigned int n)
{
    if(n == 0)
        return 0 ;
    // pow of 2, 2^0 - 2 ^32
    unsigned int powof2[33] =
    {
                 1,           2,           4,           8,         16,          32,
                64,         128,         256,         512,       1024,        2048,
              4096,        8192,       16384,       32768,      65536,      131072,
            262144,      524288,     1048576,     2097152,    4194304,     8388608,
          16777216,    33554432,    67108864,   134217728,  268435456,   536870912,
        1073741824,  2147483648,  4294967295,
    } ;
    int left = 0 ;
    int right = 32 ;
    while (left <= right)
    {
        int mid = (left + right) / 2 ;
        if (powof2[mid] <= n)
        {
            if (powof2[mid + 1] > n)
                return mid + 1;
            else if(powof2[mid] == n) // for max 32bit unsigned int 4294967295
                return mid ;
            else // powof2[mid] < n, search right part
                left = mid + 1 ;
        }
        else // powof2[mid] > n, search left part
            right = mid - 1 ;
    }
    return -1 ; // not found
}

二分累加

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int BitLength(unsigned int n){
	if (n>2147483647) {return 32;}
	n<<=1;
	int cnt=0;
	int bsheet[]={16,8,4,2,1};
	for (int i=0;i<5;i++){
		int tmp=n>>bsheet[i];
		if (tmp){
			n=tmp;
			cnt+=bsheet[i];
		}	
	}
	return cnt;
}

无分支版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int BitLength(unsigned int N) {
    //把数字从最高位起全用1填充.
    n = n | (n>>1);
    n = n | (n>>2);
    n = n | (n>>4);
    n = n | (n>>8);
    n = n | (n>>16);
    //统计1的个数
    n=(n & 0x55555555) + ((n>>1) & 0x55555555);  
    n=(n & 0x33333333) + ((n>>2) & 0x33333333);  
    n=(n & 0x0f0f0f0f) + ((n>>4) & 0x0f0f0f0f);  
    n=(n & 0x00ff00ff) + ((n>>8) & 0x00ff00ff);  
    n=(n & 0x0000ffff) + ((n>>16) & 0x0000ffff);  
    return n;  
}

位扫描指令

代码的其他片段都很好理解，重点是一条汇编指令：bsr 。这条汇编指令的意思是 Bit Scan Reverse （反向位扫描指令）。这条指令接受一个参数，会从高位扫描至低位，遇到一停止，将目标寄存器设置为该位的下标。所以，这应该是无论如何最快的取二进制最高位的方法了, 性能直逼空函数 。

1
2
3
4
5
6
7
8
9
10

inline uint32_t bsr_highest_bit(uint32_t x){
  if (!x) return 0;
  uint32_t bit;
  asm(
    "bsr %1, %0"
    : "=r" (bit)
    : "r" (x)
  );
  return bit;
}

LeetCode 338

给定一个非负整数 num. 对于 0 ≤ i ≤ num 范围中的每个数字 i, 计算其二进制数中 1 的数目并将它们作为数组返回。输入: 5 输出: [0,1,1,2,1,2]

核心代码就一行，开个数组以空间换时间。O(n).

位运算+动态规划，岂不美哉

bits[0] = 0;

bits[i] = bits[i & (i-1)] + 1;

解释：i & (i-1) 是把 i 的最后一个值为 1 的位设为 0，不难发现整数「i & (i-1)」 中 1 的位数比 i 中 1 的位数少一个 ，所以要加 1（即 bits[i & (i-1)] + 1）。非常巧妙，这样从 1 开始走一遍循环即可，中间不要做任何针对变量 i 的 1 的个数的计算，只不过付出了一个 bits 数组的代价。这里也是利用了以空间换时间的思想。

八皇后 - 位运算解法

此处仅给出代码实现，具体解释参见 你说你会位运算，那你用位运算来解下八皇后问题吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include<iostream>
using namespace std;

inline uint32_t BitLength(uint32_t x){
  if (!x) return 0;
  uint32_t bit;
  asm(
    "bsr %1, %0"
    : "=r" (bit)
    : "r" (x)
  );
  return bit;
}

int queens[8];
int cnt=0;
 
void queenSettle(int n=0,int colomn=0,int pie=0,int na=0){
	if(8==n){
		cnt++;
		for( int i=0;i<8;i++ )
   			 cout << queens[i] <<" ";
		cout<<endl;
	}else{
		int bits = (~(colomn|pie|na)) & 255;
		while(bits){
			// 每次从当前行可用的格子中取出最右边位为 1 的格子放置皇后
			int p = bits & -bits;
			queens[n] = BitLength(p);
			queenSettle(n+1, colomn | p, (pie | p) << 1, (na | p) >> 1);
			queens[n] = -1;//回溯，这步可以省略
			// 当前行最右边格子已经选完了，将其置成 0，代表这个格子已遍历过
			bits = bits & (bits-1);
		}
	}
}

int main(){
queenSettle();
cout<<cnt<<endl;
return 0;
}

老鼠试毒

有 8 个一模一样的瓶子，其中有 7 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 3 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

解题步骤如下：

1. 把这 8 个瓶子从 0 到 7 进行编号，用二进制表示如下

000
001
010
011
100
101
110
111

2. 将 0 到 7 编号中第一位为 1 的所有瓶子（即 1，3，5，7）的水混在一起给老鼠 1 吃，第二位值为 1 的所有瓶子（即2，3，6，7）的水混在一起给老鼠 2 吃， 第三位值为 1 的所有瓶子（4，5，6，7）的水混在一起给老鼠 3 吃，现在假设老鼠 1，3 死了，那么有毒的瓶子编号中第 1，3 位肯定为 1，老鼠 2 没死，则有毒的瓶子编号中第 2 位肯定为 0，得到值 101 ，对应的编号是 5， 也就是第五瓶的水有毒。

参考链接

bithacks

BitHacks–位操作技巧

算法-求一个二进制数的长度

位操作与使用位操作解题的基本思路

位运算的应用和分治法在二进制中的应用

对数和最小公倍数

取二进制最高位的一

你说你会位运算，那你用位运算来解下八皇后问题吧