What's the faster way to implement the signed-to-unsigned map r(x)= 2x-1 if x>0 and r(x) = 2x otherwise

Question

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.

A popular map is r(x)= 2x-1 if x>0 and r(x) = 2x otherwise.

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

What's the fastest way?

Answer 1

If you operate on bytes lookup table must be the fastest.

For larger integers, CMOV-based implementation would be decent. You can also utilize SSE instructions here.

Answer 2

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...

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.

Edit: 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;
}

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

Answer 3

If your implementation supports arithmetic right-shift of signed values, try this:

#define MAP(x) ((x)<<1 ^ (x)>>sizeof(x)*CHAR_BIT-1)

For implementations which don't have signed right-shift, you can use:

#define RSHIFT(x,n) ((x)>>n | \
  (-(1 & (x)>>sizeof(x)*CHAR_BIT-1))<<sizeof(x)*CHAR_BIT-1-n<<1))

(You should check this for correctness...)