现代x86处理器下One's complement绝对值运算的最优位操作方案

背景 #

• 二的补码（two's complement）数绝对值的高效实现已经是非常成熟的通用优化，落地极为广泛。
• 本次聚焦的核心技术问题：如何通过x86汇编实现一的补码数的绝对值计算？
• 该操作的典型应用场景是格雷码（grey decoding）的性能优化：常规64位整数格雷码解码需要执行6次异或+6次位移操作，而如果先将目标数与低位连续为1、末位为0的掩码做无进位乘法（carryless multiplication, CLMUL），输出结果要么是正确的格雷码解码值，要么是该值的按位取反结果，此时只要对输出做一的补码绝对值计算就能得到正确解码值，只要对该步骤做微优化，整体执行效率就会高于当前通用实现。
• 前置状态约定：初始状态符合任意标准C调用约定，或已经完成CLMUL操作、拿到无进位乘法的输出结果。

现有实现思路的性能瓶颈 #

目前已有的简易无分支实现逻辑为：

1. 原数与最高位为1、其余位为0的符号掩码做AND运算，移位提取符号位
2. 提取出的符号位与全1掩码相乘，得到全0（符号位为0，正数）或全1（符号位为1，负数）的掩码
3. 乘积掩码与原数做XOR运算得到结果

这个思路逻辑正确，但性能并非最优，核心瓶颈在于整数乘法指令的延迟：哪怕在最新的x86微架构上，64位整数乘法也有3个周期以上的延迟，且占用独立的乘法执行单元，吞吐量远低于普通ALU指令。

最优无分支实现 #

一的补码绝对值规则非常简单：符号位为0（正数）时结果为原数，符号位为1（负数）时结果为原数按位取反，不需要像二的补码绝对值那样在取反后额外加1。利用算术右移自动复制符号位的特性可以直接生成符号掩码，完全不需要乘法操作，仅需2条核心指令即可完成，是理论上延迟最低的实现。

通用寄存器版本（64位x86-64，兼容主流C调用约定） #

; 输入：待计算的一的补码数存放在rax
mov rdx, rax
sar rdx, 63    ; 算术右移63位：正数得到0x0000000000000000，负数得到0xFFFFFFFFFFFFFFFF
xor rax, rdx   ; 与掩码异或：正数异或0保持原值，负数异或全1等价于按位取反
; 输出：绝对值结果存放在rax

该实现所有指令均为单周期延迟的普通ALU指令，总延迟仅2个周期，可与其他指令乱序配对执行，不占用乘法执行端口，性能远高于带乘法的实现。如果需要处理32位数据，只需将移位位数改为31、替换对应32位寄存器即可，核心逻辑完全一致。

CLMUL场景适配版本（直接处理XMM寄存器中的CLMUL输出） #

如果是CLMUL执行完成后的场景，无进位乘法结果默认存放在XMM寄存器中，不需要将数据搬移到通用寄存器，直接用SIMD指令处理即可，额外省掉跨寄存器域搬移的延迟：

; 输入：CLMUL输出结果存放在xmm0
psraq xmm1, xmm0, 63  ; 对64位lane做算术右移63位，生成全0/全1掩码
pxor xmm0, xmm0, xmm1 ; 异或得到结果
; 输出：解码结果存放在xmm0

内容的提问来源于stack exchange，提问作者saolof