在C++20中测试一个数字是否为2^n(即2,4,8等)的最有效方法是什么?

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 ,或扩展的无符号整数类型)。

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

   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) {
   }

这是“黑客的喜悦”中的比特计数算法,这是一个有用的比特撞击算法的古老宝库。

   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/