如何判断一个数是4的整数次幂

novice2008 2009-02-06 11:41:55

加精

...全文

7257 193 打赏收藏转发到动态举报

写回复

用AI写文章

193 条回复

切换为时间正序

请发表友善的回复…

发表回复

吉祥衰宝 2012-11-01

打赏
举报

真是眼前一亮，二进制，哈哈[Quote=引用 10 楼的回复:]
4^i = 2^(2*i)
判断该数的二进制形式是否为1后面跟了偶数个0就可以了
100..000 (2*i)个0
[/Quote]

JackBurd 2012-10-31

打赏
举报

[Quote=引用 12 楼的回复:]

bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}
[/Quote]

这个才是最N的。。。

______CQ_ 2012-08-08

打赏
举报

4是2的2次方。。2的偶数次方必然是4的整数次方。。二进制与十进制之间就是用2来搞的。所以12楼正解

______CQ_ 2012-08-08

打赏
举报

[Quote=引用 12 楼的回复:]

bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}
[/Quote]
这是对的

4是2的2次方。。而二进制与十进制之间就是用2来搞的。所12楼正解。。

______CQ_ 2012-08-08

打赏
举报

著一 2012-08-08

打赏
举报

觉得这个理解很透彻！[Quote=引用 73 楼的回复:]
总结：
一、四的N次幂的形式
4的N次幂应该是：
二进制十进制
1 1 //0次幂
100 4 //1次幂
10000 16 //2次幂
1000000 64 //3次幂
100000000 256 //4次幂
...
（参考70楼）

二、特点
该数的任何二进制只有一个1
所以x&(x-1)都等于0.
（参考72楼）

4的N次幂的十进制……
[/Quote]

SongSaiGa 2012-08-07

打赏
举报

其他兄台的算法也能实现，但都是O(n)及以上级别的，这个才是O(1)级别的
[Quote=引用 12 楼的回复:]

bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}
[/Quote]

过往记忆 2012-08-05

打赏
举报

[Quote=引用 66 楼的回复:]

个人感觉可以改成
bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
else return true；
}
[/Quote]

你改错了，else return true；考虑的不周全，当x = 2时，x & (x - 1)也返回0所以会运行else部分，肯定是错的。

hanqing828 2012-07-20

打赏
举报

进来学习了，这么多说的，谁的才是正确的呢，得试一下，，

CoolEgos 2011-12-17

打赏
举报

[Quote=引用 24 楼 funfunqi 的回复:]

太简单了吧，不断除以4，只要判断最后小于4的商是否为1，每次除四余数的和是否为 0 就行了，有那么复杂？？

C/C++ code
#include <stdio.h>
int main(void)
{
int x, i, j = 0; //i是商，j表示余数
scanf("%d", &x);
i = x;
for(; i >= 4;)
……
[/Quote]这种方法是对的，也比较简单，不过这个程序有问题。输入1、4等等就有问题

fcjxxl 2011-11-03

打赏
举报

12L效率最高

wjain 2011-11-01

打赏
举报



/**

 * @file   IntegralPowerOfFour.c

 * @author Jain <Jain_Y@126.com>

 * @date   Tue Nov 01 16:19:31 2011

 * 

 * @brief  This is detect whether a integer is an integral power of four.

 * 

 * 

 */



#include <stdio.h>

#include <stdbool.h>



bool isPowerOfFour();



int main(int argc, char *argv[])

{

    long number = 0;

    printf("Please input a integer: ");

    scanf("%ld", &number);

    if (isPowerOfFour(number))

    {

        printf ("%ld is an integral power of 4.\n", number);

    }

    else

    {

        printf ("%ld is not an integral power of 4.\n", number);

    }    



    return 0;

}



bool isPowerOfFour(long number)

{

    long quotient = number;

    short remainder = -1;

    

    while(true)

    {

        remainder = quotient%4;        

        quotient /= 4;

        if (quotient < 4)

        {

            break;            

        }

    }

    if (1 == quotient && 0 == remainder)

    {

        return true;        

    }

    return false;    

}

wfeng_neusoft 2011-10-31

打赏
举报

[Quote=引用 85 楼 gzamao 的回复:]

1, 若一个数为2的n次方,则二进制可表示为1后有n个零.(证明略)
2, 如果一个数(设之为x)乘以(2的n次方), 则二进制可表示为x后加n个零.(证明略)
以上两个应该是程序员必知了.

我们再看4的n次方的构成:
4^n= (2*2)^n = (2^n) * (2^n)
设x=2^n 则上式= x * (2^n)
因为x为2的n次方,所以二进制度可表示为1后有n个零
所以……
[/Quote]
up

Li103ZzZ 2011-07-19

打赏
举报

[Quote=引用 12 楼 iceheart 的回复:]
bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}
[/Quote]

想法不错

pmc_peter 2011-05-23

打赏
举报

[Quote=引用 11 楼 dongpy 的回复:]
C/C++ code
bool func( int x )
{
while ( x > 1 )
{
if ( x % 4 )
{
return false;
}
x = x /4;
}
return true;
}
[/Quote]

个人认为这段代码比较好

aboutin 2011-05-17