n & (n - 1) 的含义

[Shellbye]

这真可以说是一个老朋友了，在不同的地方见过了好多次，只是我每次看见它，都得查一查它到底是什么意思，而且每次它的含义都还有点不同。这次看《剑指 offer》，作者讲解的比较清楚，所以我在这里顺便记录一下。

先看 n - 1

如果整数不为 0 ，则它的二进制表示中，至少有一位得是 1 。假设这个 1 位于最右侧，那么减去 1 之后，最右侧就变成了 0 。然后如果最右侧不是 1 ，而是 0 ，假设最右边的 1 位于第 m 位，那么减去 1 之后，第 m 位就变成了 0 ，然后 m 位之后的 0 全部变成了 1 。比如 1100 ，减去 1 之后，就变成了 1011 。

再看 n & (n - 1)

n - 1 的作用，是把最右边的 1 变成了 0 （其再右侧的 0 变成了 1），左边的所有位都保持不变。接下来，我们把 n - 1 和 n 按位取与运算（n & (n - 1)），那么在左边全部不变的前提下，右边的那些刚才从 0 变成 1 的位又回到了 0 的状态。比如 1100 ，减去 1 变成了 1011 ，然后 1100 & 1011 是 1000。所以，把一个整数减去 1 再与自己按位取与，会把该整数的最右边的 1 变成 0。

应用场景 1 ——计算一个数的二进制表示中有几个 1

题目：输入一个整数，输出该整数二进制表示中 1 的个数

这个题目不难，最不济就依次和 1 做按位与，然后右移，再按位与... 每次按位与之后看一下结果是不是 1 。这个解法的循环次数与输入的二进制表示长度有关系，结合我们上面的 n & (n - 1) ，我们可以有如下解法：

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

上面的解法中，每次都把 n 的最右边的 1 变成了 0 ，直到 n 自己变成 0 ，那么变了几次，就说明 n 的二进制表示里就有几个 1 。

应用场景 2 —— 判断一个正整数是不是 2 的整数倍

题目：输入一个正整数，判断该正整数是否是 2 的整数倍

这个题目也不难，可以不停地通过除以 2 看余数是否为 0 来判断，但是这样需要计算的次数也和输入的大小有关系。从二进制的角度考虑，一个数是不是 2 的整数倍其实就是它的二进制表示是不是只有一位为 1 ，如果是，那它就是 2 的整数倍，否则就不是。基于这个认知，加上 n & (n - 1) 把一个数的二进制表示的最右边的 1 变成 0 ，我们可以构思如下算法：

    boolean isPowerOf2(int n) {
        return (n & (n - 1)) == 0;
    }

如果一个数把最右边的 1 变成 0 之后，就彻底变成了 0 ，那么这个数的二进制表示就只有一个 1 ，即它肯定是 2 的整数倍。

参考

https://stackoverflow.com/questions/4678333/n-n-1-what-does-this-expression-do