题目描述（简单难度）

判断一个数是不是 2 的幂次。

思路分析

题目比较简单，有很多解法，看了其他人的解法，各种秀操作，哈哈。解法一和解法二是我开始想到的，后边的解法是其他人的也总结到这里。

解法一

介绍一种暴力的方法，判断 1 和当前数是否相等，再判断 2 和当前数是否相等，再判断 4 和当前数是否相等...直到所枚举的数超过了当前数，那么就返回 false。至于枚举的数 1 2 4 8 16...，可以通过移位得到。

public boolean isPowerOfTwo(int n) {
    int power = 1;
    while (power <= n) {
        if (power == n) {
            return true;
        }
        power = power << 1;
        // if (power == Integer.MIN_VALUE)
        if (power == -2147483648) {
            break;
        }
    }
    return false;
}

当然有一点需要注意，需要了解一些补码的知识，参考 趣谈补码。

对于 int 类型，最大的 2 的幂次是 2 的 30 次方，即1073741824，二进制形式是 0100000...00。

最大的负数是 -2147483648，二进制形式是 1000000...00。

可以发现前者左移一位刚好变成了后者，这也是代码中判断是否是 -2147483648 的原因，不然的话会造成死循环的。

解法二

我们把数字放眼到二进制形式，列举一下 2 的幂次。

1 1
2 10
4 100
8 1000
16 10000
...

可以发现发现都是 100... 的形式，如果做过 201 题，对 Integer.highestOneBit 方法可能还记得。可以实现保留最高位的 1 ，然后将其它位全部置为 0。即，把 0 0 0 1 X X X X 变成 0 0 0 1 0 0 0 0 。

如果我们对给定的数 n 调用这个方法，如果 n 是 2 的幂次，那么它还是它本身。如果是其他数，由于其它位被置 0 了，所以它一定不等于它本身了。

public boolean isPowerOfTwo(int n) {
    if (n == 0 || n == -2147483648) {
        return false;
    }
    return Integer.highestOneBit(n) == n;
}

0 和 -2147483648 不符合上边的规则，单独考虑，我们可以更干脆一些，小于等于 0 的数直接不考虑。

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return Integer.highestOneBit(n) == n;
}

201 题 的解法三对 highestOneBit 的源码进行了分析，下边把之前的解析贴过来。

我们调用了库函数 Integer.highestOneBit，我们去看一下它的实现。

/**
     * Returns an {@code int} value with at most a single one-bit, in the
     * position of the highest-order ("leftmost") one-bit in the specified
     * {@code int} value.  Returns zero if the specified value has no
     * one-bits in its two's complement binary representation, that is, if it
     * is equal to zero.
     *
     * @param i the value whose highest one bit is to be computed
     * @return an {@code int} value with a single one-bit, in the position
     *     of the highest-order one-bit in the specified value, or zero if
     *     the specified value is itself equal to zero.
     * @since 1.5
     */
public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

它做了什么事情呢？我们从 return 入手。

对于 0 0 0 1 X X X X ，最终会变成 0 0 0 1 1 1 1 1，记做 i 。把 i 再右移一位变成 0 0 0 0 1 1 1 1，然后两数做差。

i       0 0 0 1 1 1 1 1
i >>> 1 0 0 0 0 1 1 1 1   
        0 0 0 1 0 0 0 0

就得到了这个函数最后返回的结果了。

将 0 0 0 1 X X X X 变成 0 0 0 1 1 1 1 1，可以通过复制实现。

第一步，将首位的 1 赋值给它的旁边。

i |= (i >>  1);
0 0 0 1 X X X X -> 0 0 0 1 1 X X X

现在首位有两个 1 了，所以就将这两个 1 看做一个整体，继续把 1 赋值给它的旁边。
i |= (i >>  2);
0 0 0 1 1 X X X -> 0 0 0 1 1 1 1 X

现在首位有 4 个 1 了，所以就将这 4 个 1 看做一个整体，继续把 1 赋值给它的旁边。
i |= (i >>  4);
0 0 0 1 1 1 1 X -> 0 0 0 1 1 1 1 1

其实到这里已经结束了，但函数中是考虑最坏的情况，类似于这种 1000000...00, 首位是 1, 有 31 个 0

我们可以把上边的源码直接放过来。

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    int i = n;
    i |= (i >> 1);
    i |= (i >> 2);
    i |= (i >> 4);
    i |= (i >> 8);
    i |= (i >> 16);
    i = i - (i >>> 1);
    return i == n;
}

上边的解法是我开始想到的，下边的解法全部来自 这里，分享一下。

解法三

一直进行除以 2，直到不是 2 的倍数。

public boolean isPowerOfTwo(int n) {
    if (n == 0) return false;
    while (n % 2 == 0) {
        n /= 2;
    }
    return n == 1;
}

也可以改写成递归的形式。

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n == 1 || (n%2 == 0 && isPowerOfTwo(n/2)));
}

解法四

做过 191 题 的话，对一个 trick 应该有印象。

有一个方法，可以把最右边的 1 置为 0，举个具体的例子。

比如十进制的 10，二进制形式是 1010，然后我们只需要把它和 9 进行按位与操作，也就是 10 & 9 = (1010) & (1001) = 1000，也就是把 1010 最右边的 1 置为 0。

规律就是对于任意一个数 n，然后 n & (n-1) 的结果就是把 n 的最右边的 1 置为 0 。

也比较好理解，当我们对一个数减 1 的话，比如原来的数是 ...1010000，然后减一就会向前借位，直到遇到最右边的第一个 1，变成 ...1001111，然后我们把它和原数按位与，就会把从原数最右边 1 开始的位置全部置零了 ...10000000。

有了这个知识，我们看一下解法二列举的 2 的幂次，只有一个 1，如果通过 n&(n-1)，那么就会变成 0 了。

同样的 0 和 -2147483648 不符合上边的规则，需要单独考虑。又因为所有负数一定不是 2 的幂次，所以代码可以写成下边的样子。

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
}

解法五

java 中还有一个方法 Integer.bitCount(n)，返回 n 的二进制形式的 1 的个数。

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return Integer.bitCount(n) == 1;
}

同样的，我们学习一下 bitCount 的源码。

/**
     * Returns the number of one-bits in the two's complement binary
     * representation of the specified {@code int} value.  This function is
     * sometimes referred to as the <i>population count</i>.
     *
     * @param i the value whose bits are to be counted
     * @return the number of one-bits in the two's complement binary
     *     representation of the specified {@code int} value.
     * @since 1.5
     */
public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

191 题 题目就是求二进制 1 的个数，其中解法三介绍的其实就是上边的解法，我把解释贴过来。

有点类似于 190 题 的解法二，通过整体的位操作解决问题，参考 这里-by-time-m-is-the-count-of-1's-and-another-several-method-of-O(1)-time) ，也是比较 trick 的，不容易想到，但还是很有意思的。

本质思想就是用本身的比特位去记录对应位数的比特位 1 的个数，举个具体的例子吧。为了简洁，求一下 8 比特的数字中 1 的个数。

统计数代表对应括号内 1 的个数
1   1   0   1   0   0   1   1
首先把它看做 8 组，统计每组 1 的个数
原数字：(1)   (1)   (0)   (1)   (0)   (0)   (1)   (1)
统计数：(1)   (1)   (0)   (1)   (0)   (0)   (1)   (1)
每个数字本身，就天然的代表了当前组 1 的个数。

接下来看做 4 组，相邻两组进行合并，统计数其实就是上边相邻组统计数相加即可。
原数字：(1    1)   (0    1)   (0   0)   (1  1)
统计数：(1    0)   (0    1)   (0   0)   (1  0)
十进制：   2           1         0         2        

接下来看做 2 组，相邻两组进行合并，统计数变成上边相邻组统计数的和。
原数字：(1    1     0    1)   (0   0     1  1)
统计数：(0    0     1    1)   (0   0     1  0)
十进制：         3                   2  

接下来看做 1 组，相邻两组进行合并，统计数变成上边相邻组统计数的和。
原数字：(1    1     0    1     0   0     1  1)
统计数：(0    0     0    0     0   1     0  1)
十进制：                   5

看一下 「统计数」的变化，也就是统计的 1 的个数。

看下二进制形式的变化，两两相加。

看下十进制形式的变化，两两相加。

最后我们就的得到了 1 的个数是 5。

所以问题的关键就是怎么实现每次合并相邻统计数，我们可以通过位操作实现，举个例子。

比如上边 4 组到 2 组中的前两组合成一组的变化。要把 (1 0) (0 1) 两组相加，变成 (0 0 1 1) 。其实我们只需要把 1001 和 0011 相与得到低两位，然后把 1001 右移两位再和 0011 相与得到高两位，最后将两数相加即可。也就是(1001) & (0011) + (1001) >>> 2 & (0011)= 0011。

扩展到任意情况，两组合并成一组，如果合并前每组的个数是 n，合并前的数字是 x，那么合并后的数字就是 x & (000...111...) + x >>> n & (000...111...)，其中 0 和 1 的个数是 n。

public int hammingWeight(int n) {
    n = (n & 0x55555555) + ((n >>> 1) & 0x55555555); // 32 组向 16 组合并，合并前每组 1 个数
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333); // 16 组向 8 组合并，合并前每组 2 个数
    n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f); // 8 组向 4 组合并，合并前每组 4 个数
    n = (n & 0x00ff00ff)+ ((n >>> 8) & 0x00ff00ff); // 4 组向 2 组合并，合并前每组 8 个数
    n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff); // 2 组向 1 组合并，合并前每组 16 个数
    return n;
}

写成 16 进制可能不好理解，我们拿16 组向 8 组合并举例，合并前每组 2 个数。也就是上边我们推导的，我们要把 (1 0) (0 1) 两组合并，需要和 0011 按位与，写成 16 进制就是 3，因为合并完是 8 组，所以就是 8 个 3，即 0x33333333。

再回到 java 的源码。

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

第一步写法不一样，也很好理解。结合下边的图看，

第一步要做的就是把 11 -> 10，01 - > 01，00 -> 00，10 -> 01。

其实就是原来的数减去高位的数，11 - 1 = 10, 01 - 0 = 01，00 - 0 = 00，10 - 1 = 01。

第二步一致。

第三步，没有与完相加，而是先相加再相与，之所以可以这么做，是因为四位的话最多就是 4 个 1，也就是 0100 和 0100 合并，结果最多也就是 4 位，所以只需要最后和 0f 相与，将高四位置零即可。

第四步和第五步没有相与，是因为最多 32 个 1，用二进制表示就是 100000，所以只需要低 6 位的结果，高 8 位是什么已经不重要了，也就不需要通过相与置零了，最后只需要和 0x3f(111111) 相与取得我们的结果即可。

解法六

前边提到对于 int 类型，最大的 2 的幂次是 2 的 30 次方，即1073741824。对于 n 分两种情况讨论。

• 如果 n 是 2 的幂次，那么 $n=2^k$

  $2^{30}=2^k*2^{30-k}$，所以 $2^{30} \% 2^k==0$。

• 如果 n 不是 2 的幂次，那么 $n = j * 2^k$，其中 j 是一个奇数，因为 n 一直进行除以 2 可以得到 k，直到不能被 2 整除，此时一定是奇数，也就是公式中的 j。

  $2^{30} \% (j * 2^k) = 2^{30-k} \% j!=0$。

综上所述，通过是否能被 2 的 30 次方，即1073741824 整除，即可解决我们的问题。

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return 1073741824 % n == 0;
}

解法七

超级暴力打表法，因为 int 范围内 2 的幂次也只有 31 个数。

public boolean isPowerOfTwo(int n) {
    return new HashSet<>(Arrays.asList(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)).contains(n);
}

总

这道题的话使用了很多二进制的技巧，因为题目本身比较简单，所以就是各种大神秀操作了，哈哈，大概是解法最多的一道题了。