题目描述(简单难度)

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 调用这个方法,如果 n2 的幂次,那么它还是它本身。如果是其他数,由于其它位被置 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
  3. 现在首位有两个 1 了,所以就将这两个 1 看做一个整体,继续把 1 赋值给它的旁边。
  4. i |= (i >> 2);
  5. 0 0 0 1 1 X X X -> 0 0 0 1 1 1 1 X
  6. 现在首位有 4 1 了,所以就将这 4 1 看做一个整体,继续把 1 赋值给它的旁边。
  7. i |= (i >> 4);
  8. 0 0 0 1 1 1 1 X -> 0 0 0 1 1 1 1 1
  9. 其实到这里已经结束了,但函数中是考虑最坏的情况,类似于这种 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 的个数。
  7. 接下来看做 4 组,相邻两组进行合并,统计数其实就是上边相邻组统计数相加即可。
  8. 原数字:(1 1) (0 1) (0 0) (1 1)
  9. 统计数:(1 0) (0 1) (0 0) (1 0)
  10. 十进制: 2 1 0 2
  11. 接下来看做 2 组,相邻两组进行合并,统计数变成上边相邻组统计数的和。
  12. 原数字:(1 1 0 1) (0 0 1 1)
  13. 统计数:(0 0 1 1) (0 0 1 0)
  14. 十进制: 3 2
  15. 接下来看做 1 组,相邻两组进行合并,统计数变成上边相邻组统计数的和。
  16. 原数字:(1 1 0 1 0 0 1 1)
  17. 统计数:(0 0 0 0 0 1 0 1)
  18. 十进制: 5

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

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

231*. Power of Two - 图2

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

231*. Power of Two - 图3

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

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

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

扩展到任意情况,两组合并成一组,如果合并前每组的个数是 n,合并前的数字是 x,那么合并后的数字就是 x & (000...111...) + x >>> n & (000...111...),其中 01 的个数是 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 组,所以就是 83,即 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 -> 1001 - > 0100 -> 0010 -> 01

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

第二步一致。

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

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

解法六

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

  • 如果 n2 的幂次,那么

    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

综上所述,通过是否能被 230 次方,即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 哦 ^^

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