Signed Binary Representations Revisited

Juliana Lai Yeh Lee
Orientador: Routo Terada
Instituto de Matemática e Estatística
Universidade de São Paulo

Conceitos e tecnologias estudadas

Non-Adjacent Form (NAF)

Non-Adjacent Form (NAF) é uma representação binária com sinal da forma:

d = d[n - 1] 2^n-1 + d[n - 2] 2^{n - 2} + ... + d[1] 2¹ + d[0] 2⁰

onde d[i] Є {-1, 0, 1} e d[i] * d[i - 1] = 0 para i = 1, 2, ..., n - 1.

A representação NAF é obtida percorrendo-se a representação binária usual da DIREITA para a ESQUERDA, aplicando-se a conversão:

1|0|-1 ← 1|1

repetidamente, onde a | b denota a concatenação dos bits a e b.

Um exemplo de NAF:

345 =   1    0   1    0   1    1   0   0   1
        1    0   1    1   0   -1   0   0   1
        1    1   0   -1   0   -1   0   0   1
     1  0   -1   0   -1   0   -1   0   0   1

Onde 1 0 -1 0 -1 0 -1 0 0 1 é a representação NAF do número 345.

DCC - IME - USP