algorithm - Cálculo de la representación negabinary de un número dado sin bucles
language-agnostic bit-manipulation (2)
¿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);
}
"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
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 n se reemplaza por 2 n + 1 - 2 n .
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 n -1) → 1/3 × (2 n -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 n -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.)