Not sure how relevant the non-adjacent form (aka canonical
signed digit representation) is to anybody here for the design of
multipliers or dividers. If not important to you, please skip.

Browsing OEIS, I recently stumbled across a rather easy and
fast algorithm to bring a number into canonical signed digit
form. Koren does not give it and Wikipedia didn't have an entry
under https://en.wikipedia.org/wiki/Non-adjacent_form until I put
it there a week ago, so I thought it might not be well known.

The following C function

void bin2naf (uint64_t x, uint64_t *np, uint64_t *nm)
{ uint64_t xh, x3, c;
xh = x >> 1;
x3 = x + xh;
c = xh ^ x3;
*np = x3 & c;
*nm = xh & c;
}

splits x into *np and *nm so that *np and *nm are the
positive part and the negative part of the non-adjacent
form, respectively. Origin and proof can be found at
http://math.colgate.edu/~integers/a8/a8.pdf .

The nice thing for hardware implementation is that this is
just a (presumably already highly optimzed) adder, an xor
and two separate ands.