12-1. Base -2

By using −2 as the base, both positive and negative integers can be expressed without an explicit sign or other irregularity such as having a negative weight for the most significant bit (Knu3). The digits used are 0 and 1, as in base +2; that is, the value represented by a string of 1’s and 0’s is understood to be

From this, it can be seen that a procedure for finding the base −2, or “negabinary,” representation of an integer is to successively divide the number by −2, recording the remainders. The division must be such that it always gives a remainder of 0 or 1 (the digits to be used); that is, it must be modulus division. As ...

Get Hacker's Delight now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.