判断一个数是不是3的幂【(扩展)一个数是不是2、4的幂】
首先看到这个题目的时候我们容易想到采用循环或者递归的方式进行求借,也就是采用取余数的方式,循环的进行,直到除到为1的时候,示例代码如下:
#include <iostream>
using namespace std;
bool is_3power(int num)
{
if(num < 0) return false; //负数都不会是3的幂
while(num != 1){ //3的0次幂为1
if(num%3 != 0)
return false;
num /= 3;
}
return true;
}
int main()
{
cout<<"9是否为3的幂?"<<is_3power(9)<<endl;
cout<<"6是否为3的幂?"<<is_3power(6)<<endl;
cout<<"3是否为3的幂?"<<is_3power(3)<<endl;
cout<<"1是否为3的幂?"<<is_3power(1)<<endl;
return 0;
}
输出为:
9是否为3的幂?1
6是否为3的幂?0
3是否为3的幂?1
1是否为3的幂?1
现在有一个更高的要求,不许用循环或者递归的形式进行求解!
现在我们转变一下思路(这种方法比较通用):假设一个数NUM是3的幂,那么NUM的所有约数都是3的幂(这点没有问题吧?),那么当我们找到一个小于NUM的数n,且这个数n是3的幂的时候,那么n就一定是NUM的约数。
了解上述性质,我们只需要找到一个最大的3的幂,看看参数n是不是此最大的幂的约数就行了,假设参数是整型(int),那么3的最大的幂的求法为:
int max3Power = (int)pow(3,(int)(log(0x7fffffff)/log(3)));
这里解释一下log()函数,是求以e为底的对数的函数,由数学知识可以知道log(3)9 = log(e)9 / log(e)3。
知道3的最大幂的数之后,我们可以这么设计判断函数:
const int max3Power = (int)pow(3,(int)(log(0x7fffffff)/log(3)));
bool is_3power(int num)
{
if(num < 0) return false; //负数都不会是3的幂
return !(max3Power%num);
}
扩展【一个数是不是2、4的幂】
相对于前面说的比较通用的方法,对于一个数是不是2或者4的幂,有更加巧妙的方式进行判断。
1、判断是不是2的幂
将2的幂写成二进制很容易看出,2的幂的二进制只有一个1,其余全是0,如下所示:
000010000…00
而将2的幂的二进制减1,其二进制变为:
000001111…11
所以判断一个数是不是2的幂的方法为使用按位与操作,如果结果为0,则是2的幂:
n & (n-1)
代码如下
bool is_2power(int num)
{
return !(num & (num-1));//这里负数也会判断为非2的幂,负数最高位为1
}
2、判断是不是4的幂
4的幂首先是2的幂,因为4^n = (2^2)^n,所以4的幂的二进制同样只有一个1,与2的幂不同的是,4的幂的二进制的1在偶数位上,所以判断一个数是不是4的幂的方式为:
1)首先判断是不是2的幂,使用 n & (n-1)
2)进一步判断与0x55555555的按位与结果,0x55555555是用十六进制表示的数,其奇数位上全是1,偶数位上全是0,判断 n & 0x55555555为0则为4的幂。
- Pingback: C++技术岗位-面试题总结【持续更新…】 - Veaxen's