如何判断一个long int数为2的N次方用认为最简单的方法

gosapphire

前两天碰到的，我是用异或来做的，不知道有没有其它更简单的方法？
void ifTwothPower(const long int n)
{
        int i;
        int compareto = 1;

        for (i = 0; i < 64; i++)
        {
                if ( !(n^compareto) )
                {
                        std::cout << i << std::endl;
                        break;
                }
                compareto <<= 1;
        }
}

当时是想如果是2的N次方，不考虑符号的问题，所有bit位的和肯定为1，但是不知道怎么用c操作bit位。

cugb_cat

long int x = 1;
for (i = 0; i < sizeof(long int) * 8; i++) {
         if (n == x)
               break;
         x <<= 1;
}

gosapphire

多谢斑竹 我那个异或有点多余

不知道还有没有有没有其它的思路？

libinz

若a为2的N次方，则a最高位为1，其他位为0，那么(a-1)正好相反，只有最高位为0，其他位为1，
然后做a和（a-1）的 位与就行了，结果为0则a为2的N次方。

gosapphire

原帖由 libinz 于 2008-6-22 22:12 发表

若a为2的N次方，则a最高位为1，其他位为0，那么(a-1)正好相反，只有最高位为0，其他位为1，
然后做a和（a-1）的 位与就行了，结果为0则a为2的N次方。

忘了说，要打出N…………:wink:

libinz

那先求出数的二进制位数。

dianlongliu

还是觉得2楼的挺好的
mark

cugb_cat

原帖由 libinz 于 2008-6-22 22:12 发表

若a为2的N次方，则a最高位为1，其他位为0，那么(a-1)正好相反，只有最高位为0，其他位为1，
然后做a和（a-1）的 位与就行了，结果为0则a为2的N次方。

这个方法不错～～

gosapphire

自己google了一下

判断有多少个1可以这么做
x = (x & 0x55) + ((x >> 1) & 0x55);   
x = (x & 0x33) + ((x >> 2) & 0x33);   
x = (x & 0x0f) + ((x >> 4) & 0x0f);   
return x;

当时没想出来这么算有多少个1～

scutan

这是那本《高效程序的奥秘》上面的吧？