位移运算

世界上有两种人，一种知道二进制，而另一种人不知道二进制。

前言：

​ 对二进制知道已久，但是对于位运算却始终云里雾里。直到半年前去网易面试实习生被问到“给定一个的整数，求出它的二进制数中1的个数”，回头我详细搜了一下相关的解决方案，有常规解法，但是无论从效率还是代码简洁性来说，位运算都是最适合的。

​ 首先来普及一下二进制：二进制是指数字上的每一位都是0或1，即所谓的逢二进一。例如十进制的2转化为二进制之后是10，十进制的10转换成二进制之后是1010。

​ 所以二进制的运算就只设计0和1的运算，这比十进制的计算简单多了，它只有五种运算：与、或、异或、左移和右移。根据这种特点你可以给0和1赋予任何你想要的含义，来提取日常中的问题。​

一、与、或和异或

规律如下表

1
2
3
| `与（&）`   | `0 & 0 = 0` | `1 & 0 = 0` | `0 & 1 =`0  | `1 & 1 = 1` |
| `或（|）`   | `0 | 0 = 0` | `1 | 0 = 1` | `0 | 1 = 1` | `1 | 1 =1` |
| `异或（^）` | `0 & 0 = 0` | `1 ^ 0 = 1` | `0 ^ 1 = 1` | `1 ^ 1 = 0` |

对异或的理解可以是：不同值间异或为1。

二、位移运算：

​ 左移运算符m<<n表示把m左移n位。左移n位时，最左边的n位将被丢弃，同时在最右边补上n个0。比如：

1
2
3
00001010<<2 = 00101000

10001010<<3 = 01010000

​ 右移运算符m>>n表示把m右移n位。右移n位时最右边的n位将被丢弃，但是右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值，则用0填补最左边的n位；如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，右移之后最左边补n个0；如果数字原先是负数，则右移之后最左边补n个1。例如下面是对两个8位有符号数作为右移的例子：

1
2
3
00001010>>2 = 00000010

10001010>>2 = 11100010

三、思路

现在回到问题本身，基本思路是：

  • 先判断整数的二进制表示中最右边的是不是1；

  • 接着把输入的整数右移一位，此时原来处于从右边数起第二位被移到了最右边，再判断是不是1；

  • 就这样每次移一位，直到整个整数变成0为止。

这样整个问题的核心就变成了判断一个整数的最右边是不是1了。这很简单，只要将整数和1做位与运算看结果是不是0就知道了。1除了最右边的一位之外所有位都是0，如果一个整数与1做与运算的结果是1，表示该整数的最右边一位是1，否则是0。

代码如下：

1
2
3
4
5
6
7
8
9
10
int NumberOf1(int n){
    int count=0;
    while(n){
        if(n&1){
            count++;
        }
        n>>1;
    }
    return count;
}

运用除法当然也可以实现等价的功能，但是除法的效率上远远低于位移运算。

​ 到这里是捋清了基本的思路，接下来就该处理细节问题了。前边也说了，有符号的数字右移后在最左边补上与符号数相等的数字，而这个数字未必就是0 。如果输入的n是负数，怎么办呢，整数的最左边会一直补上数字1，这样整个计算就会变成一个死循环……

​ 如何避免死循环呢，一种做法是，既然我不确定输入的n是不是带符号的数，但是我可以确定我的1是无符号的，我可以将1左移来达到相同的效果。

  • 首先把n和1做与运算，判断最低位是不是1；

  • 接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1；

  • 这样反复左移，每次都能判断n的其中一位是不是1。

代码修改如下

1
2
3
4
5
6
7
8
9
10
11
int NumberOf1(int n){
    int count=0;
    unsigned int flag=1;
    while(flag){
        if(n&flag){
            count++;
        }
        flag<<1;
    }
    return count;
}

​ 是不是很有成就感，到这里本应该就结束了。书中给我们分析，这种解法的循环次数等于整数的二进制位数，32位的整数需要循环32次。

但是对原整数进行操作就没有更好的方法了吗？答案是有，而且书提出一个更好的解法，整数中有几个1就循环几次，而且理解起来比上边的更加简单。咱们的解体思路说白了不就是把整数最右边的1依次做归零计算吗，左移位只是一种途径，其它途径多的是。

​ 先来干货：把一个整数减去1，再和原来的整数做与运算，会把该整数的最右边的一个1变成0。

分析：

  • 如果一个整数不等于0，那么该整数的二进制表示中至少有一位是1，先假设这个数最右边一位是1，那么减去1时，最后一位变成0而其它所有位都保持不变。也就是最后一位相当于做了取反操作，由1变成了0；

  • 接下来假设最后一位不是1而是0的情况。如果该整数的二进制表示中最右边的1位于第m位，那么减去1后，第m位变成了0，第m位之后的所有的0变成了1，第m为之前的所有位保持不变。例如二进制1100，减去1后，变成那个了1011。

  • 由上边两种情况，可以得出一个整数减去1，都是把最右边的的1变成了0，如果它右边还有0的话，所有的0都变成1，而它左边的所有位保持不变。

  • 最后就是，当我们用减1之后的数字与原数字做位与运算，就相当于把原整数最右边的1变成了0。例如1100，减1之后变成1011，然后1100&1011 = 1000。

就下来就是代码了：

1
2
3
4
5
6
7
8
int NumberOf1(int n){
	int count =0;
	while(n){
		++count;
		n=(n-1)&n;
	}
	return count
}

好了，接下来补充一些相关知识：

  • 一个整数如果是2的整数次方，那么它的二进制表示中只有一位是1，其它的所以位都是0。根据前面的结论，把这样的整数减1之后再和它自己做与运算，这个整数中唯一的1就变成了0。

  • 输入两个整数m和n，计算要改变m二进制表示中的多少位才能得到n。可以分两步走：①求这两个数的异或，②统计异或结果中1的位数。