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

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

function quickNegabinary(number) {
  var mask = 0xAAAAAAAA;
  return ((number + mask) ^ mask).toString(2);
}
 GolezTrol05 июн. 2016 г., 04:25
Вы заметили, что версии (тоже версия C) на странице Википедии содержат реальные комментарии, которые хотя бы частично объясняют это? Почему вы удалили их? Это загадка?
 Misha Moroshko05 июн. 2016 г., 04:32
@GolezTrol Я чувствовал, что комментарии там на самом деле не объясняют, как это работает. Я ищу гораздо более подробное объяснение.

Ответы на вопрос(1)

Решение Вопроса

Негабаритная запись

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  

Метод быстрой конвертации

Метод быстрого двоичного → негабинарного преобразования добавляет и затем число xor с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-ы с маской), так что бит со значением 2n заменяется на 2п + 1 - 2n.

Таким образом, вы можете думать о методе быстрого преобразования просто как: «заменить каждые 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 отменяют друг друга, а -8 и +8 отменяют друг друга, давая:

64 - 2

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

          +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)  

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

Диапазон неабинарного числа с n битами (где n - четное число):

-2/3 × (2n-1) → 1/3 × (2n-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 × (2n-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 (), риск переполнения отсутствует. Однако 64-битные неабинарные числа из других источников могут иметь значение ниже диапазона int64_t, поэтому проверка переполнения становится необходимо.)

 Misha Moroshko07 июн. 2016 г., 11:54
Я думаю, что теперь лучше. Еще раз спасибо за все усилия!
 m6906 июн. 2016 г., 15:15
@MishaMoroshko По своей сути объяснение таково: «на каждые 2 или 8 или ..., которые вот-вот превратятся в -2 или -8 или ... добавляется 4 или 16 или ..., так что 2 становится 4 -2, 8 становится 16-8, ... ". Часть "последовательные биты" просто демонстрирует, что это может быть сложено для нескольких битов, например, 8 + 4 + 2 становится 16-8 + 4 + 4-2, а затем два 4 переносятся и становятся 8, а затем -8 и 8 взаимно отменяют друг друга, и у вас остается 16-2 , Может быть, я должен добавить эту десятичную версию объяснения для ясности?
 Misha Moroshko06 июн. 2016 г., 13:07
Вот Это Да! Спасибо за такой подробный и обстоятельный ответ. Я очень ценю ваши усилия! Начало вашего ответа действительно простое и убедительное, нопоследовательные биты раздел не такой прямой, как я надеялся. Спасибо, в любом случае!

Ваш ответ на вопрос