使用汇编除以 2 的可变幂

Question

我有这个任务：

除功率2

计算 x/2ⁿ，0 ≤ n ≤ 30。向零舍入。

• 论点1：

  x

• 论据2：

  n

示例：

• dividePower2(15,1) = 7

• dividePower2(-33,4) = -2

这是我到目前为止所得到的，但我不知道我是否朝着正确的方向前进（需要 AT&T 语法）：

.global dividePower2
   dividePower2:
   sar $2, %esi
   ret

Answer 1

是的，如果你想高效地做到这一点，算术右移是一个有用的部分。但不，

n >>= 2;

不是一件有用的事情。您所做的任何转变都需要是可变计数的。

看看编译器如何处理常量

n

，例如

return 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 where x is an integer 之间的差异详细介绍了如何编译器为

x/2

或

x/8

或其他实现 C 除法语义。

添加

2047

可以将小负数包装成小正数，但只有小于 1<<11. So the later

sar

的数字才会将所有设置位移出并留下

0

，就像我们想要将原始小数截断为零的除法一样幅度小于 2048 的负数。

对于较大数值的负数，添加一个正数会减小数值，从而减小商，除非它一开始就是精确倍数。 （因为我们加了比除数少 1 的值）。这让我们可以使用

sar

（算术右移），它向 -Infinity 舍入，考虑到它与我们想要的截断除法之间的小 1 差异。

---

对于变量计数

return x / (1<<n)

，编译器天真地只是具体化

1<<n

并使用

idiv

。但我们可以通过遵循与除以 2 的常数幂相同的模式来做得更好。

我们可以做

x + (1<<n)-1

并使用相同的测试/cmovns让我们得到

x

或

x + (1<<n)-1

。

-1

部分可以作为 LEA 的一部分来完成。

在 Intel CPU 上获取

1<<n

的最有效方法是将

bts

放入归零寄存器中。 （变量计数

shl

是 3 uops，除非我们使用 BMI2

sarx

。并且用 xor 实现

0

比

mov $1, %eax

便宜。）在 AMD Zen 上，

bts

是 2 uops，但

shl %cl, %eax

是只有 1 (https://uops.info)，将

1

移入 EAX 和

shl

可能会更便宜，因为我们无论如何都需要 CL 中的移位计数以用于后面的

sar

。 （除非我们有 BMI2

sarx

，它允许班次计数来自任何寄存器。）

另一种选择是通过将

BMI2 

(1<<n) - 1

应用到

bzhi来获得

0xffffffff

；我认为这直接适用于

n

范围内的

[0,32]

（含）。它在 Intel 和 AMD 上是单 uop (https://uops.info/)

# 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 个组件 (

[-1 + rax + rdi]

) 的 

LEA 在 Skylake 及更早版本上将具有 3 个周期延迟，但 Ice Lake 会以 1 个周期延迟运行。 Ice Lake 及更高版本上的“慢速”LEA 无法在尽可能多的端口上运行，但不会产生延迟损失。 （在 Alder Lake P 核上，scaled 索引会像 Zen 系列一样花费 2 个周期延迟，即使它只是 2 组件 LEA，但我们在这里不会扩展索引。）在 Zen 系列上，这个 3 组件LEA 有 2 个周期延迟。 Alder Lake E 核心也是如此。因此，使用单独的

add

和

dec

指令来执行此操作不会节省任何内容。

获得

(1<<n) - 1

的另一种方法是老 clang 所做的：

0xffffffff >> (-n&31)

。它实际上从

0xffffffff

生成

0

或

sar $31, reg

来广播符号位。但这种策略对于变量

n

来说不太方便，因为它需要否定。在没有 BMI2 的 x86 上尤其不方便，因为班次计数需要在 CL 中。

---

使用 SSE2

pslld

和

psrad

的 SIMD 版本应该是可能的，或者具有每个元素变量计数的 AVX2

vpsllvd

。

与 SSE4.1

pblendvps

混合可以作为标量

cmov

的替代品，但似乎更高效的东西应该是可能的。也许使用

psrad

来获取

0

或

-1

并用它做一些事情会更麻烦？或者只是将其用作

pandn

的掩码，将

1<<n - 1

为非负的元素中的

x

向量归零。

psrad

结果可直接用作

-1

中的

(1<<n) - 1

。

Answer 2

你需要在计算中使用IEEE浮点数标准。它会占用更多内存，但我没有看到任何其他方法。

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

s|exp 位|分数位

令 n1=x = s_x|exp 位_x|分数位_x

且 n2=2^n 0|b(n+127)|0

n1/n2 将简单地等于 s_x|exp 位_x-b(n+127)|分数 位_x

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

Answer 3

我只熟悉 x86 处理器系列的汇编，所以我不知道代码是什么样的。但是潜水 2 本质上是右移。所以对于

pow(2,n)

次，你需要循环它

n

次。

注意：确保您使用的是 2 的补码