代码之家 › 专栏 › 技术社区 › Amit

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

c++20 std performance c++

Amit · 技术社区 · 1 年前

一种方便的方法来验证数字是否 n 是二的幂(如2、4、8等)是使用以下测试:

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

此操作可能非常高效,因为它只涉及减法、逐位AND和比较。如果此表达式的计算结果为 true ,然后是数字 n 实际上是二的幂。

另一种方法使用 std::popcount (总体计数)函数,它是C++20标准库的一部分,用于测试:

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

此函数统计中的设置位(1)的数量。如果硬件支持popcount指令(POPCNT),则此函数可以非常快。

在C++中,你通常会为你使用的东西付费。这个测试没有计数的用处。

就CPU效率而言,什么是更好的方法?

2 回复 | 直到 1 年前

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

Edwin Buck 1 年前

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

   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/