El sistema numérico binario sesgado es un sistema numérico posicional no estándar en el que el n- ésimo dígito aporta un valor de multiplicado por el dígito (los dígitos se indexan 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 puede escribirse como 1000, 201 y 122. Cada número puede escribirse 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 menos significativo distinto de cero. En este caso, 15 se escribe canónicamente como 1000.
Ejemplos de
Las representaciones binarias de sesgo canónico de los números del 0 al 15 se muestran en la siguiente tabla: [1]
Decimal | Sesgar binario | binario |
---|---|---|
0 | 0 | 0 |
1 | 1 | 1 |
2 | 2 | 10 |
3 | 10 | 11 |
4 | 11 | 100 |
5 | 12 | 101 |
6 | 20 | 110 |
7 | 100 | 111 |
8 | 101 | 1000 |
9 | 102 | 1001 |
10 | 110 | 1010 |
11 | 111 | 1011 |
12 | 112 | 1100 |
13 | 120 | 1101 |
14 | 200 | 1110 |
15 | 1000 | 1111 |
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 aumento 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 enlazadas de dígitos distintos de cero, el incremento y la disminución se pueden realizar en tiempo constante.
Se pueden realizar otras operaciones aritméticas cambiando entre la representación binaria sesgada y la representación binaria. [2]
De la representación binaria sesgada a la representación binaria
Dado un número binario sesgado, su valor puede calcularse mediante un bucle, calculando los valores sucesivos de y agregarlo una o dos veces por cada tal que el El dígito es 1 o 2 respectivamente. Ahora se proporciona un método más eficiente, con solo representación de bits y una resta.
El número binario sesgado de la forma sin 2 y con 1s es igual al número binario menos . Dejar representa el dígito repetido veces. El número binario sesgado de la forma con 1s es igual al número binario menos .
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 1s 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 veces. Sin emabargo, está acotado por el logaritmo de y el incremento lleva un tiempo constante. Por lo tanto, la transformación de un número binario en un número binario sesgado se ejecuta en el tiempo de forma lineal en la longitud del número.
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 abstracto de la pila y también permite una indexación eficiente en la secuencia de elementos de la pila. [3] 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. [4]
Ver también
Notas
- ^ Sloane, N. J. A. (ed.). "Secuencia A169683" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki (2012). "Dos sistemas numéricos binarios sesgados y una aplicación" (PDF) . Teoría de los sistemas informáticos . 50 : 185–211. doi : 10.1007 / s00224-011-9357-0 .
- ^ Myers, Eugene W. (1983). "Una pila aplicativa de acceso aleatorio". Cartas de procesamiento de información . 17 (5): 241–248. doi : 10.1016 / 0020-0190 (83) 90106-0 . Señor 0741239 .
- ^ Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996). "Colas de prioridad óptimas puramente funcionales". Revista de programación funcional . 6 (6): 839–857. doi : 10.1017 / s095679680000201x .