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

作者:vkvi 来源:千一网络(原创) 日期: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...)

你前面那位网友看了:SQL Server 密码查看工具:Enterprise Manager PassView

▲▲▲嘿,欢迎转载传播本站原创文章,尽量保留来源噢。▲▲▲

文章评论
标题:必填
内容:
本站永远终止与捏造“罪名”不支付广告费的某度联盟合作。
vkvi
vkvi

作者简介: vkvi,致力于 .NET Web 开发、移动开发的技术推广,在 .NET、SQL Server、Windows Server 等方面有深入研究和丰富经验,10 年间共计撰写文章 4000 余篇。 主持金融、国土、农业、电商等多个行业项目执行, 推行“技术提升生产力、人心决定成功率”的管理理论。 联系他