Sesgar el sistema numérico binario

El sistema numérico binario sesgado es un sistema numérico posicional no estándar en el que el enésimo dígito aporta un valor de veces el dígito (los dígitos están indexados desde 0) en lugar de veces como lo hacen en binario . Cada dígito tiene un valor de 0, 1 o 2. Un número puede tener muchas representaciones binarias sesgadas. Por ejemplo, un número decimal 15 se puede escribir como 1000, 201 y 122. Cada número se puede escribir de forma única en forma canónica binaria sesgada donde solo hay como máximo una instancia del dígito 2, que debe ser el dígito distinto de cero menos significativo . En este caso, 15 se escribe canónicamente como 1000. ${\displaystyle 2^{n+1}-1}$ ${\displaystyle 2^{n}}$

Ejemplos

Las representaciones binarias sesgadas canónicas de los números del 0 al 15 se muestran en la siguiente tabla: ^[1]

Operaciones aritméticas

La ventaja del binario sesgado es que cada operación de incremento se puede realizar con como máximo una operación de acarreo . Esto aprovecha el hecho de que . El incremento de un número binario sesgado se realiza estableciendo los únicos dos en cero e incrementando el siguiente dígito de cero a uno o de uno a dos. Cuando los números se representan utilizando una forma de codificación de longitud de ejecución como listas vinculadas de dígitos distintos de cero, el incremento y la decremento se pueden realizar en tiempo constante. ${\displaystyle 2(2^{n+1}-1)+1=2^{n+2}-1}$

Se pueden realizar otras operaciones aritméticas cambiando entre la representación binaria sesgada y la representación binaria. ^[2]

Conversión entre número decimal y binario sesgado

Para convertir de un número decimal a un número binario sesgado, se puede utilizar la siguiente fórmula: ^[3]

Caso base : ${\displaystyle a(0)=0}$

Caso de inducción : ${\displaystyle a(2^{n}-1+i)=a(i)+10^{n-1}}$

Límites : ${\displaystyle 0\leq i\leq 2^{n}-1,n\geq 1}$

Para convertir de un número binario sesgado a decimal, se puede utilizar la definición de número binario sesgado:

${\displaystyle S=\sum _{i=0}^{N}b_{i}(2^{i+1}-1)}$, donde , st. el único bit menos significativo (lsb) es 2. ${\displaystyle b_{i}\in {0,1,2}}$ ${\displaystyle b_{lsb}}$

Código C ++ para convertir un número decimal en un número binario sesgado

#include <iostream> #include <cmath> #include <algoritmo> #include <iterador>    usando el espacio de nombres estándar ;  dp largo [ 10000 ]; //Usando la fórmula a(0) = 0; para n >= 1, a(2^n-1+i) = a(i) + 10^(n-1) para 0 <= i <= 2^n-1, //tomado de The On-Line Enciclopedia de secuencias enteras (https://oeis.org/A169683)convertToSkewbinary largo ( decimal largo ){   int maksIndex = 0 ; marcas largas = 1 ; mientras ( maks < decimal ){ maks *= 2 ; maksIndex ++ ; }                   for ( int j = 1 ; j <= maksIndex ; j ++ ){ potencia larga = pow ( 2 , j ); para ( int i = 0 ; i <= potencia -1 ; i ++ ) dp [ i + potencia -1 ] = pow ( 10 , j -1 ) + dp [ i ]; }                              devolver dp [ decimal ]; } int main () { std :: llenar ( std :: comenzar ( dp ), std :: terminar ( dp ), -1 ); dp [ 0 ] = 0 ; //Se puede comparar con los números proporcionados en //https://oeis.org/A169683 for ( int i = 50 ; i < 125 ; i ++ ){ long current = convertToSkewbinary ( i ); cout << actual << endl ; }                                devolver 0 ; } 

Código C ++ para convertir un número binario sesgado en un número decimal

#incluir <iostream> #incluir <cmath>  usando el espacio de nombres estándar ;  // Decimal = (0|1|2)*(2^N+1 -1) + (0|1|2)*(2^(N-1)+1 -1) + ... // + (0|1|2)*(2^(1+1) -1) + (0|1|2)*(2^(0+1) -1) // // Entrada esperada: un entero positivo/ long donde los dígitos son 0,1 o 2, el bit/dígito menos significativo es 2. // long convertToDecimal ( long skewBinary ){   int k = 0 ; decimal largo = 0 ; mientras ( skewBinary > 0 ){ int dígito = skewBinary % 10 ; skewBinary = techo ( skewBinary / 10 ); decimal += ( pow ( 2 , k + 1 ) -1 ) * dígito ; k ++ ; } devolver decimal ; } int principal () {                              prueba int [] = { 0 , 1 , 2 , 10 , 11 , 12 , 20 , 100 , 101 , 102 , 110 , 111 , 112 , 120 , 200 , 1000 };    for ( int i = 0 ; i < tamaño de ( prueba ) / tamaño de ( int ); i ++ ) cout << convertToDecimal ( prueba [ i ]) << endl ;;             devolver 0 ; } 

De la representación binaria sesgada a la representación binaria

Dado un número binario sesgado, su valor se puede calcular mediante un bucle, calculando los valores sucesivos de y sumándolos una o dos veces para cada uno, de modo que el enésimo dígito sea 1 o 2 respectivamente. Ahora se proporciona un método más eficiente, con sólo representación de bits y una resta. ${\displaystyle 2^{n+1}-1}$ ${\displaystyle n}$ ${\displaystyle n}$

El número binario sesgado de la forma sin 2 y con unos es igual al número binario menos . Let representa el dígito repetido veces. El número binario sesgado de la forma con unos es igual al número binario menos . ${\displaystyle b_{0}\dots b_{n}}$ ${\displaystyle m}$ ${\displaystyle 0b_{0}\dots b_{n}}$ ${\displaystyle m}$ ${\displaystyle d^{c}}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle 0^{c_{0}}21^{c_{1}}0b_{0}\dots b_{n}}$ ${\displaystyle m}$ ${\displaystyle 0^{c_{0}+c_{1}+2}1b_{0}\dots b_{n}}$ ${\displaystyle m}$

De la representación binaria a la representación binaria sesgada

De manera similar a la sección anterior, el número binario de la forma con unos es igual al número binario sesgado más . Tenga en cuenta que, dado que la suma no está definida, sumar corresponde a incrementar el número de veces. Sin embargo, está limitado por el logaritmo de y el incremento toma un tiempo constante. Por lo tanto, la transformación de un número binario en un número binario sesgado se ejecuta en un tiempo lineal a lo largo de la longitud del número. ${\displaystyle b}$ ${\displaystyle b_{0}\dots b_{n}}$ ${\displaystyle m}$ ${\displaystyle b_{1}\dots b_{n}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle b}$

Aplicaciones

Los números binarios sesgados fueron desarrollados por Eugene Myers en 1983 para una estructura de datos puramente funcional que permite las operaciones del tipo de datos abstractos de la pila y también permite una indexación eficiente en la secuencia de elementos de la pila. ^[4] Posteriormente se aplicaron para sesgar montones binomiales , una variante de montones binomiales que admiten operaciones de inserción en el peor de los casos en tiempo constante. ^[5]

Ver también

• Lógica de tres valores
• Representación binaria redundante
• código Gray n-ario

Notas

1. Sloane, Nueva Jersey (ed.). "Secuencia A169683". La enciclopedia en línea de secuencias enteras . Fundación OEIS.
2. Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki (2012). "Dos sistemas numéricos binarios sesgados y una aplicación" (PDF) . Teoría de los Sistemas Computacionales . 50 : 185-211. doi :10.1007/s00224-011-9357-0. S2CID  253736860.
3. La enciclopedia en línea de secuencias enteras. "Los números binarios sesgados canónicos".
4. Myers, Eugene W. (1983). "Una pila de acceso aleatorio aplicativa". Cartas de procesamiento de información . 17 (5): 241–248. doi :10.1016/0020-0190(83)90106-0. SEÑOR  0741239.
5. Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996). "Colas de prioridad puramente funcionales óptimas". Revista de programación funcional . 6 (6): 839–857. doi : 10.1017/s095679680000201x .