怎么快速判断一个正整数是2的N次幂
网友于：2013-02-11 浏览：129次
如何快速判断一个正整数是2的N次幂？
long N ＝ ………;
我想法是 N 保存的是一个2进制数， 如果这个2进制数中只有1位为1，其他位全是0，则返回第几位，反之返回－1。
但是这个算法有什么最好的吗？因为程序中会有无数次的调用，所以想写的精简并高效些。
–解决方案–
X和X-1同或一下是 0 ，就是，非0就不是。可以吗？
–解决方案–
//long a=0x40000000L;
if(a&&!(a & ~(a^(a-1))))
{ for(int n=0;a;a =1,n++);
cout OK: n \n ;
} else cout Fail!\n ;
–解决方案–
2的N次只可能是32种可能，因为对于long来说是4个字节（即32位）
这里为扩大范围把long变为unsigned long，因为long是有符号的，最高位为1就是负数。
//伪代码如下
//in：一个整数
//out：如果是2的幂，则返回第几位为1，否则返回-1
int TellBit(long n)
static unsigned long v={2^0, 2^1 2^2 … 2^31};//静态数组，避免每次调用都分配内存
int k = binary_search(v, n, 32);//二分查找（伪代码）
return k;
时间复杂度：
在一个32个元素的数组里面进行二分查找的复杂度为log（32）=5
即5次整数比较即可
–解决方案–
3楼的算法思想是什么？没有给说明，可读性不强。
时间复杂度是多少？
–解决方案–
如果(x & (x – 1)) == 0，则x是2的N次幂。
至于求第几位想不出好办法，我用枚举，因为int范围内只有31个这样的数。
C/C++ code
#include iostream using namespace std;const int n = 31;int a[n];int cal(int x){ if ((x & (x – 1)) == 0) { for (int i = 0; i n; i++) { if (x == a[i]) { return i; } } } return -1;}int main { int i; a[0] = 1; for (i = 1; i n; i++) { a[i] = a[i-1] 1; } int x; while (cin x) { cout cal(x) endl; }}
–解决方案–
这样的数31个，预先存到数组里，然后采用二分法进行查找，如果找到了，就说明是2的N次方，否则不是。
–解决方案–
cuixiping
的思路是对的,二分查找后,按照31个数字,最多查找Log31次,就是4次!
速度极快!
–解决方案–
3楼的算法思想是什么？没有给说明，可读性不强。
时间复杂度是多少？
–解决方案–
cuixiping
的思路是对的,二分查找后,按照31个数字,最多查找Log31次,就是4次!
速度极快!
–解决方案–
如果(x & (x – 1)) == 0，则x是2的N次幂。
相关解决方案
输入一个正整数n，输出全部和为n的连续整数序列一个正整数N，不要sqrt求开方数输入一个正整数，判断其是不是为素数对任一个正整数n，最小的正整数m,使得n*m结果为0和1组成怎么判断一个β位的整数n是否是某个整数的幂输入一个正整数 N，把它分解成质因数相乘的形式。 java写怎么巧判断一个整数是否是2的n次方幂一个正整数拆分成连续的几个整数之和任意给定一个正整数N，最小的正整数M(M 1)，使得N*M的十进制表示形式里只含有1和0给一个正整数N，打印NxN的蛇形矩阵（2) 之空间复杂度O(1)
最新解决方案
uestc poj2559 秋实大哥往打工无紧邻队列重复的队列复杂网络社区发现步骤SDUT_2146:最小小子序列和怎么在很大数量级的数据中（比如1个亿）筛选出前10万个最小值？之六OpenJudge_1321:棋盘有关问题回想深搜与剪枝初步怎么在很大数量级的数据中（比如1个亿）筛选出前10万个最小值？之五怎么在很大数量级的数据中（比如1个亿）筛选出前10万个最小值？之四数组，Map这样的数据结构的性能瓶颈会在哪里？解决思路
Web开发jQueryHTML5AndroidIphonePHPJ2EEJ2SEC#C++Ajax
