Problem:
Given an integer, write a function to determine if it is a power of two.
Summary:
判断一个数n是不是2的整数幂。
Analysis:
这道题首先需要注意n为非整数是返回false的情况。
1. 若将n转换为二进制数,如果n为2的整数幂,则转换得到的二进制数只包含一个一,故计算转换过程中1的个数,最终判断。
class Solution {
public:
bool isPowerOfTwo(int n) {
int cnt = ; while (n > ) {
if (n % ) {
cnt++;
}
n /= ;
} return cnt == ? true : false;
}
};
可以简化为位操作的形式,如下:
class Solution {
public:
bool isPowerOfTwo(int n) {
int cnt = ;
while (n > ) {
cnt += (n & );
n >>= ;
} return cnt == ;
}
};
2. 经过查网上大牛的代码,学到了一个神奇的技巧:当一个数n为2的整数幂时,其二进制最高位必为1,其余位数都为0。那么n-1最高位为0,其余位数均为1。则若n & (n -1)为0时,n必为2的整数幂。
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n > ) && !(n & (n - ));
}
};