Java编程

幂次方学院数据结构

怎么快速判断一个正整数是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

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注