C++ signed 和 unsigned int 与 long long 速度

Question

今天，我注意到在我的 64 位计算机上 int、unsigned、long long 和 unsigned long long 几个简单的位运算和算术运算的速度差异很大个人电脑

特别是，下面的循环对于 unsigned 的速度大约是 long long 的两倍，这是我没想到的。

int k = 15;
int N = 30;
int mask = (1 << k) - 1;
while (!(mask & 1 << N)) {
    int lo = mask & ~(mask - 1);
    int lz = (mask + lo) & ~mask;
    mask |= lz;
    mask &= ~(lz - 1);
    mask |= (lz / lo / 2) - 1;
}

（完整代码 here）

以下是时间（以秒为单位）（g++ -O、-O2 和 -O3）：

1.834207723 (int)
3.054731598 (long long)
1.584846237 (unsigned)
2.201142018 (unsigned long long)

这些时间非常一致（即 1% 的差值）。没有-O标志，每个都慢一秒左右，但是相对速度是一样的。

有明确的理由吗？向量化可能适用于 32 位类型，但我看不到巨大的位置 long long 和 unsigned long long 的区别来自于。有些操作在某些类型上比在其他类型上慢得多吗？还是 64 位类型较慢（即使在 64 位架构上）只是普遍现象？

对于那些感兴趣的人，这个循环遍历 {1,2,...,30} 的所有子集，正好有 15 个元素。这是通过循环（按顺序）所有小于 1<<30 且设置了 15 位的整数来完成的。对于当前情况，这是 155117520 次迭代。我不知道这段代码的来源了，但是 post 解释了更多。

编辑

从汇编代码看来，当类型是无符号时，除法可以更快。我认为这是有道理的，因为我们不必考虑符号位。

此外，32位操作使用movl和其他xxxl指令，而 64 位操作使用 movq 和 xxxq.

编辑 2

看完我链接的post后，我决定使用那边给出的公式：

T k = 15;
T N = 30;
T mask = (1 << k) - 1;
while (!(mask & 1 << N)) {
    T t = mask | (mask - 1);
    mask = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(mask) + 1));
}

它的运行时间大约是上面代码 post 的三分之一，并且对所有四种类型使用相同的时间。

Answer 1

您代码中最慢的操作是

mask |= (lz / lo / 2) - 1

32 位除法比 64 位除法快得多。例如，在 Ivy Bridge 上，32 位 IDIV 需要 19-26 个时钟，而 64 位 IDIV 需要 28-103 个时钟延迟。

无符号版本也比有符号版本快，因为在无符号情况下除以 2 只是简单的位移，并且没有大小扩展调用（CDQ、CQO）。

在无符号的情况下是简单的位移，而在有符号的情况下

[1] http://www.agner.org/optimize/instruction_tables.pdf

C++ signed 和 unsigned int 与 long long 速度

C++ signed and unsigned int vs long long speed

c++

performance

bit-manipulation

编辑

编辑 2