title: Non-adjacent form
text: # Non-adjacent form
  
  Part of a series on :
  
  Numeral systems :
  
  Place-value notation
  
  Hindu-Arabic numerals
  
  Western Arabic
  
  Eastern Arabic
  
  Bengali
  
  Devanagari
  
  Gujarati
  
  Gurmukhi
  
  Odia
  
  Sinhala
  
  Tamil
  
  Malayalam
  
  Telugu
  
  Kannada
  
  Dzongkha
  
  Tibetan
  
  Balinese
  
  Burmese
  
  Javanese
  
  Khmer
  
  Lao
  
  Mongolian
  
  Sundanese
  
  Thai
  
  East Asian systems
  
  Contemporary
  
  Chinese
  
  Suzhou
  
  Hokkien
  
  Japanese
  
  Korean
  
  Vietnamese
  
  Historic
  
  Counting rods
  
  Tangut
  
  Other systems
  
  History
  
  Ancient
  
  Babylonian
  
  Post-classical
  
  Cistercian
  
  Mayan
  
  Muisca
  
  Pentadic
  
  Quipu
  
  Rumi
  
  Contemporary
  
  Cherokee
  
  Kaktovik (Iñupiaq)
  
  By radix/base
  
  Common radices/bases
  
  2
  
  3
  
  4
  
  5
  
  6
  
  8
  
  10
  
  12
  
  16
  
  20
  
  60
  
  (table)
  
  Non-standard radices/bases
  
  Bijective (1)
  
  Signed-digit (balanced ternary)
  
  Mixed (factorial)
  
  Negative
  
  Complex (2i)
  
  Non-integer (φ)
  
  Asymmetric :
  
  Sign-value notation
  
  Non-alphabetic
  
  Aegean
  
  Attic
  
  Aztec
  
  Brahmi
  
  Chuvash
  
  Egyptian
  
  Etruscan
  
  Kharosthi
  
  Prehistoric counting
  
  Proto-cuneiform
  
  Roman
  
  Tally marks
  
  Alphabetic
  
  Abjad
  
  Armenian
  
  Alphasyllabic
  
  Akṣarapallī
  
  Āryabhaṭa
  
  Kaṭapayādi
  
  Coptic
  
  Cyrillic
  
  Geʽez
  
  Georgian
  
  Glagolitic
  
  Greek
  
  Hebrew :
  
  List of numeral systems :
  
  vte :
  
  The non-adjacent form (NAF) of a number is a unique signed-digit representation, in which non-zero values cannot be adjacent. For example:
  
      (0 1 1 $1)_2$ = 4 + 2 + 1 = 7
      (1 0 −1 $1)_2$ = 8 − 2 + 1 = 7
      (1 −1 1 $1)_2$ = 8 − 4 + 2 + 1 = 7
      (1 0 0 $−1)_2$ = 8 − 1 = 7
  
  All are valid signed-digit representations of 7, but only the final representation, (1 0 0 $−1)_2,$ is in non-adjacent form.
  
  The non-adjacent form is also known as "canonical signed digit" representation.
  
  ## Properties
  
  NAF assures a unique representation of an integer, but the main benefit of it is that the Hamming weight of the value will be minimal. For regular binary representations of values, half of all bits will be non-zero, on average, but with NAF this drops to only one-third of all digits. This leads to efficient implementations of add/subtract networks (e.g. multiplication by a constant) in hardwired digital signal processing.
  
  Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner for speeding up early multiplication algorithms, much like Booth encoding.
  
  Because every non-zero digit has to be adjacent to two 0s, the NAF representation can be implemented such that it only takes a maximum of m + 1 bits for a value that would normally be represented in binary with m bits.
  
  The properties of NAF make it useful in various algorithms, especially some in cryptography; e.g., for reducing the number of multiplications needed for performing an exponentiation. In the algorithm, exponentiation by squaring, the number of multiplications depends on the number of non-zero bits. If the exponent here is given in NAF form, a digit value 1 implies a multiplication by the base, and a digit value −1 by its reciprocal.
  
  Other ways of encoding integers that avoid consecutive 1s include Booth encoding and Fibonacci coding.
  
  ## Converting to NAF
  
  There are several algorithms for obtaining the NAF representation of a value given in binary. One such is the following method using repeated division; it works by choosing non-zero coefficients such that the resulting quotient is divisible by 2 and hence the next coefficient a zero.
  
  A faster way is given by Prodinger where x is the input, np the string of positive bits and nm the string of negative bits:
  
  which is used, for example, in A184616.
  
  