Еще один способ думать о зигзагообразном картировании - это небольшое искажение представления знака и величины.
В зигзагообразном отображении младший значащий бит (lsb) отображения указывает знак значения: если оно равно 0, то исходное значение неотрицательно, если оно равно 1, то исходное значение отрицательно.
Неотрицательные значения просто сдвигаются влево на один бит, чтобы освободить место для знакового бита в lsb.
Для отрицательных значений вы можете сделать то же самое однобитовое смещение влево для абсолютного значения (величины) числа и просто сделать так, чтобы lsb указывал знак. Например, -1 может отображаться в 0x03 или 0b00000011, где lsb указывает, что оно отрицательно, а величина 1 смещена влево на 1 бит.
Ужасная вещь в этом представлении знака и величины - "отрицательный ноль", отображенный как 0x01 или 0b00000001. Этот нулевой вариант «использует» одно из наших значений и сдвигает диапазон целых чисел, который мы можем представить, на единицу. Вероятно, нам нужно преобразовать отрицательный ноль в специальный случай в -2 ^ 63, чтобы мы могли представить полный диапазон дополнения 64b 2 [-2 ^ 63, 2 ^ 63). Это означает, что мы использовали одну из наших ценных однобайтовых кодировок для представления значения, которое очень, очень, очень редко будет использоваться в кодировке, оптимизированной для небольших чисел, и мы представили специальный случай, который является плохим.
Именно здесь происходит поворот зигзага на это представление знака и величины. Знаковый бит все еще находится в lsb, но для отрицательных чисел мы вычитаем единицу из величины, а не из специального кожуха отрицательный ноль. Теперь -1 отображается в 0x01, а -2 ^ 63 также имеет представление в неаккуратном случае (т. Е. - величина 2 ^ 63 - 1, сдвиг влево на один бит, с установленным битом lsb / sign, что означает, что все биты установлены в 1 с) .
Итак, еще один способ думать о зигзагообразном кодировании заключается в том, что это более умное представление знака и величины: бит знака сохраняется в lsb, 1 вычитается из величины отрицательных чисел, а величина смещается влево на единицу. бит.
Быстрее реализовать эти преобразования, используя безусловные побитовые операторы, которые вы разместили, вместо явного тестирования знака, особого случая манипулирования отрицательными значениями (например, - отрицание и вычитание 1 или побитовое отображение нет), сдвиг величины и затем явно установите бит знака lsb. Однако по сути они эквивалентны, и из этого более явного ряда шагов по знаку и величине может быть легче понять, что и почему мы делаем эти вещи.
Я предупрежу вас, хотя отрицательные значения сдвига битов в C / C ++ не переносимы и их следует избегать. Сдвиг влево отрицательного значения имеет неопределенное поведение, а сдвиг вправо отрицательного значения - поведение, определяемое реализацией. Даже сдвиг влево положительного целого числа может иметь неопределенное поведение (например, если вы переместитесь в знаковый бит, это может вызвать ловушку или что-то еще хуже). Так что, в общем, не сдвигайте битовые подписанные типы в C / C ++. "Просто сказать нет."
Приведите сначала к неподписанной версии типа, чтобы получить безопасные, четко определенные результаты в соответствии со стандартом. Это означает, что тогда у вас не будет арифметического сдвига отрицательных значений - только логический сдвиг, поэтому вам необходимо настроить логику, чтобы учесть это.
Вот безопасные и переносимые версии зигзагообразных отображений для 64b целых чисел в C (обратите внимание на арифметическое отрицание):
#include <stdint.h>
uint64_t zz_map( int64_t x )
{
return ( ( uint64_t ) x << 1 ) ^ -( ( uint64_t ) x >> 63 );
}
int64_t zz_unmap( uint64_t y )
{
return ( int64_t ) ( ( y >> 1 ) ^ -( y & 0x1 ) );
}