Algorithm Alley

From DDJ.com September issue

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)

See also:

• http://www.ddj.com/showArticle.jhtml?articleID=184404252 +