位运算（5）——Power of Two

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

关键是弄明白2的幂的二进制形式只有一个1。

 1 public class Solution {
 2     public boolean isPowerOfTwo(int n) {
 3         int count = 0;
 4         if (n <= 0) {
 5             return false;
 6         } else {
 7             while (n != 0) {
 8                 if ((n & 1) == 1) {
 9                     count++;
10                 }
11                 n = n >> 1;
12                 if (count > 1) {
13                     return false;
14                 }
15             }
16             return true;
17         }
18     }
19 }

相似题：判断一个数是不是3的幂。

方法一：循环

 1 public class Solution {
 2     public boolean isPowerOfThree(int n) {
 3         if (n < 1) {
 4             return false;
 5         }
 6 
 7         while (n % 3 == 0) {
 8             n /= 3;
 9         }
10 
11         return n == 1;
12     }
13 }

方法二：转3进制

10进制，1（10⁰）、10（10¹）、100（10²）……；

2进制，1（2⁰）、10（2¹）、100（2²）……；

3进制，1（3⁰）、10（3¹）、100（3²）……；

String baseChange = Integer.toString(number, base);

boolean matches = myString.matches("123");

1 public class Solution {
2     public boolean isPowerOfThree(int n) {
3         return Integer.toString(n, 3).matches("^10*$");
4     }
5 }

方法三：数学

3^k= n，即 k = log₃n 等价于 k = log₁₀n / log₁₀3。如果n是3的幂，那么k为整数。

1 public class Solution {
2     public boolean isPowerOfThree(int n) {
3         return (Math.log10(n) / Math.log10(3)) % 1 == 0;
4     }
5 }

https://leetcode.com/articles/power-of-three/