如何判断一个数是否是2的N次方

今天写一个小程序, 一个功能是用二进制位代表某种属性, 而程序则是图形化的配置这个功能

于是, 就遇到了如何检测配置值是否是2的N次方形式的检测, 解决方法目前想到的有如下几种

1.定义法

由于N次方(幂)为N个数相乘,那么反过来一直除以这个数最终的结果将为1,且余数总是零

int IsPower2(int n)
{
while(n)
{
if(n % 2) return 0;
n /= 2;// n = n / 2;
if(n == 1) return 1;
}
return 0;
}

2.儿童法

小时候我们可是学过数手指头的, 难不了我!(最笨的办法很管用)

int IsPower2(int n)
{
char sz[36], *p;
int c;

itoa(n, sz, 2);// sprintf(sz, "%x", n);
p = sz;
c = 0;
while(*p)
{
if(*p == '1')
{
c++;
if(c > 1) return 0;
}
p++;
}
if(c == 0) return 0;
return 1;
}

3.投机法(袁世凯说: 窃国者为诸侯)

一个单2进制位的数减一的结果是: 该位为0, 地位全部为1, 如8=1000B, 7=0111B,两者相与8 & 7 == 0

如果地位有1,如10=1010B, 9=1001B,该位不变, 高位有1高位不变,因此几条CPU指令即可判断是否为2次幂形式

int IsPower2(int n)
{
if(c <= 0) return 0;
if(i & (i - 1)) return 0;
return 1;
}

使用VB的朋友参考

Public Function IsPower2(ByVal n As Long) As Boolean
    If n <= 0 Then Exit Function
    If (n And (n - 1)) Then Exit Function
    IsPower2 = True
End Function

由于C/C++反复使用寄存器来暂存, 在确保是Intel x86兼容的CPU时可以使用naked内联汇编瞬间完成

当然啦, 如果对其他的CPU指令熟悉, 内联其他指令或者直接emit也是ko以的

内联汇编在之前的很多文章里提到, 这里省略,吃饭先...

2015-10-16 18:18:18