数据结构与算法

二进制中1的个数

略

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

  题目是要求用位运算来实现，位运算是计算机学科的基石，很多底层的技术都离不开位运算，位运算总共有5种运算：与、或、异或、左移和右移。

与（&） 或（|） 异或（^）
0&0=0 0|0=0 0^0=0
1&0=0 1|0=1 1^0=1
0&1=0 0|1=1 0^1=1
1&1=1 1|1=1 1^1=0

  关于位移，左位移m<<n就是把二进制m数向左移动n位，然后右边补个0；而右位移有所不同，对于有符号数，如果它是正数(m>0)，m>>n就是把m向右移动n位，左边补个0，如果它是负数(m<0)，那么他的最高位应该是1，右移动n位后，左边补个1。例如：

左移：

0000 1010 << 2 = 0010 1000

1000 1010 << 3 = 01010000

右移：

0000 1010 >> 2 = 0000 0010

1000 1010 >> 3 = 1111 0001

分析

  根据题目，只需要输出一个数的二进制数中1的个数，直观的反应就是：把这个数的每一位扫描一遍，用一个变量count记录1的个数，遇到1count就加一，扫描完毕就输出count

可能有死循环的解法

  但是，要判断每一位是否为一有点困难，例如验证第一位是否为1，需要和0000 0001与运算，如果结果为0000 0001则第一位为1，否则为0；然后第二位要和0000 0010与运算，如果结果为0000 0010则第二位为1，否则为0；然后第三位，第四位…需要一直用新的数来做与运算，这样太麻烦。

  所以我们可以用依次右移要测试的数，然后依次用0000 0001与其做与运算，如果结果为1，则最低位为1，即是要验证的那一位数。代码可以这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int NumberOf1_CanNotUse(int n) {
        int count = 0;
        while (n != 0) {
            /*
            * 用1和n进行位与运算，
            * 结果要是为1则n的二进制形式
            * 最右边那位肯定是1，否则为0
            */
            if ((n & 1) == 1) {
                count++;
            }
            //把n的2进制形式往右推一位
            n = n >> 1;
        }
        return count;
    }

  但是，这种方法存在弊端，当输入一个负数例如-1，它的二进制数位1000 0001，由于它是个负数，当他右移一位时会变成1100 0000，随着右移，他就会变成1111 1111的死循环，所以需要一个更好的算法。

正常情况下的解法

  上个解法可以形象的比喻成这样，数n是一个要测试01的数字串，而0000 0001是一个测量工具，上文的解法是让测量工具不动，然后要测的东西移动，测量工具验证是否为0000 0001，但是这种方法可能出现死循环，为了不出现死循环的尴尬局面，我们可以不去采取移动要测试的物体，而是移动测试工具，就是数字串不动，标尺测一下第一位，然后左移一下，测试一下第二位，然后标尺再左移再测试，一直到标尺变成0000 0000，停止测试，输出结果。代码为：

1
2
3
4
5
6
7
8
9
10
11
private static int NumberOf1_low(int n) {
        int count = 0;
        int flag = 1;//标尺
        while (flag != 0) {//标尺为0时结束
            if ((n & flag) != 0) {//标尺测试结果匹配，数值加一。
                count++;
            }
            flag = flag << 1;//移动标尺
        }
        return count;
    }

一个很好的解法

  改方法的原理：有一个二进制数，如果它不等于0，则它必定有一位是个1。如果它的最右位为1，减去1，那么就最后一位发生了改变，由1变成0了；但如果它的最右位为0，减去1，那么从这个数最右一个1开始，它的右边所有的数都会取反，例如1100，减去1，变成1011，它的第三位是最右的1，减去1后，那个1再包括他右边所有的数就全部取反了。

  我们可以总结：一个二进制数减去1，就是从最右边看起，它的最右边第一个1，包括它和它右边所有的数就会全部取反。1010减一变1001，1100减一变1011等等。

  根据这个现象，我们可以对要测试的数减去1，例如1100，变成1011，然后1100和1011做与运算，得到了1000。对比一下原来的数1100和一系列变化过后的数1000，会发现它的最右一位1变成了0，他就少了个1，然后可以让计数器加一，一直到那个数变化成了0000为止，输出结果。

  再举个例子：1111，一次变化后变1110，计数器加一；二次变化后变1100，计数器再加一；三、四次同样操作，计数器最后加到了4，停止循环，输出计数器的结果。

代码实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int NumberOf1(int n) {
		int count = 0;//初始化计数器
        while(n!=0){//如果数中的1还存在就一直的循环，
          			//每去掉一个1，计数器就加1，直到一个1都没有
            ++count;
            n = (n-1)&n;
        }
        return count;
    }
}

总结

  1. 把数除以2和把数右移一位数学上是等价的，但是计算机中位运算的效率要优于除法运算，所以对于除法运算，尽可能的使用位运算来代替。

  2. 对于正数和负数，它们的右移是不同的，对于负数，右移时最高位保持为1。（注意：右移n位为相当与右移1位n次，所以1000 0000 >> 4 = 1111 1000）所以当编程中遇到右移运算，要多个心眼，注意最高位自动补1是否影响结果。

  3. 使用与运算（&）验证某位为1或0，可以让该位为1，其他位为0的数与它与运算（&），如果结果为0，则该位为0，如果结果为非0，则该位为1。

    例如：验证00X0 1101的第3位是否为1，则它与0010 0000 与运算（&），如果结果为0，则该位为0，如果结果为（0010 0000标尺本身）非0，则该位为1。

  4. 同理可以用或运算（|）来验证某位为1或0，可以让该位为0，其他位为1的数与它或运算（|），

    例如：验证00X0 1101的第3位是否为0，则它与1101 1111或运算（|），如果结果为（1101 1111标尺本身），则该位为0，如果结果为全1（1111 1111），则该位为1。

  5. 与运算（&）类似于一票否决（一个为0，结果为0），或运算（|）类似于非诚勿扰，一盏灯亮就可以牵走。