测试一个大整数是否是 2 的幂
Test if a big integer is a power of two
给定一个大整数（以二进制形式存储），我如何快速测试它是否是 2 的幂，即等于整数指数 k 的 2ᵏ？
一个简单但比较慢的方法是不断除以2，直到数变成2或者余数不为零。不幸的是，我们需要执行与数字中的数字一样多的除法。
对于小整数，有很多解决方案，包括位计数等。我对具有任意位数的整数的快速解决方案感兴趣。例如。我们可以通过一些快速整数除以 2 或其他技巧来加速上述方法吗？
我认为最快的方法仍然是检查位。假设你的数字是 x，在 java 中你可以做 x & (x - 1) == 0 如果为真那么它将是 2
的幂
对于 BigInteger 你可以做 x.and(x.subtract(BigInteger.ONE)).equals(BigInteger.ZERO)
由于您只需要验证整个大整数的位填充是否为 1 我想最快的方法可能是将大整数存储为 uint32_t 或更好的数组 uint64_t 这样你就可以使用 popcnt x86 指令。
也有使用 SSE3 指令 PSHUFB 的幼稚方法，如 here, and even other approaches 所述，它仍然依赖于 popcnt，但使用手写汇编。
当然这可能有点矫枉过正，因为您不需要人口计数，但您需要知道它是否恰好为 1，但这也许值得一试。
与往常一样，在此类优化问题中，猜测是无关紧要的，唯一的选择是测试不同的方法，看看哪种方法更合适。
从大数中减去 1 不是最优的，因为在 CPU 级别会有多个操作，包括大数的进位，因为计算不适合累加器.
对于 CPU 的计算，最快的方法是：
- 对于每个累加器大小的字节集（64 位数字上的 8 个字节，1
LOAD 指令）
- 检查数字是否为零（1
CMP 指令）
- 如果不为零，将数字复制到另一个寄存器（1
JNZ指令）
- 从新寄存器中的数字中减去
1（1 SUB指令）
- AND 两个寄存器（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 或 [ 打包为 16 或 32 位=13=]。然后，将生成的标量（short 或 int）与所有标量进行比较。
[不幸的是，在 AVX512 中似乎不存在相应的 _mm512_movemask_epi8，它允许一次处理 64 个字节。]
当您找到一组包含非零值的字节时，您可以使用对 256 个条目的查找-table 逐一测试它们。
使用 SIMD 方法，您甚至可以通过另一个查找来加快速度-table 256 个条目告诉一个字节中非零位的索引，或者当有多个非零位时的保留值位。使用此查找 table 两次或四次，您将知道 16 位或 32 位中的哪一个对应于非零字节（并且还会检测到几个非零字节）。
利用公式 n ^ (n - 1) 的解决方案也是可能的。
如前所述，这些微优化可能毫无价值，除非您的大多数数字不是 2 的幂。
给定一个大整数（以二进制形式存储），我如何快速测试它是否是 2 的幂，即等于整数指数 k 的 2ᵏ？
一个简单但比较慢的方法是不断除以2，直到数变成2或者余数不为零。不幸的是，我们需要执行与数字中的数字一样多的除法。
对于小整数，有很多解决方案，包括位计数等。我对具有任意位数的整数的快速解决方案感兴趣。例如。我们可以通过一些快速整数除以 2 或其他技巧来加速上述方法吗？
我认为最快的方法仍然是检查位。假设你的数字是 x，在 java 中你可以做 x & (x - 1) == 0 如果为真那么它将是 2
对于 BigInteger 你可以做 x.and(x.subtract(BigInteger.ONE)).equals(BigInteger.ZERO)
由于您只需要验证整个大整数的位填充是否为 1 我想最快的方法可能是将大整数存储为 uint32_t 或更好的数组 uint64_t 这样你就可以使用 popcnt x86 指令。
也有使用 SSE3 指令 PSHUFB 的幼稚方法，如 here, and even other approaches 所述，它仍然依赖于 popcnt，但使用手写汇编。
当然这可能有点矫枉过正，因为您不需要人口计数，但您需要知道它是否恰好为 1，但这也许值得一试。
与往常一样，在此类优化问题中，猜测是无关紧要的，唯一的选择是测试不同的方法，看看哪种方法更合适。
从大数中减去 1 不是最优的，因为在 CPU 级别会有多个操作，包括大数的进位，因为计算不适合累加器.
对于 CPU 的计算，最快的方法是：
- 对于每个累加器大小的字节集（64 位数字上的 8 个字节，1
LOAD指令） - 检查数字是否为零（1
CMP指令） - 如果不为零，将数字复制到另一个寄存器（1
JNZ指令） - 从新寄存器中的数字中减去
1（1SUB指令） - AND 两个寄存器（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 或 [ 打包为 16 或 32 位=13=]。然后，将生成的标量（short 或 int）与所有标量进行比较。
[不幸的是，在 AVX512 中似乎不存在相应的 _mm512_movemask_epi8，它允许一次处理 64 个字节。]
当您找到一组包含非零值的字节时，您可以使用对 256 个条目的查找-table 逐一测试它们。
使用 SIMD 方法，您甚至可以通过另一个查找来加快速度-table 256 个条目告诉一个字节中非零位的索引，或者当有多个非零位时的保留值位。使用此查找 table 两次或四次，您将知道 16 位或 32 位中的哪一个对应于非零字节（并且还会检测到几个非零字节）。
利用公式 n ^ (n - 1) 的解决方案也是可能的。
如前所述，这些微优化可能毫无价值，除非您的大多数数字不是 2 的幂。