题目描述（简单难度）

231*. Power of Two - 图1

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

思路分析

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

解法一

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

  1. public boolean isPowerOfTwo(int n) {
  2.     int power = 1;
  3.     while (power <= n) {
  4.         if (power == n) {
  5.             return true;
  6.         }
  7.         power = power << 1;
  8.         // if (power == Integer.MIN_VALUE)
  9.         if (power == -2147483648) {
  10.             break;
  11.         }
  12.     }
  13.     return false;
  14. }

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

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

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

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

解法二

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

  1. 1 1
  2. 2 10
  3. 4 100
  4. 8 1000
  5. 16 10000
  6. ...

可以发现发现都是 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 了，所以它一定不等于它本身了。

  1. public boolean isPowerOfTwo(int n) {
  2.     if (n == 0 || n == -2147483648) {
  3.         return false;
  4.     }
  5.     return Integer.highestOneBit(n) == n;
  6. }

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

  1. public boolean isPowerOfTwo(int n) {
  2.     if (n <= 0) {
  3.         return false;
  4.     }
  5.     return Integer.highestOneBit(n) == n;
  6. }

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

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

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

它做了什么事情呢？我们从 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，然后两数做差。

  1. i       0 0 0 1 1 1 1 1
  2. i >>> 1 0 0 0 0 1 1 1 1   
  3.         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 赋值给它的旁边。

  1. i |= (i >>  1);
  2. 0 0 0 1 X X X X -> 0 0 0 1 1 X X X
  4. 现在首位有两个 1 了，所以就将这两个 1 看做一个整体，继续把 1 赋值给它的旁边。
  5. i |= (i >>  2);
  6. 0 0 0 1 1 X X X -> 0 0 0 1 1 1 1 X
  8. 现在首位有 4 个 1 了，所以就将这 4 个 1 看做一个整体，继续把 1 赋值给它的旁边。
  9. i |= (i >>  4);
  10. 0 0 0 1 1 1 1 X -> 0 0 0 1 1 1 1 1
  12. 其实到这里已经结束了，但函数中是考虑最坏的情况，类似于这种 1000000...00, 首位是 1, 有 31 个 0

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

  1. public boolean isPowerOfTwo(int n) {
  2.     if (n <= 0) {
  3.         return false;
  4.     }
  5.     int i = n;
  6.     i |= (i >> 1);
  7.     i |= (i >> 2);
  8.     i |= (i >> 4);
  9.     i |= (i >> 8);
  10.     i |= (i >> 16);
  11.     i = i - (i >>> 1);
  12.     return i == n;
  13. }

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

解法三

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

  1. public boolean isPowerOfTwo(int n) {
  2.     if (n == 0) return false;
  3.     while (n % 2 == 0) {
  4.         n /= 2;
  5.     }
  6.     return n == 1;
  7. }

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

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

解法四

做过 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 的幂次，所以代码可以写成下边的样子。

  1. public boolean isPowerOfTwo(int n) {
  2.     if (n <= 0) {
  3.         return false;
  4.     }
  5.     return (n & (n - 1)) == 0;
  6. }

解法五

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

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

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

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

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 的个数
  2. 1   1   0   1   0   0   1   1
  3. 首先把它看做 8 组，统计每组 1 的个数
  4. 原数字：(1)   (1)   (0)   (1)   (0)   (0)   (1)   (1)
  5. 统计数：(1)   (1)   (0)   (1)   (0)   (0)   (1)   (1)
  6. 每个数字本身，就天然的代表了当前组 1 的个数。
  8. 接下来看做 4 组，相邻两组进行合并，统计数其实就是上边相邻组统计数相加即可。
  9. 原数字：(1    1)   (0    1)   (0   0)   (1  1)
  10. 统计数：(1    0)   (0    1)   (0   0)   (1  0)
  11. 十进制：   2           1         0         2        
  13. 接下来看做 2 组，相邻两组进行合并，统计数变成上边相邻组统计数的和。
  14. 原数字：(1    1     0    1)   (0   0     1  1)
  15. 统计数：(0    0     1    1)   (0   0     1  0)
  16. 十进制：         3                   2  
  18. 接下来看做 1 组，相邻两组进行合并，统计数变成上边相邻组统计数的和。
  19. 原数字：(1    1     0    1     0   0     1  1)
  20. 统计数：(0    0     0    0     0   1     0  1)
  21. 十进制：                   5

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

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

231*. Power of Two - 图2

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

231*. Power of Two - 图3

最后我们就的得到了 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。

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

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

再回到 java 的源码。

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

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

231*. Power of Two - 图4

第一步要做的就是把 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 的幂次，那么

    231*. Power of Two - 图5

    231*. Power of Two - 图6

    ，所以

    231*. Power of Two - 图7

    。

  • 如果 n 不是 2 的幂次，那么

    231*. Power of Two - 图8

    ，其中 j 是一个奇数，因为 n 一直进行除以 2 可以得到 k，直到不能被 2 整除，此时一定是奇数，也就是公式中的 j。

    231*. Power of Two - 图9

    。

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

  1. public boolean isPowerOfTwo(int n) {
  2.     if (n <= 0) {
  3.         return false;
  4.     }
  5.     return 1073741824 % n == 0;
  6. }

解法七

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

  1. public boolean isPowerOfTwo(int n) {
  2.     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);
  3. }

总

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

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情