Какой более быстрый способ реализовать карту со знаком в без знака r (x) = 2x-1, если x> 0 и r (x) = 2x в противном случае

Question

Отображение со знаком на целые числа без знака может быть выполнено с использованием обычных методов, таких как дополнение к двум.К сожалению, они не могут отобразить маленькие отрицательные целые числа на маленькие числа.Для алгоритмов сжатия мы часто хотим максимально сохранить абсолютное значение чисел: маленькие отрицательные и положительные числа должны быть сопоставлены с маленькими числами.

Популярная карта - это r (x) = -2x-1если x <0 и r (x) = 2x, если x> = 0.(Аналогичным является r (x) = -2x, если x <= 0, и 2x + 1, если x> 0.)

Наивно реализованная, эта карта является относительно медленной.Конечно, намного медленнее, чем простое приведение целых чисел со знаком к целым числам без знака (при этом молча применяется дополнение к двум).

Какой самый быстрый способ?

Answer 1

silently applies Two's complement, да, на большинстве современных платформ это просто 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

Answer 2

Если вы работаете с байтами, таблица поиска должна быть самой быстрой.

Для больших целых чисел реализация на основе CMOV была бы приличной. Вы также можете использовать инструкции SSE здесь.

Answer 3

Если ваша реализация поддерживает арифметическое смещение вправо со знаком, попробуйте следующее:

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

Для реализаций, которые не имеют подписанного сдвига вправо, вы можете использовать:

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

(Вы должны проверить это на правильность ...)