判断输入的一个非负的正整数,其是否是2的幂



判断输入的一个非负的正整数,其是否是2的幂,

/**
判断输入的一个非负的正整数,其是否是2的幂
*/

#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

#define max -1

/**
方法1 、 对2的幂进行判断,如 1、10、100、1000….(二进制数)这些只用高位为 1 , 如何确定高位
为 1 是解题的关键。
对一数 M = 1000 (二进制数) -M 在计算机中的存储是 补码 : 111…..1000 (最高位为符号位)
可以看出 M 和 -M 只用最高位为 1 ,我们可以我们可以把这个提取出来判断 M&(-M) ?= M
*/
bool judgePower2_1(int M)
{
return M ==(M&(-M));
}
/**
方法4 、 对那一位 1 提取的方法
*/
bool judgePower2_4(int M)
{
if(M == 0)
return false;
return 0 == (M & (M-1));
}
/**
方法2、采用素数的方法,一个一个判断 也可以 ,设 X = 2^n次幂,如果 X < M
继续乘以2,如果 X==M ;则输出 true,如果 X > M,则不是2的幂,输出 false;
*/
bool judgePower2_2(int M)
{
int n = 0;
int X = 0;
X = pow(2,n);
while(X < M)
n++,X=pow(2,n);
if(X==M)
return true;
return false;
}
/**
方法3、解题突破口同 方法2,这里我才用 递归的方式解答
*/
bool judgePower2_3(int n)
{
if(n==0)
return false;
if( n==2|| n==1 )
return true;
if(n%2 == 1)
return false;
return judgePower2_3(n/2);
}

int main()
{
cout << “Hello world!” << endl;
cout<<”please cin number n : “;
int n;
cin>>n;

//if(judgePower2_1(n))
//if(judgePower2_2(n))
if(judgePower2_3(n))
//if(judgePower2_4(n))
cout<<”yes , it’s power of 2″<<endl;
else
cout<<”not power of 2″<<endl;
return 0;
}