Editing Non-adjacent form (section)

==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 numeral system|binary]] representations of values, half of all [[bit]]s 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]].<ref>{{cite conference|last1=Hewlitt|first1=R.M.|title=Canonical signed digit representation for FIR digital filters|conference=Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on|pages=416–426|doi=10.1109/SIPS.2000.886740|year=2000|isbn=978-0-7803-6488-2|s2cid=122082511}}</ref>

Obviously, at most half of the digits are non-zero, which was the reason it was introduced by G.W. Reitweisner <ref name="Reitweisner">{{cite journal |first=George W. |last=Reitwiesner |title=Binary Arithmetic |journal=Advances in Computers |date=1960 |volume=1 |pages=231–308 |doi=10.1016/S0065-2458(08)60610-5|isbn=9780120121014 }}</ref> 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'' +&thinsp;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]].