最近做了几道很有意思的题，判断一个整数是不是 2、3、4 的幂。在求解的过程中引发了一些思考，记在这里。
判断 n 是否为 2 的幂
如果 n 是 2 的幂且 n 为整数，必然可表示为二进制的 0b1000.....0，我们可以发现 n -1 可表示为 0b11...1，二者进行与运算，结果必定为 0。其他任何数与 n 做与运算，结果必定大于0。
因此符合 n & (n-1) == 0 的数为 2 的整数次幂。
这里还有另外一种方法。
我们随便找到一个 2 的整数幂，例如 64，我们将 64 进行因数分解，64 = 2 * 2 * 2 * 2 * 2 * 2。64 的因数必定为 2 的整数幂。因此只要一个数字能被 64 整除，该数必定为 2 的幂。
在 int64 范围内的最大的 2 的幂是 1<<62，也就是 4611686018427387904。符合 4611686018427387904 % n == 0 的数为 2 的整数次幂。
判断 n 是否为 3 的幂
我们将上边 2 的整数幂的第二个算法推广，便可以得出完全一样的判断是否为 3 的幂的算法。
27 = 3 * 3 * 3 * 1，因此 1，3，9，27 都是 3 的幂。
在 int64 范围内的最大的 3 的幂是 4052555153018976267，符合 4052555153018976267 % n == 0 的数为 3 的整数次幂。
判断 n 是否为某个素数的幂
将上边的算法进行再次推广，我们发现这个方法适合于任何的素数。
一个素数的幂必定所有的因数都是该素数的幂。
因此我们可以在整数范围内找到最大的该素数的幂，然后用这个数对 n 进行取余，结果为 0 则为该素数的幂。
判断 n 是否为 4 的幂
4 不是素数，所以上边的适用于素数的办法并不适合4。
例如 16 = 4 * 4，同时 16 = 8 * 2， 8 和 2 都不是 4 的幂。
对于 4 我们进行观察，首先发现 4 的幂必定为 2 的幂。
其次我们发现 2*x+1 位为 1，其他位为 0。
因此这个数与 0x[01]…[01] 进行与运算必定为它本身。不符合这样的数进行运算则为 0 。
我们在 int 范围内找到最大的数是 6148914691236517205 。所有符合 (6148914691236517205 & num == num) && (4611686018427387904 % num == 0) 的数为 4 的幂。
判断 n 是否为 8、16、32、64 … 的幂
对上边的结论再次推广，8 的幂的 3x+1 位必定为1，16 的幂的 4x+1 位必定为 1。
因此我们可以用类似 0b[001]…[001] 和 0b[0001]…[0001] 的方式来判断 8(23) 和 16(24) 的幂，也就是适用所有的 2n 的幂。
小结
我们在学习过程中总是会遇到各种各样的问题，在懂得相应的原理之后更应该多多思考，举一反三，很多时候会发现自己吃遇到的不仅仅是一个问题，而是一种广泛的思路。由 2、3 的思路我们可以推广到所有的素数，由 2、4 的思路我们可以推广到所有的 2 的幂，这便是我们日常中的开拓与巩固，在巩固过程中让自己真正理解了自己的思路。