c - 如果 x>0 且 r(x) = 2x，则实现有符号到无符号映射 r(x)= 2x-1 的更快方法是什么

Question

可以使用二进制补码等常用技术将有符号整数映射到无符号整数。不幸的是，他们无法将小负整数映射到小数字。对于压缩算法，我们通常希望尽可能保留数字的绝对值:小负数和正数必须映射到小数字。

如果 x<0，则流行的映射为 r(x)= -2x-1；如果 x>=0，则 r(x) = 2x。 (类似的是，如果 x<=0，则 r(x) = -2x；如果 x>0，则 r(x) = -2x。)

这张 map 的实现比较简单，速度相对较慢。当然比仅仅将有符号整数转换为无符号整数(默默地应用补码)要慢得多。

最快的方法是什么？

Answer 1

默默地应用二进制补码，是的，在大多数现代平台上，这只是一个nop，编译器只是以不同的方式解释您的数据。所以这真的很难被击败。

为了便于比较，如果您能提供一些基准就好了......

如果我没记错的话2 * abs(x) + signbit可以通过位的循环左移来完成。因此，如果您的平台有这样的指令，那么使用内联汇编器应该很容易实现，并且最后应该只产生一条指令。

编辑:我错了，这个简单的事情只适用于负数的符号和值表示。

对于二进制补码，如果输入为负，则必须对旋转结果求负。类似的东西

inline uint64_t rotateL(uint64_t x) {
  asm ("rolq %0" : "=r" (x) : "r" (x));
  return x;
}

inline uint64_t value(uint64_t x) {
  uint64_t ret = rotateL(x);
  return (ret % UINT64_C(2))
    ? -ret
    : ret;
}

我研究了 gcc 生成的汇编程序。看起来不错，只有 5 条说明

rolq    %rax
movq    %rax, %rdx
negq    %rdx
testb   $1, %al
cmovne  %rdx, %rax