E is odd then zi ← 2 − (E mod 4) E ← E − zi else zi ← 0 E ← E/2 i ← i + 1 return z 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: Input x Output np, nm xh = x >> 1; x3 = x + xh; c = xh ^ x3; np = x3 & c; nm = xh & c; which is used, for example, in . External links Introduction to Canonical Signed Digit Representation References Non-standard positional numeral systems