今天看到一个这样的题目:判断一个整数是不是 2 的整数次方?
大学竞赛好像还真见过,现在已经忘得一干二净了。现在看到一个解法还真的挺溜。
首先按照二进制找规律
- 2 => 10
- 4 => 100
- 8 => 1000
- 16=> 10000
- …
下面就不写了,第一位为 1 后面全是 0,这样的数就是 2 的整数次方数。
二进制算法中还有一个规律
8 => 1000
7 => 0111
16=> 10000
15=> 01111
N 和 N-1 的区别是最低位的 1 变成 0,最低位后面的 0 全变成 1,并且 N&(N-1)可以恰好为 0。
如果 N=1100,N&(N-1) = 1100&1011 != 0,所以 N 不是 2 的整数次数。
综上所述 :判断一个整数是不是 2 的整数次方,只需要判断 N&(N-1) 是否为 0。