找到不大于 A 且可被 B 整除的最大数的最有效方法

Question

我有2个号码A和B，我想找C = A - (A % B)，但是有些问题。首先，如果 C 和 D = A / B 应该具有相同的奇偶校验（（偶数和偶数）或（奇数和奇数）），否则 C 应该递增（++C）。第二个问题是我经常做这个计算，所以我希望它的成本尽可能小。现在我的解决方案是这样的：

uint32_t D = A / B;
C = D * B;
if ((C ^ D) & 0x1) ++C;

有更好的方法吗？也许 (C % 2) != (D % 2) 由于编译器优化而更快，但我无法证明这一点。我还想知道是否可以通过一些特定的英特尔功能（寄存器）来完成。

Answer 1

我假设输入 A 和 B 也是 uint32_t?

除法的成本使其他一切相形见绌 ，除非 B 在内联后的编译时已知。（即使它不是 2 的幂）。与其他任何指令相比，实际的 div 指令非常昂贵，并且无法使用 SIMD 进行矢量化。（x86 上唯一可用的 SIMD 除法是 FP，或者当然是除以 2 的整数移位）。

到目前为止，您可以做的最有用的事情是安排 B 的值在编译时对编译器可见，或者至少使用 link-time 优化交叉-文件内联。 (Why does GCC use multiplication by a strange number in implementing integer division?)

如果 B 不是编译时常量，x86 除法将免费产生余数和商。 sub比imul便宜，所以使用并让编译器优化：

uint32_t D = A / B;
uint32_t C = A - A % B;

如果 B 是一个编译时常量，编译器会将其优化为除法然后乘法，并且（希望）将其优化到与原始值一样好。

不，(C^D) ^ 1 应该是一种比 (C % 2) != (D % 2) 更有效的检查低位是否不同的方法。在组合之前对每个输入单独做一些事情会花费更多的指令，所以最好引导编译器朝着更高效的 asm 实现的方向发展。（显然，查看这两种情况的 asm 输出是个好主意）。

可能有用的是使用 + 而不是 ^。 XOR = 没有进位的加法，但你只关心低位。 ^ 和 + 的低位总是相同的。这使编译器可以选择使用 lea 指令进行复制和添加。（在这种情况下可能没有帮助；如果编译器破坏了寄存器中的值 D，假设它在这之后就死了。但是如果你也直接用D)[=32=]

当然，您实际上并不想使用 if(...) 进行分支，因此您应该将其写为：

C += (C+D) & 1;       // +1 if low bits differ

找到不大于 A 且可被 B 整除的最大数的最有效方法

Most efficient way to find the greatest number not greater than A, which is divisible by B

c++

math

x86

integer-division

micro-optimization