le_*_*e_m 0 algorithm biginteger
给定一个大整数(以二进制形式存储),如何快速测试它是否为2的幂,即对于整数指数k等于2？
一个简单但相当慢的方法是连续除以2直到数字变为2或者存在非零余数.不幸的是,我们需要执行尽可能多的分区,因为我们的号码中有数字.
对于小整数,有许多解决方案,包括位计数等.我对具有任意位数的整数的快速解决方案感兴趣.例如,我们可以通过一些快速整数除以2或其他欺骗加速上述方法吗？
gab*_*oft 10
我认为最快的方法仍然是检查这些位.假设你的数字是x,在java中你可以做到,x & (x - 1) == 0如果是真的那么它将是2的幂
对于BigInteger你可以做到 x.and(x.subtract(BigInteger.ONE)).equals(BigInteger.ZERO)