如何快速判断一个数是不是 2 的乘方?

作者:vkvi 来源:ITPOW(原创) 日期:2009-4-8

最简单的方法,判断 (i & (i - 1)) == 0 的结果。

因为他是 2 的乘方,所以二进制数一定是第一位是 1,后面的都是 0。(见后面的证明)

这样,如果他减 1,将是除了第一位为 0,其余的都是 1,如果他们按位与运算肯定是 0 啊!

证明“因为他是 2 的乘方,所以二进制数一定是第一位是 1,后面的都是 0。”

由于上述中使用了“一定”这类词语,所以我们来简单证明一下。

2 的 0 次幂(1)的二进制是 1

2 的 1 次幂(2)的二进制是 10

2 的 2 次幂(4)的二进制是 100

于是,设 2 的 n 次幂的二进制是 1 后面跟 n 个零,如果能够证明 2 的 n+1 次幂的二进制是 1 后面跟 n+1 个零,就可以得出结论。

根据同底数幂的乘法规则 a^m×a^n=a^(m+n),可得出 a^(n+1) = a^n×a^1。

把 2 代入 a,得 2^(n+1) = 2^n×2 = 2^n + 2^n。

转换成二进制为:

   1(...n 个 0...)
  +1(...n 个 0...)
------------------------
  10(...n 个 0...)
------------------------
  1(...n+1 个 0...)
相关文章