Notes on Henry Warren's book "Hacker's Delight"

2-1 Manipulating rightmost bits, pages 11-12.

The following table generalizes some operations decribed in that section.

Value of one or more bits Inversion of smallest bit Inversion of trailing bits Bitmask of smallest bit Bitmask of traling bits
0 x | (x + 1) x | (x - 1) ~x & (x + 1) ~x & (x - 1)
1 x & (x - 1) x & (x + 1) x & (~x + 1) x & (~x - 1)

Negation operation expressed as logical NOT and arithmetic ADD:

        
        -x = ~x + 1 = ~(x - 1) (we assume twos complement representation of negative numbers)
        

Logical NOT of a sum can be rewritten as a difference between the inverted first term and the second term:

        
        ~(x + a) = ~x - a

        Proof: 
        Inversion is defined as: ~x = 2^n - 1 - x, where n - word size. Then 
        substitute inversion with that expression:
        ~(x + a) = ~x - a
        2^n - 1 - (x + a) = 2^n - 1 - x - a
        -x - a = -x - a
        1 = 1
        

Gosper algorithm, page 14.

Gosper algorithm produces the next higher number with the same number of bits. The algorithm requires a division which is not available in some instruction sets. Fortunately, the division can be replaced by right shifts since the divisor is always a power of two. Here is the modified C function:

        unsigned snoob(unsigned x)
        {
          unsigned smallest;
          unsigned ripple;
          unsigned ones;

          // generate higher bits of result by adding the smallest 1-bit to x
          smallest = x & -x;
          ripple = x + smallest;

          // the remaining bits should be a consecutive string of 1-bits
          // starting from bit 0      
          ones = x ^ ripple;         // bitmask of remaining bits plus two extra bits           
          while((ones & 1) == 0)     // shift the bitmask to bit 0
            ones >>= 1;              //
          ones >>= 2;                // remove the extra 2 bits
          return ripple | ones;      // merge higher and lower bits and return
        }
        

Gray Code, page 235.

The reflective binary Gray Code can be generalized to any natural integer radix (except base 1). For example, in base 10, first 100 encoded numbers are:

     0    19    20    39    40    59    60    79    80    99
     1    18    21    38    41    58    61    78    81    98
     2    17    22    37    42    57    62    77    82    97
     3    16    23    36    43    56    63    76    83    96
     4    15    24    35    44    55    64    75    84    95
     5    14    25    34    45    54    65    74    85    94
     6    13    26    33    46    53    66    73    86    93
     7    12    27    32    47    52    67    72    87    92
     8    11    28    31    48    51    68    71    88    91
     9    10    29    30    49    50    69    70    89    90
    
(read the table by columns)

Encoding a number to Gray Code can be done as follows:

    G(i) = B(i), if B(i+1) is an even digit 
    G(i) = n - 1 - B(i), if B(i+1) is odd 

    i - digit index (1..m-1, 1 - least significant, m - most significant)
    n - the radix base (2, 3, 4, ...) 
    B - original number in base n
    G - Gray Code number in base n
    

Decoding a Gray Code number:

    First, initialize the result:
    
    B = G
    
    Then, scan all the digits starting from the most significant one (i = m-1, m-2, ... 1):
     
    B(i) = B(i), if B(i+1) is even 
    B(i) = n - 1 - B(i), if B(i+1) is odd    
    

The following MATLAB programs can be used to verify the algorithms:

generateGrayCode.m - generate Gray Code in any base using reflection
convertToGrayCode.m - encoding
convertFromGrayCode.m - decoding



Last updated: 7-Mar-2004