Algorithm Alley
by Ron Gutman



Listing One 

public class BitLinear  {

   public static long reverse (long bits) {
        long rl = 0;
        for (int i = 0; i < 64; i++) {
           rl = (rl << 1) + (bits & 1);
           bits = bits >>> 1;
        }
        return rl; 
   }  
   
   public static int count (long bits) {
        int cnt = 0;
        while (bits != 0) {
            cnt += bits & 1;
            bits = bits >>> 1;
        }
        return cnt;
   }
      
}




Listing Two

public class BitRecursive
{
   // reverse leftmost n bits of V
   static long reversen (long V, int n) {
        if (n <= 1)
            return V;
         
        int n2 = n/2;
      
        // reverse rightmost n/2 bits
        long right = reversen( V & ((1L<<n2)-1), n2); 
      
        // reverse lefttmost n/2 bits
        long left =  reversen( V >>> n2, n2); 
      
        // combine in reverse order
        return (right << n2) | left;                  
   }
         
   public static long reverse (long bits) {
        return reversen (bits, 64);
   }
   
}




Listing Three

public class BitLogN {

   public static long reverse (long bits) {
       // >>> fills bits on the left with 0 (no sign extension)
       bits = ((bits&0x00000000ffffffffL) <<  32) | 
              ((bits&0xffffffff00000000L) >>> 32);
       bits = ((bits&0x0000ffff0000ffffL) <<  16) |
              ((bits&0xffff0000ffff0000L) >>> 16);
       bits = ((bits&0x00ff00ff00ff00ffL) <<   8) |
              ((bits&0xff00ff00ff00ff00L) >>>  8);
       bits = ((bits&0x0f0f0f0f0f0f0f0fL) <<   4) | 
              ((bits&0xf0f0f0f0f0f0f0f0L) >>>  4);
       bits = ((bits&0x3333333333333333L) <<   2) |
              ((bits&0xccccccccccccccccL) >>>  2);
       bits = ((bits&0x5555555555555555L) <<   1) |
              ((bits&0xaaaaaaaaaaaaaaaaL) >>>  1);
       return bits; 
   }

   public static int count (long bits) {
       bits = (bits&0x5555555555555555L) +
             ((bits&0xaaaaaaaaaaaaaaaaL) >>>  1);
       bits = (bits&0x3333333333333333L) +
             ((bits&0xccccccccccccccccL) >>>  2);
       bits = (bits&0x0f0f0f0f0f0f0f0fL) +
             ((bits&0xf0f0f0f0f0f0f0f0L) >>>  4);
       bits = (bits&0x00ff00ff00ff00ffL) +
             ((bits&0xff00ff00ff00ff00L) >>>  8);
       bits = (bits&0x0000ffff0000ffffL) +
             ((bits&0xffff0000ffff0000L) >>> 16);
       bits = (bits&0x00000000ffffffffL) +
             ((bits&0xffffffff00000000L) >>> 32);
       return (int) bits;
   }


   public static long mortonKey (int x, int y) {
       /* In C++, the calls to spreadBits could be made in-line    */
       /* to avoid function call overhead.                         */
       /* In C, make the function a macro (admittedly an ugly one) */
       return (spreadBits(x) << 1) | spreadBits(y);
   }


   // For j = 1 to 31, shift bit j j positions to the left 
   static long spreadBits (int i) {
       long bits = i;
      
       // shift bits 16 to 31 16 bits
       bits = (bits & 0x000000000000ffffL) |
             ((bits & 0x00000000ffff0000L) << 16);
       // shift originally odd-numbered bytes 8 bits
       bits = (bits & 0x000000ff000000ffL) |
             ((bits & 0x0000ff000000ff00L) <<  8);
       // shift originally odd-numbered nibbles 4 bits
       bits = (bits & 0x000f000f000f000fL) |
             ((bits & 0x00f000f000f000f0L) <<  4);
       // shift originally odd-numbered bit pairs 2 bits
       bits = (bits & 0x0303030303030303L) |
             ((bits & 0x0c0c0c0c0c0c0c0cL) <<  2);
       // shift originally odd-numbered bit pairs 1 bits
       bits = (bits & 0x1111111111111111L) |
             ((bits & 0x2222222222222222L) <<  1);
      
       return bits;
   }

}



Listing Four

public class BitTable {
    
   short[] table = new short[256];
   
   public BitTable() {
       BitLinear lin = new BitLinear();
       for (int i = 0; i < 256; i++) {
           table[i] = (short) (lin.reverse(i) >>> 56);
      }
   }
   
   public long reverse (long bits) {
       long rl = 0;
       rl =             table[(int)(bits & 255)]; bits = bits >>> 8;
       rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
       rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
       rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
       rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
       rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
       rl = (rl << 8) | table[(int)(bits & 255)]; bits = bits >>> 8;
       rl = (rl << 8) | table[(int)(bits & 255)];           
       return rl; 
   } 

}





Example 1: 

  if n equals 1, return V
  set R = right most n/2 bits of V
  set L = left most  n/2 bits of V
  R = reversen(R,n/2)
  L = reversen(L,n/2)
  set RL = n bit value whose left most n/2 bits
     equals R and whose right most n/2 bits equals L
  return RL





Example 2: 

  if n equals 1, return V
  set R = right most n/2 bits of V
  set L = left most  n/2 bits of V
  return countn(L,n/2) + countn(R,n/2)




