由判断一个数是不是 2、3、4 的幂引发的思考

技术 LeetCode

最近做了几道很有意思的题,判断一个整数是不是 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 的幂。

其次我们发现 2x+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 的幂,这便是我们日常中的开拓与巩固,在巩固过程中让自己真正理解了自己的思路。

创建于2019年11月20日 11:53
阅读量 14
留言列表

暂时没有留言

添加留言