给定一个大整数(以二进制形式存储)，如何快速测试它是否是 2 的幂，即相当于整数指数 k 的 2k？
一种简单但相当缓慢的方法是连续除以 2，直到数字变成 2 或存在非零余数。不幸的是，我们需要执行与数字一样多的除法。
对于小整数，有许多解决方案，包括位计数等。我对具有任意位数的整数的快速解决方案感兴趣。例如，我们可以通过一些快速整数除以 2 或其他技巧来加速上述方法吗？
我认为最快的方法仍然是检查位。假设你的数字是x，在java中你可以做x & (x - 1) == 0如果为真，那么它将是2的幂
对于 BigInteger，您可以执行x.and(x.subtract(BigInteger.ONE)).equals(BigInteger.ZERO)
从大数字中减去1是次优的，因为在 CPU 级别会有多个操作，包括大数字的进位，因为计算不适合累加器。
对于 CPU 上的计算，最快的方法是：
- 对于每个累加器大小的字节集(64 位数字上为 8 个字节，1
LOAD指令) - 检查数字是否为零(1
CMP指令) - 如果不是零，则将数字复制到另一个寄存器(1
JNZ指令) - 从新寄存器中的数字中减去
1(1SUB指令) - 和两个寄存器(1
AND指令) - 如果该值为零，请继续检查其余集合是否为纯零。(1
JZ指令)
为了优化，您需要将数字拆分为这样的集合并进行比较。
上述方法的主要优点是：通过做步骤(2)，我们摆脱了大的减法和进位。步骤 (4) 中的减法将只取一条指令，与零的比较也将取一条指令。所以它应该加快操作速度。
对于非常大的数字，此测试实质上相当于将所有字节与零进行比较，除了其中一个必须具有 2 的幂。我们可以专注于零的这个测试，而有效地检查非零则不那么重要。
最简单的形式是测试32或64位整数(即4或8个字节)是否为零(取决于寄存器大小)。
通过 SIMD 入侵可以实现更快的速度。在SSE2或AVX下，您可以获取16或32个字节，与零(具有预先清除的寄存器的_mm256_cmpeq_epi8/_mm256_cmpeq_epi8)进行比较，并使用_mm_movemask_epi8或_mm256_movemask_epi8打包为16或32位。然后，将生成的标量(短标量或整数标量)与所有标量进行比较。
[不幸的是，AVX512中似乎不存在相应的_mm512_movemask_epi8，它允许一次处理64个字节。
当您发现一组包含非零值的字节时，您可以使用包含 256 个条目的查找表逐个测试它们。
使用 SIMD 方法，您甚至可以通过另一个包含 256 个条目的查找表来加快速度，告诉字节中非零位的索引，或者在有多个非零位时提供保留值。使用此查找表两次或四次，您将知道 16 位或 32 位中的哪一位对应于非零字节(并且还会检测几个非零字节)。
利用配方n ^ (n - 1)的解决方案也是可能的。
如前所述，这些微优化可能毫无价值，除非你的大多数数字不是 2 的幂。
由于您只需要验证整个大整数的位填充是否1我想最快的方法可能是将大整数存储为uint32_t或更好的uint64_t数组，以便您可以使用popcntx86指令。
还有一些幼稚的方法，如使用SSE3指令PSHUFB，如这里所述，甚至其他方法仍然依赖于popcnt但使用手写汇编。
当然，这可能是矫枉过正的，因为你不需要人口计数，但你需要知道它是否正好是 1，但可能值得一试。
与此类优化问题一样，猜测是无关紧要的，唯一的选择是测试不同的方法，看看哪种方法更适合。