在C++20中测试正整数是否为2^n（即1、2、4、8等）的最有效方法？

Question

验证正整数

n

是否是 2 的幂（如 1、2、4、8 等）的一个简便方法是使用以下测试：

bool test = n & (n - 1) == 0;

此操作非常高效，因为它只涉及减法、按位与和比较（检查零标志）。如果这个表达式的计算结果为

true

，那么数字

n

确实是 2 的幂。

另一种方法使用

std::popcount

（人口计数）函数，它是C++20标准库的一部分，用于测试：

bool test = std::popcount(n) == 1; // (Since C++20)

此函数计算设置位（1）的数量。如果硬件支持弹出计数指令（POPCNT），此函数可以非常快。

在 C++ 中，您通常“按使用量付费”。对于此测试，计数没有用。

就 CPU 效率而言，什么是更好的方法？

Answer 1

bool test = std::has_single_bit(n);

std::has_single_bit

应转换为当前平台最有效的序列

template< class T >
constexpr bool has_single_bit( T x ) noexcept;

(C++20 起)

检查 x 是否是 2 的整数幂。

仅当 T 是无符号整数类型（即

unsigned char

、

unsigned short

、

unsigned int

、

unsigned long

、

unsigned long long

或扩展无符号整数类型）时，此重载才参与重载决策。

Answer 2

您希望代码的可读性如何？

   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0F0F0F0F;
   x = x + (x >> 8);
   x = x + (x >> 16);
   if (x == 1) {
   }

这是来自“Hacker's Delight”的位计数算法，这是有用的位敲击算法的古老宝库。

   x = x - ((x >> 1) & 0x55555555);

执行成对位加法。 请注意

000 >>1 = 000, 000 & 101 = 0
001 >>1 = 000, 000 & 101 = 0
010 >>1 = 001, 001 & 101 = 1
011 >>1 = 001, 001 & 101 = 1
100 >>1 = 010, 010 & 101 = 0
101 >>1 = 010, 010 & 101 = 0
110 >>1 = 011, 011 & 101 = 1
111 >>1 = 011, 011 & 101 = 1

因此

((x >> 1) & 0x555555555)

的作用就像每两位的“是 2 组”，按字内的顺序排列。

这意味着如果每对中设置了 2，则结果相减将减去 1，如果未设置则不减去任何内容。 在每对位中，您现在拥有该对的计数，存储在该对曾经所在的位置。

其他行则进行两两求和，将每对“2位”的计数相加，将每对“4位”的计数相加，将每对“8位”的计数相加，依此类推。 如果需要做两个64位字，可以额外添加一行。

最后，要查看是否设置了一位，请检查计数是否等于 1。

请注意，虽然考虑起来很有趣，但最好使用

std::has_single_bit

，它使用相同的算法（但参数化以处理不同长度的单词，并检查位数（我正在谈论的算法）是否等于1. 上述解决方案适用于 32 位字，但可以轻松更改为 64 位字。

https://github.com/gcc-mirror/gcc/blob/bd3a312728fbf8c35a09239b9180269f938f872e/libstdc%2B%2B-v3/include/std/bit#L325

黑客的喜悦https://learning.oreilly.com/library/view/hackers-delight-second/9780133084993/