C/C++快速判断一个数是不是2的乘幂

1.对有符号整数,我们可以用下面直接的方法判断是不是2的幂次方,i=2^n:

对于非整数,答案是false。输入1或2,返回true,因为2^0=1,2^1=2。对于其它数,每次乘2,判断是不是2的幂次方。上面代码的时间复杂度为O(log(n))。

2.使用math.h 中的log2()函数,检查一个数的对数是不是足够小。如果它的对数接近0,那么这个数就是2的幂次方,代码如下:

上面代码的性能严重依赖log2的实现,在大多数平台,它的时间复杂度成O(1)。

3.最快的方法应该是使用2进制逻辑运算。对于整数对应的2进制,如果是2的幂次方,那么它的二进制形式应该是一个单独的1,右面的所有位为0。因此我们可以判断 n & (n – 1) == 0, 例如8的二进制表示为01000,01000 & 00111 == 0,所以8是2的幂次方。代码如下:

它的时间复杂度是O(1),他比前面两种方法快了大概178倍。

相关文章

发表评论

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