Sistema numérico binário inclinado - Skew binary number system

O sistema de inclinação número binário é um sistema de numeração posicionai não-padrão em que o N -ésimo dígito contribui com um valor de vezes o dígito (dígitos são indexados a partir de 0) em vez de vezes como o fazem em binário . Cada dígito tem um valor de 0, 1 ou 2. Um número pode ter muitas representações binárias distorcidas. Por exemplo, um número decimal 15 pode ser escrito como 1000, 201 e 122. Cada número pode ser escrito exclusivamente na forma canônica binária inclinada onde há apenas no máximo uma instância do dígito 2, que deve ser o dígito diferente de zero menos significativo . Nesse caso, 15 é escrito canonicamente como 1000. ${\ displaystyle 2 ^ {n + 1} -1}$${\ displaystyle 2 ^ {n}}$

Exemplos

As representações binárias de inclinação canônica dos números de 0 a 15 são mostradas na tabela a seguir:

Operações aritméticas

A vantagem do binário skew é que cada operação de incremento pode ser feita com no máximo uma operação de transporte . Isso explora o fato de que . O incremento de um número binário inclinado é feito definindo os únicos dois como zero e incrementando o próximo dígito de zero a um ou um a dois. Quando os números são representados usando uma forma de codificação de comprimento de execução como listas vinculadas de dígitos diferentes de zero, o incremento e a diminuição podem ser executados em tempo constante. ${\ displaystyle 2 (2 ^ {n + 1} -1) + 1 = 2 ^ {n + 2} -1}$

Outras operações aritméticas podem ser realizadas alternando entre a representação binária distorcida e a representação binária.

Da representação binária distorcida à representação binária

Dado um número binário inclinado, seu valor pode ser calculado por um loop, computando os valores sucessivos de e adicionando-o uma ou duas vezes para cada um, de modo que o ésimo dígito seja 1 ou 2, respectivamente. Um método mais eficiente é agora fornecido, com apenas representação de bits e uma subtração. ${\ displaystyle 2 ^ {n + 1} -1}$${\ displaystyle n}$${\ displaystyle n}$

O número binário inclinado da forma sem 2 e com 1s é igual ao número binário menos . Let representa o dígito repetido vezes. O número binário inclinado da forma com 1s é igual ao número binário 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}$

Da representação binária à representação binária distorcida

De maneira semelhante à seção anterior, o número binário da forma com 1s é igual ao número binário inclinado mais . Observe que, como a adição não está definida, a adição corresponde a incrementar o número de vezes. No entanto, é limitado pelo logaritmo de e a incrementação leva um tempo constante. Portanto, a transformação de um número binário em um número binário enviesado ocorre no tempo linear no comprimento do 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}$

Formulários

Os números binários skew foram desenvolvidos por Eugene Myers em 1983 para uma estrutura de dados puramente funcional que permite as operações do tipo de dados abstratos da pilha e também permite a indexação eficiente na sequência de elementos da pilha. Mais tarde, eles foram aplicados a pilhas binomiais de inclinação , uma variante de pilhas binomiais que suportam operações de inserção de pior caso em tempo constante.

Veja também

• Lógica de três valores
• Representação binária redundante
• código n-áry Gray

Notas