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

问题描述

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

Mapping signed to unsigned integers bijectively can be done using common techniques like Two's complement. Unfortunately, they fail to map small negative integers to small numbers. For compression algorithms, we often want to preserve the absolute value of numbers as much as possible: small negative and positive numbers must be mapped to small numbers.

如果x ＜0，则流行的映射是r(x)＝-2x-1，如果x＞ ＝ 0，则r(x)＝ 2x.(如果x 0，则相似度为2x + 1.)

A popular map is r(x)= -2x-1 if x<0 and r(x) = 2x if x>=0. (A similar one is r(x) = -2x if x<=0 and 2x+1 if x>0.)

天真地实施，此地图相对较慢.当然，它比仅将有符号整数转换为无符号整数(默默地应用Two's Complement)要慢得多.

Implemented naively, this map is relatively slow. Certainly much slower than merely casting signed integers to unsigned integers (which silently applies Two's Complement).

最快的方法是什么?

推荐答案

静默应用二进制补码，是的，在大多数蒙大拿平台上，这只是编译器的 nop 以不同的方式解释您的数据.因此，这真的很难被克服.

silently applies Two's complement, yes, on most mondern platforms this is just a nop the compiler just interprets your data differently. So this is really hard to beat.

为便于比较，请提供一些基准...

For your comparision it would be good if you'd provide some benchmarks...

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

If I am not mistaken 2 * abs(x) + signbit can be done with a cyclic left shift of the bits. So if your platform has such an instruction, this should be easy to implement with inline assembler and should result in just one instruction at the end.

我误会了，这个简单的操作仅适用于负数的符号和值表示形式.

I was mistaken, this simple thing would only work with sign and value representation of negative numbers.

对于二进制补码，如果输入为负，则必须取反旋转结果.像

For two's complement you'd have to negate the result of the rotation if the input had been negative. Something like

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条指令

I looked into the assembler that it produced by gcc. Looks quite good, has just 5 instructions

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

这篇关于如果x> 0且r(x)= 2x，则实现有符号到无符号映射r(x)= 2x-1的更快方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！