二的幂

来源Leetcode第231题 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1

---

2147483648

最开始的移位比对超时后，评论区有人提到用(2^32 % n)，因为2^32 % n一定为0。

public boolean isPowerOfTwo(int n) {
    long test = 2147483647;
    test += 1;
    return n > 0 && test % n == 0;
}

官方题解

来自

我们不打算在这里讨论时间复杂度为 O(logN) 的解决方案。该问题将通过位运算在 O(1) 的时间复杂度解决，通过使用如下的按位技巧：

• 如何获取二进制中最右边的 1：x & (-x)。
• 如何将二进制中最右边的 1 设置为 0：x & (x - 1)。

位运算：获取二进制中最右边的 1

易知，x 和 -x 只有一个共同点：最右边的 1。这说明 x & (-x) 将保留最右边的 1。并将其他的位设置为 0。通过 x & (-x) 保留了最右边的 1，并将其他位设置为 0 若 x 为 2 的幂，则它的二进制表示中只包含一个 1，则有 x & (-x) = x。

若 x 不是 2 的幂，则在二进制表示中存在其他 1，因此 x & (-x) != x。

因此判断是否为 2 的幂的关键是：判断 x & (-x) == x。

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

位运算：去除二进制中最右边的 1

易知，x & (x - 1) 可以将最右边的 1 设置为 0。因而，x & (x - 1) 操作会将 2 的幂设置为 0，因此判断是否为 2 的幂是：判断 x & (x - 1) == 0。

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