测试一个大整数是否为2的幂

Question

给定一个大整数(以二进制形式存储)，如何快速测试它是否为2的幂，即对于整数指数k等效于2ᵏ？

一个简单但相当慢的方法是连续除以2，直到这个数变成2，或者有一个非零余数。不幸的是，我们需要尽可能多的表现，因为我们的数字中有数字。

对于小整数，有很多的解，包括位计数等。我对任意数字数的整数的快速解感兴趣。我们能不能通过一些快速整数除以2或其他诡计来加速上述方法？

Answer 1

我认为最快的方法仍然是通过检查比特。假设你的数字是x，在java中你可以做x & (x - 1) == 0，如果是真的，那么它就是2的幂。

对于BigInteger，您可以执行x.and(x.subtract(BigInteger.ONE)).equals(BigInteger.ZERO)

Answer 2

从一个大的数字中减去1是次优的，因为在CPU级别上将有多个操作，包括一个大数的进位，因为计算不适合累加器。

对于CPU上的计算，最快的方法是：

1. 对于每个累加器大小的字节集(64位数字上的8个字节，一个LOAD指令)
2. 检查数字是否为零(1 CMP指令)
3. 如果不是零，将号码复制到另一个寄存器(1 JNZ指令)
4. 从新寄存器中的数字中减去1 (1 SUB指令)
5. 和两个寄存器(1 AND指令)
6. 如果值为零，则继续检查其余的集合是否为纯零。(1 JZ指令)

为了进行优化，您需要将数字分割成这样的集合并进行比较。

上述方法的主要优点是:通过执行步骤(2)，我们消除了大减法和进位。步骤(4)中的减法将精确地使用一条指令，而与零的比较也将使用一条指令。所以它应该加速行动。

Answer 3

对于真正大的数字，这个测试实质上相当于将所有字节与零进行比较，除了其中一个字节必须保持2的幂。我们可以专注于这个测试的零，而有效地检查非零是不重要的。

最简单的形式是测试32或64位整数(即4或8字节)为零(取决于寄存器大小)。

通过SIMD导入可以实现更快的速度。在SSE2或AVX下，您可以获取16或32个字节，比较零(_mm256_cmpeq_epi8/_mm256_cmpeq_epi8和预清除寄存器)，并使用_mm_movemask_epi8或_mm256_movemask_epi8将其打包为16或32位。然后，将结果标量(短或int)与所有标量进行比较。

不幸的是，在AVX512中似乎没有相应的AVX512，它允许一次处理64个字节。

当您找到一组包含非零值的字节时，可以使用一个由256个条目组成的查找表逐一测试它们。

使用SIMD方法，您甚至可以通过另一个由256个条目组成的查找表来加快速度，该表指示一个字节中的非零位的索引，或者当有几个非零位时保留值。使用此查找表两次或四次，您将知道16位或32位中哪一位对应于一个非零字节(并检测到几个非零字节)。

利用公式n ^ (n - 1)的解决方案也是可能的。

如前所述，这些微优化可能毫无价值，除非你的大多数数字不是2的幂。