使用组件除以 2 的可变幂

您需要使用IEEE浮点数标准 Computing.It 这将占用更多内存，但我没有看到任何其他方法。

请记住，任何浮点数都可以写成：

s|exp 位|小数位

设 n1=x = s_x|exp bits_x|分数 bits_x

和 n2=2^n 0|b（n+127）|0

n1/n2 将简单地等于 s_x|exp bits_x-b（n+127）|分数 bits_x

您将需要 2 个 32 位寄存器来存储除数和除数，以及 1 个 32 位寄存器来存储结果。

是的，如果你要有效地做到这一点，算术右移是其中有用的部分。
但是不，这不是一件有用的事情。您所做的任何移位都需要是可变计数（或者如果您要广播符号位以制作 0 / -1 掩码，则为 31）。n >>= 2;

例如，看看编译器如何处理常量。（戈德博尔特）。nreturn x / (1<<11);

# x86-64 GCC -O3
bar(int):
        testl   %edi, %edi        # set FLAGS according to x
        leal    2047(%rdi), %eax
        cmovns  %edi, %eax        # x < 0  ?  x+(1<<11)-1  :  x
        sarl    $11, %eax         # arithmetic right shift that value
        ret                       # return value in EAX

一个简单的 x >> n （sar %cl， %edi） 向 -Infinity 四舍五入，而不是向 0 截断。 x/2 和 x>>1 或 x*2 和 x << 1 的差异（其中 x 是整数）详细介绍了编译器如何实现 C 除法语义。x/2x/8

加法可以将小负数包装成小正数，但只能将小于 1<<11 的数字包装起来。因此，后者将把所有设定的位移出并离开，就像我们想要对大小小于 2048 的原始小负数进行截断为零的除法一样。2047sar0

对于较大的负数，添加一个正数会减小量级，从而降低商，除非它一开始就是一个精确的倍数。（因为我们比除数少 1）。这让我们可以使用（算术右移）向 -Infinity 四舍五入，考虑它与我们想要的截断除法之间的差值 1。sar

对于变量计数，编译器天真地只是将 和 使用 。但是，我们可以通过遵循与符号除以 2 的常数幂相同的模式来做得更好。return x / (1<<n)1<<nidiv

（n in 的范围限制意味着溢出到不是问题。不过，我认为这个算法可以正常工作。结果是 或 ，这是 32 位 x 31 可能的两个结果。将 = 0x80000000 以外的任何负数相加将产生一个非负数，因此产生 0。对于 x = INT_MIN，我们正在做 给予 。[0,30]1<<31INT_MINn=310-1sar0x7fffffffINT_MINsar-1 >> 31-1

我们可以做并使用相同的测试/cmovns 得到我们或.该部分可以作为 LEA 的一部分完成。x + (1<<n)-1xx + (1<<n)-1-1

使用英特尔 CPU 的最有效方法是进入归零寄存器。（变量计数为 3 uops，除非我们使用 BMI2 。并且使用 xor 实现 a 比 。在 AMD Zen 上，其中有 2 个 uops，但只有 1 （https://uops.info），将 a 移动到 EAX 中可能会更便宜，因为无论如何我们都需要 CL 中的移位计数以供以后使用。（除非我们有 BMI2，它允许来自任何寄存器的班次计数。1<<nbtsshlsarx0mov $1, %eaxbtsshl %cl, %eax1shlsarsarx

另一种选择是通过将 BMI2 bzhi 应用于 ;我认为这直接适用于包含的范围（尽管仍然仅适用于 n=[0,31]）。它是英特尔和AMD（https://uops.info/）上的单uop。见下文;这就是 clang 为 C 版本所做的。(1<<n) - 10xffffffffn[0,32]sar

# untested
.global dividePower2         # int x in EDI,  int n in ESI
                             # returns int in EAX
dividePower2:
   xor   %eax, %eax
   bts   %esi, %eax             # 2^n = 1<<n
   lea   -1(%rax, %rdi), %eax   # x + 2^n - 1

   test  %edi, %edi
   cmovns %edi, %eax     # x for non-negative,  x + 2^n - 1 for negative

   mov   %esi, %ecx      # or  sarx %esi, %eax, %eax
   sar   %cl, %eax       # >>= n  on the adjusted value is equivalent to /= (1>>n)
   ret

具有 3 个组件 （） 的 LEA 在 Skylake 及更早版本上将有 3 个周期的延迟，但 Ice Lake 以 1 个周期的延迟运行它。Ice Lake 上的“慢速”LEA 以后不能在尽可能多的端口上运行，但不会有延迟惩罚。（在 Alder Lake P 核上，缩放索引会像 Zen 系列一样消耗 2 个周期的延迟，即使它只是 2 个组件的 LEA，但我们在这里不缩放索引。在 Zen 系列中，此 3 分量 LEA 具有 2 个周期的延迟。在Alder Lake E-cores上也是如此。因此，使用单独的说明来保存任何东西。[-1 + rax + rdi]adddec

另一种获得方法是老 clang 所做的：.它实际上生成或从广播符号位。但是这种策略对于变量不太方便，因为它需要否定。在没有 BMI2 的 x86 上尤其不方便，因为班次计数需要以 CL 为单位。(1<<n) - 10xffffffff >> (-n&31)0xffffffff0sar $31, regn

应该可以使用带有 SSE2 的 SIMD 版本，或者具有每个元素变量计数的 AVX2。pslldpsradvpsllvd

与 SSE4.1 混合可以替代标量，但似乎应该可以进行更有效的操作。也许更笨拙地用来获取或做某事？或者只是将其用作掩码，将非负元素中的向量归零。结果直接用作 .pblendvpscmovpsrad0-1pandn1<<n - 1xpsrad-1(1<<n) - 1

在 C 或 C++ 中

// well-defined behaviour for n=0..30
int divp2_bitshift(int x, int n){
    int bias = x < 0 ? (1U<<n)-1 : 0U;
    return (x+bias) >> n;
// To handle n=31, use  unsigned bias  and cast x+bias  back to signed int to avoid signed-overflow UB
// That might depend on int being 2's complement, so C++20 or C23
}

int divp2_reference(int x, int n){
    return x / (1LL<<n);  // 64-bit shift and division avoids overflow to INT_MIN
}

Clang 以一种巧妙的方式编译为优化版本，它使用：-march=skylakebzhi

# clang -O3 -march=skylake (BM1 and BMI2)
bitshift(int, int):
        movl    %edi, %eax
        sarl    $31, %eax            # 00000000 or FFFFFFFF
        bzhil   %esi, %eax, %eax     # 0 or (1<<n)-1 

        addl    %edi, %eax
        sarxl   %esi, %eax, %eax
        retq

Godbolt，包括一个，用于针对每个位模式和每个 from to 对参考版本与优化版本进行详尽测试。它适用于所有情况。mainint32_tn031

当参考实现是 时，它通过所有 ，但失败（因为在参考实现中溢出到 INT_MIN，但位移版本给出，因为它除以 2 的正幂。我编译了使有符号整数溢出定义良好，以便于测试 asm。return x / (1<<n)n=0..30-2147483648 / (1<<31) = 11<<31-1gcc -O3 -fwrapv -march=native

因此，此优化不适用于 ，因为该行为被明确定义为具有负除数。x/(1<<n)gcc -fwrapvn=31

但是，如果没有 where signed overflow 是 C 中的未定义行为，这种优化将是有效的。TODO：将此错过的优化报告给 GCC 和 clang。-fwrapv

对 n=0..31 也有效，但对 n=32 或更高无效，因为这在 C 中仍然定义得很好。 有效，并使商为 0。x/(1LL<<n)intlong longn=32..63