剑指Offer(15) 二进制中1的个数

发表于 | 分类于 | 阅读次数:
字数统计: 2.1k | 阅读时长 ≈ 8

用机器语言编写程序，经常需要直接处理二进制数值，并在位级别上执行操作。位操作可以解决各种各样的问题。有的问题会明确要求用位操作来解决，而在其他的情况下，位操作也是优化代码的实用技巧。写代码要熟悉位操作，同时也要熟悉位操作的手工运算。写好代码后一定要进行充分测试，也可以边写代码边测试。

位操作手工运算

其实二进制的位运算不是很难掌握，因为位运算总共只有7种运算：与、或、非(取反)、异或、左移位、带符号位右移位和无符号位右移位。
位操作符仅适用于整数类型（byte、short、int和long）。位操作涉及的字符将转换为整数。所有的位操作符可以构成位赋值操作符，如 &=， |=， ~=， ^=， <<=， >>=， >>>=。

对于复杂一点的位操作，可以使用若干技巧来解决。假定操作数的位宽为4。
（1）0110 + 0110
相当于 0110 * 2，也就是将0110左移1位。

（2）0100 0011
0100相当于4，上面就等于 4 0011，也就是2^2，于是将0011左移2位得到1100。
**一个数与2^n相乘，相当于将这个数左移n位。

（3）1101 ^ (~1101)
逐比特分解这个操作。一个比特与对它去烦的数值做异或操作，结果总是1。因此 x ^ (~x)的结果是一串1。

（4）1011 & (~0 << 2)
类似 x & (~0 << n)的操作会将x最右边的n位清零。 ~0的值是一串1（0在内存中为0x00000000，故取反后为一串1），将它左移n位后的结果为一串1后面跟n个0。将这个数与x进行“位与”操作，相当于将x最右边的n位清零。

位操作原理与技巧

处理位操作问题时，理解下面的原理会有很大帮助。下面的示例中，“1s”和“0s”分别表示一串1和一串0。
异或
x ^ 0s = x x ^ 1s = ~x x ^ x = 0
与
x & 0s = 0 x & 1s = x x & x = x
或
x | 0s = x x | 1s = 1s x | x = x

要理解这些表达式的含义，需要记住 所有操作都是按位进行的，某一位的运算结果不会影响其余位。

清零取数要用与，某位置一可用或
若要取反和交换，轻轻松松用异或

常见位操作

常见操作有：获取、设置、清除及更新位数据
以下这些位操作很重要，不过不要死记硬背，否则会滋生一些难以觉察的错误，相反，要吃透这些操作方法，学会举一反三，灵活处理问题。

获取

该方法将1左移i位，接着，对这个值与num执行“位与”操作，从而将i位之外的所有位清零。最后，检查该结果是否为零。不为零说明i位为1，否则，i位为0。
n & (1 << (k - 1)) 第k位置为1

1
2
3
boolean getBit(int num, int i) {
    return ((num & (1 << i)) != 0);
}

置位

将1左移i位，然后对这个值和num执行“位或”操作，这样只会改变i位的数据。该掩码i位除外的位均为零，孤儿不会影响num的其余位。

1
2
3
int setBit(int num, int i) {
    return num | (1 << i);
}

清零

将给定操作数n的第k位清零，可以用表达式 n & ~(1 << (k-1))

将掩码和num执行位与操作，这样只会清零num的i位，其余位保持不变。

1
2
3
4
int clearBit(int num, int i) {
    int mask = ~(1 << i);
    return num & mask;
}

将num最高位至i位（含）清零的做法如下：

1
2
3
4
int clearBitsMSBthroughI(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

将i位至0位（含）清零的做法：

1
2
3
4
int clearBitsIthrough0(int num, int i) {
    int mask = ~((1 << (i + 1)) - 1);
    return num & mask;
}

更新

这个方法将setBit与clearBit合二为一。首先，用诸如11101111的掩码将num的第i位清零。接着，将带写入值val左移i位，得到一个i位为val但其余位都为0的数。最后，对之前去的的两个结果执行“位或”操作
，val为1则将num的i位更新为1，否则该位仍为0。

1
2
3
4
int updateBit(int num, int i, int val) {
    int mask = ~(1 << i);
    return (num & mask) | (val << i);
}

(n & (n - 1) == 0) 的含义

（A & B） == 0 的含义
意思是，A和B二进制表示的同一位置绝不会同时为1。
因此，如果n & (n - 1) == 0，则 n 和 n-1 就不会有共同的1。

表达式 (n & (n - 1) == 0) 是用来检查n是否为2的某次方（或者检查n是否为0）。

二进制中1的个数

题目

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。

思路

遇到与二进制有关的题目，应该想到位运算(与、或、异或、左移、右移)。

方法一：“位与”有一个性质：通过与对应位上为1，其余位为0的数进行与运算，可以判断某一整数指定位上的值是否为1。
这道题中，先把整数n与1做与运算，判断最低位是否为1；接着把1左移一位，与n做与运算，可以判断次低位是否为1……反复左移，即可对每一个位置都进行判断，从而可以获得1的个数。这种方法需要循环判断32次。

方法二（better）：
如果一个整数不为0，把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1。其余所有位将不会受到影响。
再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。因此，把一个整数减1，再和原来的整数做与运算，会把该整数最右边的1变成0。
这种方法，整数中有几个1，就只需要循环判断几次。

测试用例

1.正数（包括边界值1、0x7FFFFFFF）
2.负数（包括边界值0x80000000、0xFFFFFFFF）
3.0

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class NumberOf1InBinary {
    public int numberOf1_Solution1(int n) {
        int count = 0;
        int flag = 1;
        while (flag != 0) {
            if ((flag & n) != 0)
                count++;
            flag <<= 1;)
        }
        return count;
    }

    public int numberOf1_Solution2(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

总结

  1. 注意：负数右移还是负数！即如果对n=0x8000 0000右移，最高位的1是不会变的。如果这道题目通过令n=n>>1来计算n中1的个数，该数最终会变成0xFFFF FFFF而陷入死循环！

  2. 把一个整数减1，再和原来的整数做与运算，会把该整数最右边的1变成0。这种方法一定要牢牢记住，很多情况下都可能用到，例如：

    • 一句话判断一个整数是否为2的整数次方；
    • 对两个整数m和n，计算需要改变m二进制表示中的几位才能得到n。

  3. 与数字操作有关的题目，测试时注意边界值的问题。对于32位数字，其正数的边界值为1、0x7FFFFFFF，负数的边界值为0x80000000、0xFFFFFFFF。

  4. (flag & n！=0)，而非(flag & n == 1)； 也就不能写成count += (flag & 1)。
  5. if语句中，不能写为if(flag & n != 0) ，而要写成 if((flag & n) != 0)，需要加上括号

扩展题

题目

编写一个函数，确定需要改变几个位，才能将整数A转成整数B。
这道题可以分两步解决：第一步求这两个数的异或；第二步统计异或结果中1的位数。

只要输出a^b有几个位为1即可。

1
2
3
4
5
6
7
int bitSwapRequired(int a, int b) {
    int count = 0;
    for (int c = a ^ b; c != 0; c >>= 1) {
        count += c & 1;
    }
    return count;
}

上面的代码的做法是不断对c执行移位操作，然后检查最低有效位，但是其实可以不断翻转最低有效位，计算要多少次才会变成0。操作c = c & (c - 1)会清楚c的最低有效位。

1
2
3
4
5
6
7
public static int bitSwapRequired(int a, int b) {
    int count = 0;
    for (int c = a ^ b; c != 0; c = c & (c - 1)) 
        count++;

    return count;
}
0%