有效地将无符号值除以 2 的幂，向上舍入
Efficiently dividing unsigned value by a power of two, rounding up
我想实现 unsigneda 整数除法 任意二的幂，四舍五入，高效。所以从数学上讲，我想要的是 ceiling(p/q)0。在 C 中，不利用 q 限制域的 strawman 实现可能类似于以下函数 1:
/** q must be a power of 2, although this version works for any q */
uint64_t divide(uint64_t p, uint64_t q) {
uint64_t res = p / q;
return p % q == 0 ? res : res + 1;
}
...当然，我实际上并不想在机器级别使用除法或 mod，因为即使在 mod 现代硬件。我正在寻找使用 shifts and/or 一些其他廉价操作的强度降低 - 利用 q 是 2 的幂这一事实。
你可以假设我们有一个高效的 lg(unsigned int x) 函数，如果 x 是二次幂，它 returns x 的 base-2 对数.
如果 q 为零，未定义的行为是可以的。
请注意，简单的解决方案：(p+q-1) >> lg(q) 通常不起作用 - 例如尝试使用 p == 2^64-100 and q == 2562。
uint64_t exponent = lg(q);
uint64_t mask = q - 1;
// v divide
return (p >> exponent) + (((p & mask) + mask) >> exponent)
// ^ round up
"round up"部分的单独计算避免了(p+q-1) >> lg(q)的溢出问题。根据您的编译器的智能程度，可以将 "round up" 部分表示为 ((p & mask) != 0) 而无需分支。
你可以这样做，比较除以 n / d 和除以 (n-1) / d。
#include <stdio.h>
int main(void) {
unsigned n;
unsigned d;
unsigned q1, q2;
double actual;
for(n = 1; n < 6; n++) {
for(d = 1; d < 6; d++) {
actual = (double)n / d;
q1 = n / d;
if(n) {
q2 = (n - 1) / d;
if(q1 == q2) {
q1++;
}
}
printf("%u / %u = %u (%f)\n", n, d, q1, actual);
}
}
return 0;
}
程序输出：
1 / 1 = 1 (1.000000)
1 / 2 = 1 (0.500000)
1 / 3 = 1 (0.333333)
1 / 4 = 1 (0.250000)
1 / 5 = 1 (0.200000)
2 / 1 = 2 (2.000000)
2 / 2 = 1 (1.000000)
2 / 3 = 1 (0.666667)
2 / 4 = 1 (0.500000)
2 / 5 = 1 (0.400000)
3 / 1 = 3 (3.000000)
3 / 2 = 2 (1.500000)
3 / 3 = 1 (1.000000)
3 / 4 = 1 (0.750000)
3 / 5 = 1 (0.600000)
4 / 1 = 4 (4.000000)
4 / 2 = 2 (2.000000)
4 / 3 = 2 (1.333333)
4 / 4 = 1 (1.000000)
4 / 5 = 1 (0.800000)
5 / 1 = 5 (5.000000)
5 / 2 = 3 (2.500000)
5 / 3 = 2 (1.666667)
5 / 4 = 2 (1.250000)
5 / 5 = 1 (1.000000)
更新
我发布了对原问题的早期答案，这个答案有效，但没有考虑算法的效率，或者除数总是 2 的幂。执行两次除法是不必要的昂贵。
我在 64 位系统上使用 MSVC 32 位编译器，因此我不可能为所需目标提供最佳解决方案。但这是一个 有趣的问题 所以我四处摸索发现最好的解决方案是发现 2**n 除数的位。使用库函数 log2 可以，但速度太慢了。自己轮班要好得多，但我最好的 C 解决方案仍然是
unsigned roundup(unsigned p, unsigned q)
{
return p / q + ((p & (q-1)) != 0);
}
我的内联 32 位汇编器解决方案更快，但当然不能回答问题。我通过假设 eax 作为函数值返回来窃取了一些周期。
unsigned roundup(unsigned p, unsigned q)
{
__asm {
mov eax,p
mov edx,q
bsr ecx,edx ; cl = bit number of q
dec edx ; q-1
and edx,eax ; p & (q-1)
shr eax,cl ; divide p by q, a power of 2
sub edx,1 ; generate a carry when (p & (q-1)) == 0
cmc
adc eax,0 ; add 1 to result when (p & (q-1)) != 0
}
} ; eax returned as function value
如果 p 大于 2 的幂（哎呀），我的旧答案就不起作用了。所以我的新解决方案，使用 __builtin_ctzll() 和 __builtin_ffsll() 函数 0 在 gcc 中可用（作为奖励，提供你提到的快速对数！ ):
uint64_t divide(uint64_t p,uint64_t q) {
int lp=__builtin_ffsll(p);
int lq=__builtin_ctzll(q);
return (p>>lq)+(lp<(lq+1)&&lp);
}
请注意，这是假设 long long 是 64 位。否则必须稍微调整一下。
这里的想法是，当且仅当 p 的尾随零比 q 少时我们才需要溢出。请注意，对于 2 的幂，尾随零的数量等于对数，因此我们也可以将此内置函数用于对数。
&&lp 部分仅针对 p 为零的极端情况：否则它将在此处输出 1。
0 不能对两者都使用 __builtin_ctzll() 因为如果 p==0.
它是未定义的
如果您的编译器使用算术右移（通常为真），这似乎很有效并且适用于带符号的情况。
#include <stdio.h>
int main (void)
{
for (int i = -20; i <= 20; ++i) {
printf ("%5d %5d\n", i, ((i - 1) >> 1) + 1);
}
return 0;
}
用>> 2除以4，>> 3除以8，等等。高效 lg 完成那里的工作。
你甚至可以除以1！ >> 0
C 中无符号整数除以 2 的幂的有效方法是右移 -- 右移一位除以二（向下舍入），因此右移 n 除以 2n（向下舍入）。
现在你想向上舍入而不是向下舍入，你可以先加上 2n-1，或者等价地减去班前加一，班后加一（0除外）。结果类似于：
unsigned ceil_div(unsigned d, unsigned e) {
/* compute ceil(d/2**e) */
return d ? ((d-1) >> e) + 1 : 0;
}
条件可以去掉，用d的布尔值加减一：
unsigned ceil_div(unsigned d, unsigned e) {
/* compute ceil(d/2**e) */
return ((d - !!d) >> e) + !!d;
}
由于其大小和速度要求，该函数应设为静态内联。它可能不会对优化器产生影响，但参数应该是常量。如果必须在多个文件之间共享，请将其定义为 header:
static inline unsigned ceil_div(const unsigned d, const unsigned e){...
Efficiently dividing unsigned value by a power of two, rounding up
[重写] 给定 OP .
当溢出不是问题时，圆角或天花板部分很容易。简单添加 q-1，然后移位。
否则，由于舍入的可能性取决于p小于q的所有位，因此在移出这些位之前需要先检测这些位。
uint64_t divide_A(uint64_t p, uint64_t q) {
bool round_up = p & (q-1);
return (p >> lg64(q)) + round_up;
}
这假设代码具有高效的 lg64(uint64_t x) 函数，如果 x 是二次幂，则 returns x 的 base-2 对数。 `
这个答案是关于什么是 asm 的理想；我们想说服编译器为我们发出什么。 （我不建议实际使用内联汇编，除非在对编译器输出进行基准测试时作为比较点。https://gcc.gnu.org/wiki/DontUseInlineAsm）。
我确实设法从 ceil_div_andmask 的纯 C 中获得了相当不错的 asm 输出，见下文。（它比 Broadwell/Skylake 上的 CMOV 更糟糕，但在 Haswell 上可能不错。不过，user23/chux 版本在这两种情况下看起来都更好。）它主要是值得一提的，因为它是我让编译器发出我想要的 asm 的少数情况之一。
Chris Dodd 关于 return ((p-1) >> lg(q)) + 1 的一般想法以及 d=0 的特殊情况处理似乎是最好的选择之一。 IE。它在 asm 中的最佳实现很难与其他任何东西的最佳实现相提并论。 Chux 的 (p >> lg(q)) + (bool)(p & (q-1)) 也有优势（比如 p->result 的延迟较低），并且当相同的 q 用于多个分区时更多 CSE。请参阅下面的 latency/throughput 分析 gcc 用它做什么。
如果相同的e = lg(q)被重复用于多个被除数，或者同一个被除数被重复用于多个除数，不同的实现可以CSE更多的表达式。 他们还可以使用 AVX2 进行有效矢量化。
Branches are cheap and very efficient if they predict very well，所以在 d==0 上分支是最好的，如果它几乎从未被采用。如果 d==0 不罕见，branchless asm 平均表现会更好。理想情况下，我们可以用 C 编写一些东西，让 gcc 在配置文件引导的优化过程中做出正确的选择，并在任何情况下编译成良好的 asm。
由于最好的无分支 asm 实现与分支实现相比不会增加太多延迟，因此无分支可能是可行的方法，除非分支可能在 99% 的时间内以相同的方式运行。这可能适用于 p==0 上的分支，但不太可能适用于 p & (q-1).
上的分支
很难引导 gcc5.4 发出任何最佳的东西。 This is my work-in-progress on Godbolt).
我认为Skylake对于这个算法的最优序列如下。 （显示为 AMD64 SysV ABI 的独立函数，但谈论 throughput/latency 假设编译器将发出类似内联到循环中的内容，没有附加 RET）。
分支从计算 d-1 到检测 d==0，而不是单独的测试 & 分支。很好地减少了 uop 计数，尤其是在 JC 可以与 SUB 宏融合的 SnB 系列上。
ceil_div_pjc_branch:
xor eax,eax ; can take this uop off the fast path by adding a separate xor-and-return block, but in reality we want to inline something like this.
sub rdi, 1
jc .d_was_zero ; fuses with the sub on SnB-family
tzcnt rax, rsi ; tzcnt rsi,rsi also avoids any false-dep problems, but this illustrates that the q input can be read-only.
shrx rax, rdi, rax
inc rax
.d_was_zero:
ret
- 融合域微指令：5（不包括 ret），其中之一是异或零（无执行单元）
- HSW/SKL 成功分支预测的延迟：
- (d==0)：对 d 或 q 没有数据依赖，破坏了 dep 链。 （控制对 d 的依赖以检测错误预测并退出分支）。
- (d!=0): q->结果: tzcnt+shrx+inc = 5c
- (d!=0): d->结果: sub+shrx+inc = 3c
- 吞吐量：可能只是uop吞吐量的瓶颈
我试过但没能让 gcc 从减法在 CF 上分支，但它总是想做一个单独的比较。我知道 gcc 可以在减去两个变量后被引导到 CF 上的分支，但如果一个是编译时常量，这可能会失败。 （IIRC，这通常会编译为带有无符号变量的 CF 测试：foo -= bar; if(foo>bar) carry_detected = 1;）
使用 ADC / SBB 无分支来处理 d==0 案例。零处理仅向关键路径添加一条指令（相对于没有对 d==0 进行特殊处理的版本），但还将另一条指令从 INC 转换为 sbb rax, -1 以使 CF 撤消 -= -1.在 Broadwell 之前使用 CMOV 更便宜，但需要额外的说明来设置它。
ceil_div_pjc_asm_adc:
tzcnt rsi, rsi
sub rdi, 1
adc rdi, 0 ; d? d-1 : d. Sets CF=CF
shrx rax, rdi, rsi
sbb rax, -1 ; result++ if d was non-zero
ret
- 融合域微指令：SKL 上 5（不计算 ret）。 7 在 HSW
- SKL 延迟：
- q->结果：tzcnt+shrx+sbb = 5c
- d->result: sub+adc+shrx(dep on q begins here)+sbb = 4c
- 吞吐量：P1 上的 TZCNT 运行s。 p06 上仅 SBB、ADC 和 SHRX 运行。所以我认为我们每次迭代 p06 的瓶颈是 3 微指令，使这个 运行 最多 每 1.5c.
一次迭代
如果q和d同时就绪，注意这个版本可以运行 SUB/ADC与TZCNT的3c延迟并行。如果两者都来自相同的缓存未命中缓存行，那当然是可能的。无论如何，在 d->result 依赖链中尽可能晚地引入对 q 的依赖是一个优势。
使用 gcc5.4 从 C 中获取它似乎不太可能。有一个 add-with-carry 的内在函数，但是 gcc 把它搞得一团糟。它不使用 ADC 或 SBB 的立即操作数，而是将进位存储到每个操作之间的整数寄存器中。 gcc7、clang3.9 和 icc17 都由此产生了糟糕的代码。
#include <x86intrin.h>
// compiles to completely horrible code, putting the flags into integer regs between ops.
T ceil_div_adc(T d, T q) {
T e = lg(q);
unsigned long long dm1; // unsigned __int64
unsigned char CF = _addcarry_u64(0, d, -1, &dm1);
CF = _addcarry_u64(CF, 0, dm1, &dm1);
T shifted = dm1 >> e;
_subborrow_u64(CF, shifted, -1, &dm1);
return dm1;
}
# gcc5.4 -O3 -march=haswell
mov rax, -1
tzcnt rsi, rsi
add rdi, rax
setc cl
xor edx, edx
add cl, -1
adc rdi, rdx
setc dl
shrx rdi, rdi, rsi
add dl, -1
sbb rax, rdi
ret
CMOV 修复整个结果：q->result 的延迟更差，因为它在 d->result dep 链中使用得更快。
ceil_div_pjc_asm_cmov:
tzcnt rsi, rsi
sub rdi, 1
shrx rax, rdi, rsi
lea rax, [rax+1] ; inc preserving flags
cmovc rax, zeroed_register
ret
- 融合域微指令：SKL 上 5（不计算 ret）。 HSW 6 人
- SKL 延迟：
- q->结果：tzcnt+shrx+lea+cmov = 6c（比ADC/SBB差1c）
- d->result: sub+shrx(dep on q begins here)+lea+cmov = 4c
- 吞吐量：P1 上的 TZCNT 运行s。 LEA 是 p15。 CMOV 和 SHRX 是 p06。 SUB 是 p0156。理论上仅在融合域 uop 吞吐量上存在瓶颈，因此 每 1.25c 一次迭代。对于大量独立操作，SUB 或 LEA 窃取 p1 或 p06 的资源冲突不应该成为吞吐量问题，因为在每 1.25c 1 iter 时，没有端口饱和只能 运行 在该端口上的 uops。
CMOV 以获取 SUB 的操作数：我希望我能找到一种方法来为后面的指令创建一个操作数，该操作数在需要时会产生一个零，而无需输入对 q、e 或 SHRX 结果的依赖性。如果 d 在 q 之前或同时准备就绪，这将有所帮助。
这并没有实现那个目标，并且在循环中需要一个额外的 7 字节 mov rdx,-1。
ceil_div_pjc_asm_cmov:
tzcnt rsi, rsi
mov rdx, -1
sub rdi, 1
shrx rax, rdi, rsi
cmovnc rdx, rax
sub rax, rdx ; res += d ? 1 : -res
ret
具有昂贵 CMOV 的 BDW 之前的 CPU 的低延迟版本，使用 SETCC 为 AND 创建掩码。
ceil_div_pjc_asm_setcc:
xor edx, edx ; needed every iteration
tzcnt rsi, rsi
sub rdi, 1
setc dl ; d!=0 ? 0 : 1
dec rdx ; d!=0 ? -1 : 0 // AND-mask
shrx rax, rdi, rsi
inc rax
and rax, rdx ; zero the bogus result if d was initially 0
ret
d->result 仍有 4c 延迟（q->result 为 6），因为 SETC/DEC 与 SHRX/INC 并行发生.总 uop 计数：8。这些 insns 中的大多数可以 运行 在任何端口上，因此它应该是每 2 个时钟 1 个迭代器。
当然，对于pre-HSW，还需要更换SHRX。
我们可以让 gcc5.4 发出几乎一样好的东西：（仍然使用单独的测试而不是基于 sub rdi, 1 设置掩码，但其他方面相同说明同上）。看到了on Godbolt.
T ceil_div_andmask(T p, T q) {
T mask = -(T)(p!=0); // TEST+SETCC+NEG
T e = lg(q);
T nonzero_result = ((p-1) >> e) + 1;
return nonzero_result & mask;
}
当编译器知道 p 是非零时，它会利用并生成漂亮的代码：
//
#if defined(__GNUC__) && !defined(__INTEL_COMPILER)
#define assume(x) do{if(!(x)) __builtin_unreachable();}while(0)
#else
#define assume(x) (void)(x) // still evaluate it once, for side effects in case anyone is insane enough to put any inside an assume()
#endif
T ceil_div_andmask_nonzerop(T p, T q) {
assume(p!=0);
return ceil_div_andmask(p, q);
}
# gcc5.4 -O3 -march=haswell
xor eax, eax # gcc7 does tzcnt in-place instead of wasting an insn on this
sub rdi, 1
tzcnt rax, rsi
shrx rax, rdi, rax
add rax, 1
ret
楚克斯/user23_variant
p->result 的延迟只有 3c，常数 q 可以 CSE 很多。
T divide_A_chux(T p, T q) {
bool round_up = p & (q-1); // compiles differently from user23_variant with clang: AND instead of
return (p >> lg(q)) + round_up;
}
xor eax, eax # in-place tzcnt would save this
xor edx, edx # target for setcc
tzcnt rax, rsi
sub rsi, 1
test rsi, rdi
shrx rdi, rdi, rax
setne dl
lea rax, [rdx+rdi]
ret
在 TZCNT 之前执行 SETCC 将允许就地 TZCNT，从而节省 xor eax,eax。我还没有看过它是如何在循环中内联的。
- 融合域 uops：HSW/SKL
上的 8（不包括 ret）
- HSW/SKL 延迟：
- q->结果: (tzcnt+shrx(p) | sub+test(p)+setne) + lea(or add) = 5c
- d->result: test(dep on q begins here)+setne+lea = 3c. （shrx->lea 链较短，因此不是关键路径）
- 吞吐量：可能只是 前端出现瓶颈，每 2c 一个迭代。保存
xor eax,eax 应该会加速到每 1.75c 一个（但是当然任何循环开销都会成为瓶颈的一部分，因为前端瓶颈就是这样）。
如果dividend/divisor可以保证不超过63（或31）位，可以使用问题中提到的以下版本。请注意，如果 p+q 使用所有 64 位，它们将如何溢出。如果 SHR 指令在进位标志中移动，这会很好，但据我所知它没有。
uint64_t divide(uint64_t p, uint64_t q) {
return (p + q - 1) >> lg(q);
}
如果不能保证这些约束条件，你可以直接做floor方法，如果会向上取整就加1。这可以通过检查被除数中的任何位是否在除数范围内来确定。
注：p&-p在2s补码机或the BLSI instruction
上提取最低位
uint64_t divide(uint64_t p, uint64_t q) {
return (p >> lg(q)) + ( (p & -p ) < q );
}
clang 编译为：
bsrq %rax, %rsi
shrxq %rax, %rdi, %rax
blsiq %rdi, %rcx
cmpq %rsi, %rcx
adcq [=12=], %rax
retq
这有点罗嗦，而且使用了一些较新的指令，所以也许有一种方法可以在原始版本中使用进位标志。让我们来看看：
RCR instruction does but seems like it would be worse ... perhaps the SHRD指令……大概是这样的（暂时无法测试）
xor edx, edx ;edx = 0 (will store the carry flag)
bsr rcx, rsi ;rcx = lg(q) ... could be moved anywhere before shrd
lea rax, [rsi-1] ;rax = q-1 (adding p could carry)
add rax, rdi ;rax += p (handle carry)
setc dl ;rdx = carry flag ... or xor rdx and setc
shrd rax, rdx, cl ;rax = rdx:rax >> cl
ret
还有 1 条指令，但应该与旧处理器兼容（如果它能工作......我总是得到 source/destination 交换 - 随意编辑）
附录：
I've implemented the lg() function I said was available as follows:
inline uint64_t lg(uint64_t x) {
return 63U - (uint64_t)__builtin_clzl(x);
}
inline uint32_t lg32(uint32_t x) {
return 31U - (uint32_t)__builtin_clz(x);
}
快速日志功能并未完全针对 clang 和 ICC 上的 bsr 进行优化，但您可以这样做：
#if defined(__x86_64__) && (defined(__clang__) || defined(__INTEL_COMPILER))
static inline uint64_t lg(uint64_t x){
inline uint64_t ret;
//other compilers may want bsrq here
__asm__("bsr %0, %1":"=r"(ret):"r"(x));
return ret;
}
#endif
#if defined(__i386__) && (defined(__clang__) || defined(__INTEL_COMPILER))
static inline uint32_t lg32(uint32_t x){
inline uint32_t ret;
__asm__("bsr %0, %1":"=r"(ret):"r"(x));
return ret;
}
#endif
已经有很多人的脑力应用于这个问题，在 C 中有几个很好的答案变体以及 Peter Cordes 的答案，它涵盖了你在 asm 中所能期望的最好的答案，并附有注释试图将其映射回 C.
所以当人类在玩罐头的时候，我想看看一些强大的计算能力会说些什么！为此，我使用了斯坦福大学的 STOKE 超级优化器来尝试找到解决此问题的 32 位和 64 位版本的好方法。
通常，superoptimizer is usually something like a brute force search through all possible instruction sequences until you find the best one by some metric. Of course, with something like 1,000 instructions that will quickly spiral out of control for more than a few instructions1. STOKE, on the hand, takes a guided randomized approach: it randomly makes mutations to an existing candidate program, evaluating at each step a cost function that takes both performance and correctness into effect. That's the one-liner anyway - there are plenty of papers 如果 激发了 你的好奇心。
所以在几分钟内，STOKE 找到了一些非常有趣的解决方案。它发现了现有解决方案中几乎所有的高级想法，以及一些独特的想法。比如32位的函数，STOKE找到这个版本：
neg rsi
dec rdi
pext rax, rsi, rdi
inc eax
ret
它根本不使用任何 leading/trailing-zero 计数或移位指令。几乎，它使用 neg esi 将除数转换为高位为 1 的掩码，然后 pext 使用该掩码有效地进行移位。除了这个技巧之外，它还使用了用户 QuestionC 使用的相同技巧：递减 p、移位、递增 p - 但它恰好适用于零股息，因为它使用 64 位寄存器来区分零情况和 MSB-set large p案例.
我把这个算法的C version加到benchmark中，加到结果中。它与其他优秀算法具有竞争力，在 "Variable Q" 个案例中并列第一。它确实矢量化，但不如其他 32 位算法，因为它需要 64 位数学运算，因此矢量一次只能处理一半的元素。
更好的是，在 32 位的情况下，它提出了多种解决方案，这些解决方案利用了以下事实：如果您使用 64 位，一些在边缘情况下失败的直观解决方案恰好 "just work"操作其中的一部分。例如：
tzcntl ebp, esi
dec esi
add rdi, rsi
sarx rax, rdi, rbp
ret
这相当于我在问题中提到的 return (p + q - 1) >> lg(q) 建议。这通常不起作用，因为对于大 p + q 它会溢出，但对于 32 位 p 和 q，此解决方案通过在 64 位中执行重要部分而效果很好。使用 some casts 将其转换回 C，它实际上计算出使用 lea 将在一条指令中执行加法 1:
stoke_32(unsigned int, unsigned int):
tzcnt edx, esi
mov edi, edi ; goes away when inlining
mov esi, esi ; goes away when inlining
lea rax, [rsi-1+rdi]
shrx rax, rax, rdx
ret
因此，当内联到已经将值零扩展到 rdi 和 rsi 的内容中时，它是一个 3 指令解决方案。独立函数定义需要 mov 指令进行零扩展，因为那是 .
对于 64 位功能，它没有提出任何颠覆现有解决方案的东西，但它确实提出了一些巧妙的东西，例如：
tzcnt r13, rsi
tzcnt rcx, rdi
shrx rax, rdi, r13
cmp r13b, cl
adc rax, 0
ret
那家伙计算两个参数的尾随零，然后如果q的尾随零比p少，则将结果加1，因为那是你需要四舍五入的时候。聪明！
总的来说，它理解了你需要 shl 非常快地 tzcnt 的想法（就像大多数人一样），然后想出了很多其他的解决方案来解决这个问题调整结果以考虑四舍五入。它甚至设法在多个解决方案中使用 blsi 和 bzhi。这是它提出的 5 指令解决方案：
tzcnt r13, rsi
shrx rax, rdi, r13
imul rsi, rax
cmp rsi, rdi
adc rax, 0
ret
这基本上是一种 "multiply and verify" 方法 - 取截断的 res = p \ q，将其乘回去，如果它与 p 不同，则添加一个：return res * q == p ? ret : ret + 1。凉爽的。虽然并不比彼得的解决方案好。 STOKE 似乎在其延迟计算中存在一些缺陷——它认为上面的延迟为 5——但它更像是 8 或 9，具体取决于体系结构。因此，它有时会缩小基于其有缺陷的延迟计算的解决方案。
1 有趣的是，尽管这种 蛮力 方法在 5-6 条指令左右达到了可行性：如果你假设你可以 trim 通过消除 SIMD 和 x87 指令，指令数为 300，那么您将需要大约 28 天的时间来尝试所有 300 ^ 5 5 个指令序列，达到 1,000,000 candidates/second。您也许可以通过各种优化将其减少 1,000 倍，这意味着 5 条指令序列不到一个小时，而 6 条指令可能需要一周。碰巧的是，这个问题的大多数最佳解决方案都属于 5-6 条指令 window...
2 这将是一个 慢 lea，但是，因此 STOKE 找到的序列仍然是最佳的我针对延迟进行了优化。
我想实现 unsigneda 整数除法 任意二的幂，四舍五入，高效。所以从数学上讲，我想要的是 ceiling(p/q)0。在 C 中，不利用 q 限制域的 strawman 实现可能类似于以下函数 1:
/** q must be a power of 2, although this version works for any q */
uint64_t divide(uint64_t p, uint64_t q) {
uint64_t res = p / q;
return p % q == 0 ? res : res + 1;
}
...当然，我实际上并不想在机器级别使用除法或 mod，因为即使在 mod 现代硬件。我正在寻找使用 shifts and/or 一些其他廉价操作的强度降低 - 利用 q 是 2 的幂这一事实。
你可以假设我们有一个高效的 lg(unsigned int x) 函数，如果 x 是二次幂，它 returns x 的 base-2 对数.
如果 q 为零，未定义的行为是可以的。
请注意，简单的解决方案：(p+q-1) >> lg(q) 通常不起作用 - 例如尝试使用 p == 2^64-100 and q == 2562。
uint64_t exponent = lg(q);
uint64_t mask = q - 1;
// v divide
return (p >> exponent) + (((p & mask) + mask) >> exponent)
// ^ round up
"round up"部分的单独计算避免了(p+q-1) >> lg(q)的溢出问题。根据您的编译器的智能程度，可以将 "round up" 部分表示为 ((p & mask) != 0) 而无需分支。
你可以这样做，比较除以 n / d 和除以 (n-1) / d。
#include <stdio.h>
int main(void) {
unsigned n;
unsigned d;
unsigned q1, q2;
double actual;
for(n = 1; n < 6; n++) {
for(d = 1; d < 6; d++) {
actual = (double)n / d;
q1 = n / d;
if(n) {
q2 = (n - 1) / d;
if(q1 == q2) {
q1++;
}
}
printf("%u / %u = %u (%f)\n", n, d, q1, actual);
}
}
return 0;
}
程序输出：
1 / 1 = 1 (1.000000)
1 / 2 = 1 (0.500000)
1 / 3 = 1 (0.333333)
1 / 4 = 1 (0.250000)
1 / 5 = 1 (0.200000)
2 / 1 = 2 (2.000000)
2 / 2 = 1 (1.000000)
2 / 3 = 1 (0.666667)
2 / 4 = 1 (0.500000)
2 / 5 = 1 (0.400000)
3 / 1 = 3 (3.000000)
3 / 2 = 2 (1.500000)
3 / 3 = 1 (1.000000)
3 / 4 = 1 (0.750000)
3 / 5 = 1 (0.600000)
4 / 1 = 4 (4.000000)
4 / 2 = 2 (2.000000)
4 / 3 = 2 (1.333333)
4 / 4 = 1 (1.000000)
4 / 5 = 1 (0.800000)
5 / 1 = 5 (5.000000)
5 / 2 = 3 (2.500000)
5 / 3 = 2 (1.666667)
5 / 4 = 2 (1.250000)
5 / 5 = 1 (1.000000)
更新
我发布了对原问题的早期答案，这个答案有效，但没有考虑算法的效率，或者除数总是 2 的幂。执行两次除法是不必要的昂贵。
我在 64 位系统上使用 MSVC 32 位编译器，因此我不可能为所需目标提供最佳解决方案。但这是一个 有趣的问题 所以我四处摸索发现最好的解决方案是发现 2**n 除数的位。使用库函数 log2 可以，但速度太慢了。自己轮班要好得多，但我最好的 C 解决方案仍然是
unsigned roundup(unsigned p, unsigned q)
{
return p / q + ((p & (q-1)) != 0);
}
我的内联 32 位汇编器解决方案更快，但当然不能回答问题。我通过假设 eax 作为函数值返回来窃取了一些周期。
unsigned roundup(unsigned p, unsigned q)
{
__asm {
mov eax,p
mov edx,q
bsr ecx,edx ; cl = bit number of q
dec edx ; q-1
and edx,eax ; p & (q-1)
shr eax,cl ; divide p by q, a power of 2
sub edx,1 ; generate a carry when (p & (q-1)) == 0
cmc
adc eax,0 ; add 1 to result when (p & (q-1)) != 0
}
} ; eax returned as function value
如果 p 大于 2 的幂（哎呀），我的旧答案就不起作用了。所以我的新解决方案，使用 __builtin_ctzll() 和 __builtin_ffsll() 函数 0 在 gcc 中可用（作为奖励，提供你提到的快速对数！ ):
uint64_t divide(uint64_t p,uint64_t q) {
int lp=__builtin_ffsll(p);
int lq=__builtin_ctzll(q);
return (p>>lq)+(lp<(lq+1)&&lp);
}
请注意，这是假设 long long 是 64 位。否则必须稍微调整一下。
这里的想法是，当且仅当 p 的尾随零比 q 少时我们才需要溢出。请注意，对于 2 的幂，尾随零的数量等于对数，因此我们也可以将此内置函数用于对数。
&&lp 部分仅针对 p 为零的极端情况：否则它将在此处输出 1。
0 不能对两者都使用 __builtin_ctzll() 因为如果 p==0.
如果您的编译器使用算术右移（通常为真），这似乎很有效并且适用于带符号的情况。
#include <stdio.h>
int main (void)
{
for (int i = -20; i <= 20; ++i) {
printf ("%5d %5d\n", i, ((i - 1) >> 1) + 1);
}
return 0;
}
用>> 2除以4，>> 3除以8，等等。高效 lg 完成那里的工作。
你甚至可以除以1！ >> 0
C 中无符号整数除以 2 的幂的有效方法是右移 -- 右移一位除以二（向下舍入），因此右移 n 除以 2n（向下舍入）。
现在你想向上舍入而不是向下舍入，你可以先加上 2n-1，或者等价地减去班前加一，班后加一（0除外）。结果类似于：
unsigned ceil_div(unsigned d, unsigned e) {
/* compute ceil(d/2**e) */
return d ? ((d-1) >> e) + 1 : 0;
}
条件可以去掉，用d的布尔值加减一：
unsigned ceil_div(unsigned d, unsigned e) {
/* compute ceil(d/2**e) */
return ((d - !!d) >> e) + !!d;
}
由于其大小和速度要求，该函数应设为静态内联。它可能不会对优化器产生影响，但参数应该是常量。如果必须在多个文件之间共享，请将其定义为 header:
static inline unsigned ceil_div(const unsigned d, const unsigned e){...
Efficiently dividing unsigned value by a power of two, rounding up
[重写] 给定 OP
当溢出不是问题时，圆角或天花板部分很容易。简单添加 q-1，然后移位。
否则，由于舍入的可能性取决于p小于q的所有位，因此在移出这些位之前需要先检测这些位。
uint64_t divide_A(uint64_t p, uint64_t q) {
bool round_up = p & (q-1);
return (p >> lg64(q)) + round_up;
}
这假设代码具有高效的 lg64(uint64_t x) 函数，如果 x 是二次幂，则 returns x 的 base-2 对数。 `
这个答案是关于什么是 asm 的理想；我们想说服编译器为我们发出什么。 （我不建议实际使用内联汇编，除非在对编译器输出进行基准测试时作为比较点。https://gcc.gnu.org/wiki/DontUseInlineAsm）。
我确实设法从 ceil_div_andmask 的纯 C 中获得了相当不错的 asm 输出，见下文。（它比 Broadwell/Skylake 上的 CMOV 更糟糕，但在 Haswell 上可能不错。不过，user23/chux 版本在这两种情况下看起来都更好。）它主要是值得一提的，因为它是我让编译器发出我想要的 asm 的少数情况之一。
Chris Dodd 关于 return ((p-1) >> lg(q)) + 1 的一般想法以及 d=0 的特殊情况处理似乎是最好的选择之一。 IE。它在 asm 中的最佳实现很难与其他任何东西的最佳实现相提并论。 Chux 的 (p >> lg(q)) + (bool)(p & (q-1)) 也有优势（比如 p->result 的延迟较低），并且当相同的 q 用于多个分区时更多 CSE。请参阅下面的 latency/throughput 分析 gcc 用它做什么。
如果相同的e = lg(q)被重复用于多个被除数，或者同一个被除数被重复用于多个除数，不同的实现可以CSE更多的表达式。 他们还可以使用 AVX2 进行有效矢量化。
Branches are cheap and very efficient if they predict very well，所以在 d==0 上分支是最好的，如果它几乎从未被采用。如果 d==0 不罕见，branchless asm 平均表现会更好。理想情况下，我们可以用 C 编写一些东西，让 gcc 在配置文件引导的优化过程中做出正确的选择，并在任何情况下编译成良好的 asm。
由于最好的无分支 asm 实现与分支实现相比不会增加太多延迟，因此无分支可能是可行的方法，除非分支可能在 99% 的时间内以相同的方式运行。这可能适用于 p==0 上的分支，但不太可能适用于 p & (q-1).
很难引导 gcc5.4 发出任何最佳的东西。 This is my work-in-progress on Godbolt).
我认为Skylake对于这个算法的最优序列如下。 （显示为 AMD64 SysV ABI 的独立函数，但谈论 throughput/latency 假设编译器将发出类似内联到循环中的内容，没有附加 RET）。
分支从计算 d-1 到检测 d==0，而不是单独的测试 & 分支。很好地减少了 uop 计数，尤其是在 JC 可以与 SUB 宏融合的 SnB 系列上。
ceil_div_pjc_branch:
xor eax,eax ; can take this uop off the fast path by adding a separate xor-and-return block, but in reality we want to inline something like this.
sub rdi, 1
jc .d_was_zero ; fuses with the sub on SnB-family
tzcnt rax, rsi ; tzcnt rsi,rsi also avoids any false-dep problems, but this illustrates that the q input can be read-only.
shrx rax, rdi, rax
inc rax
.d_was_zero:
ret
- 融合域微指令：5（不包括 ret），其中之一是异或零（无执行单元）
- HSW/SKL 成功分支预测的延迟：
- (d==0)：对 d 或 q 没有数据依赖，破坏了 dep 链。 （控制对 d 的依赖以检测错误预测并退出分支）。
- (d!=0): q->结果: tzcnt+shrx+inc = 5c
- (d!=0): d->结果: sub+shrx+inc = 3c
- 吞吐量：可能只是uop吞吐量的瓶颈
我试过但没能让 gcc 从减法在 CF 上分支，但它总是想做一个单独的比较。我知道 gcc 可以在减去两个变量后被引导到 CF 上的分支，但如果一个是编译时常量，这可能会失败。 （IIRC，这通常会编译为带有无符号变量的 CF 测试：foo -= bar; if(foo>bar) carry_detected = 1;）
使用 ADC / SBB 无分支来处理 d==0 案例。零处理仅向关键路径添加一条指令（相对于没有对 d==0 进行特殊处理的版本），但还将另一条指令从 INC 转换为 sbb rax, -1 以使 CF 撤消 -= -1.在 Broadwell 之前使用 CMOV 更便宜，但需要额外的说明来设置它。
ceil_div_pjc_asm_adc:
tzcnt rsi, rsi
sub rdi, 1
adc rdi, 0 ; d? d-1 : d. Sets CF=CF
shrx rax, rdi, rsi
sbb rax, -1 ; result++ if d was non-zero
ret
- 融合域微指令：SKL 上 5（不计算 ret）。 7 在 HSW
- SKL 延迟：
- q->结果：tzcnt+shrx+sbb = 5c
- d->result: sub+adc+shrx(dep on q begins here)+sbb = 4c
- 吞吐量：P1 上的 TZCNT 运行s。 p06 上仅 SBB、ADC 和 SHRX 运行。所以我认为我们每次迭代 p06 的瓶颈是 3 微指令，使这个 运行 最多 每 1.5c. 一次迭代
如果q和d同时就绪，注意这个版本可以运行 SUB/ADC与TZCNT的3c延迟并行。如果两者都来自相同的缓存未命中缓存行，那当然是可能的。无论如何，在 d->result 依赖链中尽可能晚地引入对 q 的依赖是一个优势。
使用 gcc5.4 从 C 中获取它似乎不太可能。有一个 add-with-carry 的内在函数，但是 gcc 把它搞得一团糟。它不使用 ADC 或 SBB 的立即操作数，而是将进位存储到每个操作之间的整数寄存器中。 gcc7、clang3.9 和 icc17 都由此产生了糟糕的代码。
#include <x86intrin.h>
// compiles to completely horrible code, putting the flags into integer regs between ops.
T ceil_div_adc(T d, T q) {
T e = lg(q);
unsigned long long dm1; // unsigned __int64
unsigned char CF = _addcarry_u64(0, d, -1, &dm1);
CF = _addcarry_u64(CF, 0, dm1, &dm1);
T shifted = dm1 >> e;
_subborrow_u64(CF, shifted, -1, &dm1);
return dm1;
}
# gcc5.4 -O3 -march=haswell
mov rax, -1
tzcnt rsi, rsi
add rdi, rax
setc cl
xor edx, edx
add cl, -1
adc rdi, rdx
setc dl
shrx rdi, rdi, rsi
add dl, -1
sbb rax, rdi
ret
CMOV 修复整个结果：q->result 的延迟更差，因为它在 d->result dep 链中使用得更快。
ceil_div_pjc_asm_cmov:
tzcnt rsi, rsi
sub rdi, 1
shrx rax, rdi, rsi
lea rax, [rax+1] ; inc preserving flags
cmovc rax, zeroed_register
ret
- 融合域微指令：SKL 上 5（不计算 ret）。 HSW 6 人
- SKL 延迟：
- q->结果：tzcnt+shrx+lea+cmov = 6c（比ADC/SBB差1c）
- d->result: sub+shrx(dep on q begins here)+lea+cmov = 4c
- 吞吐量：P1 上的 TZCNT 运行s。 LEA 是 p15。 CMOV 和 SHRX 是 p06。 SUB 是 p0156。理论上仅在融合域 uop 吞吐量上存在瓶颈，因此 每 1.25c 一次迭代。对于大量独立操作，SUB 或 LEA 窃取 p1 或 p06 的资源冲突不应该成为吞吐量问题，因为在每 1.25c 1 iter 时，没有端口饱和只能 运行 在该端口上的 uops。
CMOV 以获取 SUB 的操作数：我希望我能找到一种方法来为后面的指令创建一个操作数，该操作数在需要时会产生一个零，而无需输入对 q、e 或 SHRX 结果的依赖性。如果 d 在 q 之前或同时准备就绪，这将有所帮助。
这并没有实现那个目标，并且在循环中需要一个额外的 7 字节 mov rdx,-1。
ceil_div_pjc_asm_cmov:
tzcnt rsi, rsi
mov rdx, -1
sub rdi, 1
shrx rax, rdi, rsi
cmovnc rdx, rax
sub rax, rdx ; res += d ? 1 : -res
ret
具有昂贵 CMOV 的 BDW 之前的 CPU 的低延迟版本，使用 SETCC 为 AND 创建掩码。
ceil_div_pjc_asm_setcc:
xor edx, edx ; needed every iteration
tzcnt rsi, rsi
sub rdi, 1
setc dl ; d!=0 ? 0 : 1
dec rdx ; d!=0 ? -1 : 0 // AND-mask
shrx rax, rdi, rsi
inc rax
and rax, rdx ; zero the bogus result if d was initially 0
ret
d->result 仍有 4c 延迟（q->result 为 6），因为 SETC/DEC 与 SHRX/INC 并行发生.总 uop 计数：8。这些 insns 中的大多数可以 运行 在任何端口上，因此它应该是每 2 个时钟 1 个迭代器。
当然，对于pre-HSW，还需要更换SHRX。
我们可以让 gcc5.4 发出几乎一样好的东西：（仍然使用单独的测试而不是基于 sub rdi, 1 设置掩码，但其他方面相同说明同上）。看到了on Godbolt.
T ceil_div_andmask(T p, T q) {
T mask = -(T)(p!=0); // TEST+SETCC+NEG
T e = lg(q);
T nonzero_result = ((p-1) >> e) + 1;
return nonzero_result & mask;
}
当编译器知道 p 是非零时，它会利用并生成漂亮的代码：
//
#if defined(__GNUC__) && !defined(__INTEL_COMPILER)
#define assume(x) do{if(!(x)) __builtin_unreachable();}while(0)
#else
#define assume(x) (void)(x) // still evaluate it once, for side effects in case anyone is insane enough to put any inside an assume()
#endif
T ceil_div_andmask_nonzerop(T p, T q) {
assume(p!=0);
return ceil_div_andmask(p, q);
}
# gcc5.4 -O3 -march=haswell
xor eax, eax # gcc7 does tzcnt in-place instead of wasting an insn on this
sub rdi, 1
tzcnt rax, rsi
shrx rax, rdi, rax
add rax, 1
ret
楚克斯/user23_variant
p->result 的延迟只有 3c，常数 q 可以 CSE 很多。
T divide_A_chux(T p, T q) {
bool round_up = p & (q-1); // compiles differently from user23_variant with clang: AND instead of
return (p >> lg(q)) + round_up;
}
xor eax, eax # in-place tzcnt would save this
xor edx, edx # target for setcc
tzcnt rax, rsi
sub rsi, 1
test rsi, rdi
shrx rdi, rdi, rax
setne dl
lea rax, [rdx+rdi]
ret
在 TZCNT 之前执行 SETCC 将允许就地 TZCNT，从而节省 xor eax,eax。我还没有看过它是如何在循环中内联的。
- 融合域 uops：HSW/SKL 上的 8（不包括 ret）
- HSW/SKL 延迟：
- q->结果: (tzcnt+shrx(p) | sub+test(p)+setne) + lea(or add) = 5c
- d->result: test(dep on q begins here)+setne+lea = 3c. （shrx->lea 链较短，因此不是关键路径）
- 吞吐量：可能只是 前端出现瓶颈，每 2c 一个迭代。保存
xor eax,eax应该会加速到每 1.75c 一个（但是当然任何循环开销都会成为瓶颈的一部分，因为前端瓶颈就是这样）。
如果dividend/divisor可以保证不超过63（或31）位，可以使用问题中提到的以下版本。请注意，如果 p+q 使用所有 64 位，它们将如何溢出。如果 SHR 指令在进位标志中移动，这会很好，但据我所知它没有。
uint64_t divide(uint64_t p, uint64_t q) {
return (p + q - 1) >> lg(q);
}
如果不能保证这些约束条件，你可以直接做floor方法，如果会向上取整就加1。这可以通过检查被除数中的任何位是否在除数范围内来确定。 注：p&-p在2s补码机或the BLSI instruction
上提取最低位uint64_t divide(uint64_t p, uint64_t q) {
return (p >> lg(q)) + ( (p & -p ) < q );
}
clang 编译为：
bsrq %rax, %rsi
shrxq %rax, %rdi, %rax
blsiq %rdi, %rcx
cmpq %rsi, %rcx
adcq [=12=], %rax
retq
这有点罗嗦，而且使用了一些较新的指令，所以也许有一种方法可以在原始版本中使用进位标志。让我们来看看： RCR instruction does but seems like it would be worse ... perhaps the SHRD指令……大概是这样的（暂时无法测试）
xor edx, edx ;edx = 0 (will store the carry flag)
bsr rcx, rsi ;rcx = lg(q) ... could be moved anywhere before shrd
lea rax, [rsi-1] ;rax = q-1 (adding p could carry)
add rax, rdi ;rax += p (handle carry)
setc dl ;rdx = carry flag ... or xor rdx and setc
shrd rax, rdx, cl ;rax = rdx:rax >> cl
ret
还有 1 条指令，但应该与旧处理器兼容（如果它能工作......我总是得到 source/destination 交换 - 随意编辑）
附录：
I've implemented the lg() function I said was available as follows:
inline uint64_t lg(uint64_t x) { return 63U - (uint64_t)__builtin_clzl(x); } inline uint32_t lg32(uint32_t x) { return 31U - (uint32_t)__builtin_clz(x); }
快速日志功能并未完全针对 clang 和 ICC 上的 bsr 进行优化，但您可以这样做：
#if defined(__x86_64__) && (defined(__clang__) || defined(__INTEL_COMPILER))
static inline uint64_t lg(uint64_t x){
inline uint64_t ret;
//other compilers may want bsrq here
__asm__("bsr %0, %1":"=r"(ret):"r"(x));
return ret;
}
#endif
#if defined(__i386__) && (defined(__clang__) || defined(__INTEL_COMPILER))
static inline uint32_t lg32(uint32_t x){
inline uint32_t ret;
__asm__("bsr %0, %1":"=r"(ret):"r"(x));
return ret;
}
#endif
已经有很多人的脑力应用于这个问题，在 C 中有几个很好的答案变体以及 Peter Cordes 的答案，它涵盖了你在 asm 中所能期望的最好的答案，并附有注释试图将其映射回 C.
所以当人类在玩罐头的时候，我想看看一些强大的计算能力会说些什么！为此，我使用了斯坦福大学的 STOKE 超级优化器来尝试找到解决此问题的 32 位和 64 位版本的好方法。
通常，superoptimizer is usually something like a brute force search through all possible instruction sequences until you find the best one by some metric. Of course, with something like 1,000 instructions that will quickly spiral out of control for more than a few instructions1. STOKE, on the hand, takes a guided randomized approach: it randomly makes mutations to an existing candidate program, evaluating at each step a cost function that takes both performance and correctness into effect. That's the one-liner anyway - there are plenty of papers 如果 激发了 你的好奇心。
所以在几分钟内，STOKE 找到了一些非常有趣的解决方案。它发现了现有解决方案中几乎所有的高级想法，以及一些独特的想法。比如32位的函数，STOKE找到这个版本：
neg rsi
dec rdi
pext rax, rsi, rdi
inc eax
ret
它根本不使用任何 leading/trailing-zero 计数或移位指令。几乎，它使用 neg esi 将除数转换为高位为 1 的掩码，然后 pext 使用该掩码有效地进行移位。除了这个技巧之外，它还使用了用户 QuestionC 使用的相同技巧：递减 p、移位、递增 p - 但它恰好适用于零股息，因为它使用 64 位寄存器来区分零情况和 MSB-set large p案例.
我把这个算法的C version加到benchmark中，加到结果中。它与其他优秀算法具有竞争力，在 "Variable Q" 个案例中并列第一。它确实矢量化，但不如其他 32 位算法，因为它需要 64 位数学运算，因此矢量一次只能处理一半的元素。
更好的是，在 32 位的情况下，它提出了多种解决方案，这些解决方案利用了以下事实：如果您使用 64 位，一些在边缘情况下失败的直观解决方案恰好 "just work"操作其中的一部分。例如：
tzcntl ebp, esi
dec esi
add rdi, rsi
sarx rax, rdi, rbp
ret
这相当于我在问题中提到的 return (p + q - 1) >> lg(q) 建议。这通常不起作用，因为对于大 p + q 它会溢出，但对于 32 位 p 和 q，此解决方案通过在 64 位中执行重要部分而效果很好。使用 some casts 将其转换回 C，它实际上计算出使用 lea 将在一条指令中执行加法 1:
stoke_32(unsigned int, unsigned int):
tzcnt edx, esi
mov edi, edi ; goes away when inlining
mov esi, esi ; goes away when inlining
lea rax, [rsi-1+rdi]
shrx rax, rax, rdx
ret
因此，当内联到已经将值零扩展到 rdi 和 rsi 的内容中时，它是一个 3 指令解决方案。独立函数定义需要 mov 指令进行零扩展，因为那是
对于 64 位功能，它没有提出任何颠覆现有解决方案的东西，但它确实提出了一些巧妙的东西，例如：
tzcnt r13, rsi
tzcnt rcx, rdi
shrx rax, rdi, r13
cmp r13b, cl
adc rax, 0
ret
那家伙计算两个参数的尾随零，然后如果q的尾随零比p少，则将结果加1，因为那是你需要四舍五入的时候。聪明！
总的来说，它理解了你需要 shl 非常快地 tzcnt 的想法（就像大多数人一样），然后想出了很多其他的解决方案来解决这个问题调整结果以考虑四舍五入。它甚至设法在多个解决方案中使用 blsi 和 bzhi。这是它提出的 5 指令解决方案：
tzcnt r13, rsi
shrx rax, rdi, r13
imul rsi, rax
cmp rsi, rdi
adc rax, 0
ret
这基本上是一种 "multiply and verify" 方法 - 取截断的 res = p \ q，将其乘回去，如果它与 p 不同，则添加一个：return res * q == p ? ret : ret + 1。凉爽的。虽然并不比彼得的解决方案好。 STOKE 似乎在其延迟计算中存在一些缺陷——它认为上面的延迟为 5——但它更像是 8 或 9，具体取决于体系结构。因此，它有时会缩小基于其有缺陷的延迟计算的解决方案。
1 有趣的是，尽管这种 蛮力 方法在 5-6 条指令左右达到了可行性：如果你假设你可以 trim 通过消除 SIMD 和 x87 指令，指令数为 300，那么您将需要大约 28 天的时间来尝试所有 300 ^ 5 5 个指令序列，达到 1,000,000 candidates/second。您也许可以通过各种优化将其减少 1,000 倍，这意味着 5 条指令序列不到一个小时，而 6 条指令可能需要一周。碰巧的是，这个问题的大多数最佳解决方案都属于 5-6 条指令 window...
2 这将是一个 慢 lea，但是，因此 STOKE 找到的序列仍然是最佳的我针对延迟进行了优化。