algorithm - Cálculo de la representación negabinary de un número dado sin bucles

language-agnostic bit-manipulation

Question

¿Podría proporcionar una explicación convincente, o una prueba matemática, de por qué la siguiente función calcula la representación negabinary de un número dado?

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

Answer 1

"0xAAAAAAAA" es uno de esos números mágicos que contiene una secuencia de 10 patrones (binarios). Esto se usa como máscara porque está realizando una operación XOR a nivel de bit. Cuando agrega el número a esta máscara y hace un XOR, el resultado se vería afectado solo por los bits proporcionados por el número, el resto sería 0 en el resultado. [Dado que XOR de dos mismos bits es 0]. Finalmente, toString (2) está convirtiendo el resultado en binario

Ejemplo: -> Considera 3 es tu número. Agregue 3 a 2863311530 [que es la representación decimal de 0xAAAAAAAA]. -> XOR la ​​suma (máscara + 3) con 0xAAAAAAAA, que es ... 10101010 1101 ^ .... 10101010. Esto le da 111 (dado que los últimos 3 bits correspondientes en la máscara y la suma son diferentes) -> Convertir 111 en binario, que es 7

Answer 2

Notación Negabinary

La notación Negabinary usa una raíz de -2. Esto significa que, como en todos los sistemas numéricos con una base negativa, todos los demás bits tienen un valor negativo:

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  

Método de conversión rápida

El método de conversión binario → negabinary rápido agrega y luego xor es un número con 0xAAAAAAAA , o binario ...10101010 (una máscara que indica las posiciones impares que tienen un valor negativo en notación negabinary), p. Ej. Para el valor 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)  

Cómo funciona: un bit de configuración

Es fácil ver cómo funciona el método, si toma el ejemplo de un número con solo un bit establecido en notación binaria. Si el bit configurado está en una posición par, nada cambia:

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

Sin embargo, si el bit configurado está en una posición impar:

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

el bit configurado se desplaza hacia la izquierda (agregando 1) y luego se combina con el negativo de su valor original (mediante XOR-ing con la máscara), de modo que un bit con el valor 2 ⁿ se reemplaza por 2 ^{n + 1} - 2 ⁿ .

Así que puede pensar en el método de conversión rápida simplemente como: "reemplace cada 2 por 4 - 2, cada 8 por 16 - 8, cada 32 por 64 - 32, y así sucesivamente".

Cómo funciona: múltiples conjuntos de bits

Al convertir un número con varios bits configurados, los resultados de convertir un número con un bit establecido, como se describe anteriormente, pueden simplemente agregarse juntos. Combinando, por ejemplo, los ejemplos de un solo conjunto de bits de 4 y 8 (ver arriba) para hacer 12:

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

O, para un ejemplo más complicado, donde se llevan algunos dígitos:

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)  

Lo que sucede aquí es que en la suma que describe el número binario:

32 + 16 + 8 + 4 + 2

32 se convierte en 64 - 32, 8 en 16 - 8 y 2 en 4 - 2, de modo que la suma se convierte en:

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

donde los dos 16''s son llevados para convertirse en un 32 y los dos 4 son llevados para convertirse en un 8:

64 - 32 + 32 - 8 + 8 - 2

y el -32 y el +32 se cancelan entre sí, y el -8 y el +8 se cancelan entre sí, para dar:

64 - 2

O, usando la aritmética 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)  

Valores negativos

El método de conversión rápida también funciona para los números negativos en la notación de complemento de dos, por ejemplo:

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)  

Alcance y desbordamiento

El rango de un número negabinary con n bits (donde n es un número par) es:

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

O bien, para las profundidades de bits comunes:

 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  

Este rango es más bajo que las representaciones de entero estándar tanto firmadas como no firmadas con la misma profundidad de bits, por lo que los enteros con y sin signo pueden ser demasiado grandes para representarse en notación negativa con la misma profundidad de bit.

Aunque el método de conversión rápida aparentemente se puede encontrar en un desbordamiento de valores negativos por debajo de -1/6 × (2 ⁿ -4), el resultado de la conversión sigue siendo el correcto:

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)  

Función inversa

Los números de Negabinary se pueden convertir a valores enteros estándar invirtiendo la suma y XOR-ing con la máscara, por ejemplo:

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

(Si la función inversa solo se utiliza en números negabinary creados por la función negabinary (), no hay riesgo de desbordamiento. Sin embargo, los números negabinary de 64 bits de otras fuentes podrían tener un valor por debajo del rango int64_t, por lo que la verificación de desbordamiento se convierte necesario.)