Вычисление отрицательного представления заданного числа без петель

Question

Не могли бы вы дать убедительное объяснение или математическое доказательство того, почему следующая функция вычисляет представление заданного числа negabinary?

function quickNegabinary(number) { 
    var mask = 0xAAAAAAAA; 
    return ((number + mask)^mask).toString(2); 
} 

Answer 1

Negabinary обозначения

Negabinary нотация использует десятичную -2. Это означает, что, как и в любой системе счисления с отрицательным основанием, каждый бит имеет отрицательное значение:

position: ...  7 6 5 4 3 2 1 0 

binary:  ... 128 64 32 16 8 4 2 1 
negabinary: ... -128 +64 -32 +16 -8 +4 -2 +1 

метод быстрого преобразования

→ метод быстрой двоичной negabinary преобразования добавляет, а затем исключающее это номер с 0xAAAAAAAA или двоичный ...10101010 (маска, которая указывает нечетные позиции, которые имеют отрицательное значение в негативной нотации), например для значения 82:

binary:    01010010 = 82 (binary: 64 + 16 + 2) 
mask:     10101010 = 170 
bin+mask    11111100 = 252 
(bin+mask) XOR mask: 01010110 = 82 (negabinary: 64 + 16 + 4 - 2) 

Как это работает: один набор бит

Легко видеть, как работает метод, если взять пример ряда только одного набора бит в двоичной нотации. Если набор бит в ровном положении, ничего не меняется:

binary:    00000100 = 4 (binary: 4) 
mask:     10101010 = 170 
bin+mask    10101110 = 174 
(bin+mask) XOR mask: 00000100 = 4 (negabinary: 4) 

Однако, если набор бит в нечетном положении:

binary:    00001000 = 8 (binary: 8) 
mask:     10101010 = 170 
bin+mask    10110010 = 178 
(bin+mask) XOR mask: 00011000 = 8 (negabinary: 16 - 8) 

набор бит сдвигается влево (путем добавления 1 к это) и затем объединяется с отрицательным значением его исходного значения (посредством XOR-ing с маской), так что бит со значением 2 ⁿ заменяется на 2 ^{n + 1} - 2 ⁿ.

Таким образом, вы можете думать о методе быстрой конвертации просто как: «заменять каждые 2 на 4 - 2, каждые 8 ​​на 16 - 8, каждые 32 на 64 - 32 и так далее».

Как это работает: несколько набор битов

При преобразовании числа с несколькими установленными битами, результаты преобразования числа с одним набором бит, как описано выше, может быть просто суммироваться. Объединение, например,в одной набор-битовые примеры 4 и 8 (см выше), чтобы сделать 12:

binary:    00001100 = 12 (binary: 8 + 4) 
mask:     10101010 = 170 
bin+mask    10110110 = 182 
(bin+mask) XOR mask: 00011100 = 12 (negabinary: 16 - 8 + 4) 

Или, для более сложного примера, где перевозится несколько цифр:

binary:    00111110 = 62 (binary: 32 + 16 + 8 + 4 + 2) 
mask:     10101010 = 170 
bin+mask    11101000 = 232 
(bin+mask) XOR mask: 01000010 = 62 (negabinary: 64 - 2) 

Что здесь происходит является то, что в сумме, которая описывает двоичное число:

32 + 16 + 8 + 4 + 2

32 превращается в 64 - 32, 8 в 16 - 8 и 2 до 4 - 2, так что сумма становится:

64 - 32 + 16 + 16 - 8 + 4 + 4 - 2

, где два 16-х затем переносятся, чтобы стать 32, и два 4-х выполняются, чтобы стать 8:

64 - 32 + 32 - 8 + 8 - 2

и -32 и +32 ca мена друг друга, и -8 и +8 компенсируют друг друга, чтобы дать:

64 - 2

Или, используя negabinary арифметику:

  +1 +1     (carry) 
    0 1 -1 0 0 0 0 0 = 32 (negabinary: 64 - 32) 
    0 0 0 1 0 0 0 0 = 16 (negabinary: 16) 
    0 0 0 1 -1 0 0 0 = 8 (negabinary: 16 - 8) 
    0 0 0 0 0 1 0 0 = 4 (negabinary: 4) 
    + 0 0 0 0 0 1 -1 0 = 2 (negabinary: 4 - 2) 
    ---------------------- 
    = 0 1 0 0 0 0 -1 0 = 62 (negabinary: 64 - 2) 

Отрицательный значения

Метод быстрой конверсии также работает для отрицательных чисел в двухзначной нотации дополнения, например:

binary:      11011010 = -38 (two's complement) 
mask:       10101010 = -86 (two's complement) 
bin+mask      10000100 = -124 (two's complement) 
(bin+mask) XOR mask:   00101110 = -38 (negabinary: -32 - 8 + 4 - 2) 

binary:    11111111 11011010 = -38 (two's complement) 
mask:    10101010 10101010 = -21846 (two's complement) 
bin+mask    10101010 10000100 = -21884 (two's complement) 
(bin+mask) XOR mask: 00000000 00101110 = -38 (negabinary: -32 - 8 + 4 - 2) 

Диапазон и переполнения

Диапазон из числа negabinary с п битов (где п четное число) составляет:

-2/3 × (2 ⁿ -1) → 1/3 × (2 ⁿ -1)

Или, для общей битовой глубины:

8-bit:   -170 ~    85 
16-bit:   -43,690 ~   21,845 
32-bit: -2,863,311,530 ~ 1,431,655,765 
64-bit:  -1.23e+19 ~  6.15e+18 
80-bit:  -8.06e+23 ~  4.03e+23 

Этого диапазон ниже, чем оба знаковых и беззнаковых стандартных целочисленных представлений с одной и той же битовой глубиной, так что оба подписанных и целые числа без знака могут быть слишком большими, чтобы быть представленный в негативной нотации с одинаковой глубиной бита.

Хотя метод быстрой конверсии может работать, казалось бы, в переполнение для отрицательных значений ниже -1/6 × (2 ^п -4), результат преобразования по-прежнему правильно:

binary:      11010011 = -45 (two's complement) 
mask:       10101010 = -86 (two's complement) 
bin+mask    11111111 01111101 = -131 (two's complement) 
overflow truncated:   01111101 = 125 (two's complement) 
(bin+mask) XOR mask:   11010111 = -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1) 

binary:    11111111 11010011 = -45 (two's complement) 
mask:    10101010 10101010 = -21846 (two's complement) 
bin+mask    10101010 01111101 = -21891 (two's complement) 
(bin+mask) XOR mask: 00000000 11010111 = -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1) 

Обратных функции

Negabinary номер может быть преобразован обратно в стандартные целочисленных значения путем изменения и дополнения XOR-кий с маской, например:

uint64_t negabinary(int64_t bin) { 
    if (bin > 0x5555555555555555) throw std::overflow_error("value out of range"); 
    const uint64_t mask = 0xAAAAAAAAAAAAAAAA; 
    return (mask + bin)^mask; 
} 

int64_t revnegabin(uint64_t neg) { 
    // const uint64_t even = 0x2AAAAAAAAAAAAAAA, odd = 0x5555555555555555; 
    // if ((neg & even) > (neg & odd)) throw std::overflow_error("value out of range"); 
    const uint64_t mask = 0xAAAAAAAAAAAAAAAA; 
    return (mask^neg) - mask; 
} 

(Если обратная функция вызывается только на negabinary номеров, созданных с помощью функции negabinary(), не существует никакого риска переполнения. Однако 64-битные отрицательные числа из других источников могут иметь значение ниже диапазона int64_t, поэтому проверка переполнения становится необходимой.)

Answer 2

"0xAAAAAAAA" - одно из тех магических чисел, которое содержит последовательность из 10 (двоичных) узоров. Это используется как маска, потому что вы выполняете побитовое XOR-операцию. Когда вы добавляете номер в эту маску и выполняете XOR, на результат будут влиять только те биты, которые предоставляются номером, остальное будет 0 в результате. [Поскольку XOR двух одинаковых битов равен 0]. Наконец, toString (2) преобразует результат в двоичный код

Пример: -> Рассмотрим 3 - ваш номер. Добавить 3 до 2863311530 [который является десятичным представлением 0xAAAAAAAA]. -> XOR сумма (маска + 3) с 0xAAAAAAAA, которая является ... 10101010^.... 10101010. Это дает 111 (так как последние 3 соответствующих битов в маске, а сумма разные) -> Преобразование 111 в двоичной, что 7