leetcode power of number

Posted on   |   In   |  

判断一个数是2的幂，3的幂，4的幂

Power Of Two

Given an integer, write a function to determine if it is a power of two.
判断一个数是否是2的幂
解法一:循环判断，这里不再写代码

解法二：
思路:先写出所有的2的幂
1(1)
2(10)
4(100)
8(1000)
16(10000)

可以发现规律，这些数都是只有一个1的二进制数，利用(n&(n-1))可以去掉n的二进制的低位1，所以只要是2的幂则这个结果一定为0；

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n <= 0 ? false : !(n&(n-1));
    }
};

Power Of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
注意题目给出的是有符号数的32位
解法一：利用取对数的方法,将这个数对3取对数，得到的结果在作为pow(3,)的参数

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int num) {
        return num <= 0?false:(num == pow(4, round(log(num)/log(4) ) ) );
    }
};

解法二:
1(1)
4(100)
16(10000)
64(1000000)

比较一下上面的数和2的幂的区别会发现，上面所有的1出现在奇数位上，所以可以先判断是不是2得幂，再判断是不是奇数位上的1

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int num) {
        return num <= 0?false:(!(num&(num-1)) && (num&(0x55555555)) );
    }
};

Power Of Three

Given an integer, write a function to determine if it is a power of three.
循环法，列举法(列出所有的3的幂)都太费时间或空间；

1
2
3
4
while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

1
2
3
4
5
return (n == 1) 
    or (n == 3)
    or (n == 9)
    ... 
    or (n == 1162261467)

取对数法

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n<=0?false:(n == pow(3, round( log(n)/log(3) ) ));
    }
};