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.

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
    

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