src/java/org/apache/cassandra/utils/obs/BitUtil.java - cassandra - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.apache.cassandra.utils.obs;

 /**  A variety of high efficiency bit twiddling routines.
  * @lucene.internal
  */
 final class BitUtil
 {

   /** Returns the number of bits set in the long */
   public static int pop(long x)
   {
   /* Hacker's Delight 32 bit pop function:
    * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
    *
   int pop(unsigned x) {
      x = x - ((x >> 1) & 0x55555555);
      x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
      x = (x + (x >> 4)) & 0x0F0F0F0F;
      x = x + (x >> 8);
      x = x + (x >> 16);
      return x & 0x0000003F;
     }
   ***/

     // 64 bit java version of the C function from above
     x = x - ((x >>> 1) & 0x5555555555555555L);
     x = (x & 0x3333333333333333L) + ((x >>>2 ) & 0x3333333333333333L);
     x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
     x = x + (x >>> 8);
     x = x + (x >>> 16);
     x = x + (x >>> 32);
     return ((int)x) & 0x7F;
   }

   /*** Returns the number of set bits in an array of longs. */
   public static long pop_array(long A[], int wordOffset, int numWords)
   {
     /*
     * Robert Harley and David Seal's bit counting algorithm, as documented
     * in the revisions of Hacker's Delight
     * http://www.hackersdelight.org/revisions.pdf
     * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
     *
     * This function was adapted to Java, and extended to use 64 bit words.
     * if only we had access to wider registers like SSE from java...
     *
     * This function can be transformed to compute the popcount of other functions
     * on bitsets via something like this:
     * sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
     *
     */
     int n = wordOffset+numWords;
     long tot=0, tot8=0;
     long ones=0, twos=0, fours=0;

     int i;
     for (i = wordOffset; i <= n - 8; i+=8)
     {
       /***  C macro from Hacker's Delight
        #define CSA(h,l, a,b,c) \
        {unsigned u = a ^ b; unsigned v = c; \
        h = (a & b) | (u & v); l = u ^ v;}
        ***/

       long twosA,twosB,foursA,foursB,eights;

       // CSA(twosA, ones, ones, A[i], A[i+1])
       {
         long b=A[i], c=A[i+1];
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, A[i+2], A[i+3])
       {
         long b=A[i+2], c=A[i+3];
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursA, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       //CSA(twosA, ones, ones, A[i+4], A[i+5])
       {
         long b=A[i+4], c=A[i+5];
         long u=ones^b;
         twosA=(ones&b)|(u&c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, A[i+6], A[i+7])
       {
         long b=A[i+6], c=A[i+7];
         long u=ones^b;
         twosB=(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursB, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursB=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }

       //CSA(eights, fours, fours, foursA, foursB)
       {
         long u=fours^foursA;
         eights=(fours&foursA)|(u&foursB);
         fours=u^foursB;
       }
       tot8 += pop(eights);
     }

     // handle trailing words in a binary-search manner...
     // derived from the loop above by setting specific elements to 0.
     // the original method in Hackers Delight used a simple for loop:
     //   for (i = i; i < n; i++)      // Add in the last elements
     //  tot = tot + pop(A[i]);

     if (i<=n-4)
     {
       long twosA, twosB, foursA, eights;
       {
         long b=A[i], c=A[i+1];
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       {
         long b=A[i+2], c=A[i+3];
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=4;
     }

     if (i<=n-2)
     {
       long b=A[i], c=A[i+1];
       long u=ones ^ b;
       long twosA=(ones & b)|( u & c);
       ones=u^c;

       long foursA=twos&twosA;
       twos=twos^twosA;

       long eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=2;
     }

     if (i<n)
     {
       tot += pop(A[i]);
     }

     tot += (pop(fours)<<2)
             + (pop(twos)<<1)
             + pop(ones)
             + (tot8<<3);

     return tot;
   }

   /** Returns the popcount or cardinality of the two sets after an intersection.
    * Neither array is modified.
    */
   public static long pop_intersect(long A[], long B[], int wordOffset, int numWords)
   {
     // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
     int n = wordOffset+numWords;
     long tot=0, tot8=0;
     long ones=0, twos=0, fours=0;

     int i;
     for (i = wordOffset; i <= n - 8; i+=8)
     {
       long twosA,twosB,foursA,foursB,eights;

       // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
       {
         long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
       {
         long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursA, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
       {
         long b=(A[i+4] & B[i+4]), c=(A[i+5] & B[i+5]);
         long u=ones^b;
         twosA=(ones&b)|(u&c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
       {
         long b=(A[i+6] & B[i+6]), c=(A[i+7] & B[i+7]);
         long u=ones^b;
         twosB=(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursB, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursB=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }

       //CSA(eights, fours, fours, foursA, foursB)
       {
         long u=fours^foursA;
         eights=(fours&foursA)|(u&foursB);
         fours=u^foursB;
       }
       tot8 += pop(eights);
     }


     if (i<=n-4)
     {
       long twosA, twosB, foursA, eights;
       {
         long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       {
         long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=4;
     }

     if (i<=n-2)
     {
       long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
       long u=ones ^ b;
       long twosA=(ones & b)|( u & c);
       ones=u^c;

       long foursA=twos&twosA;
       twos=twos^twosA;

       long eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=2;
     }

     if (i<n)
     {
       tot += pop((A[i] & B[i]));
     }

     tot += (pop(fours)<<2)
             + (pop(twos)<<1)
             + pop(ones)
             + (tot8<<3);

     return tot;
   }

   /** Returns the popcount or cardinality of the union of two sets.
     * Neither array is modified.
     */
    public static long pop_union(long A[], long B[], int wordOffset, int numWords)
    {
      // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \| B[\1]\)/g'
      int n = wordOffset+numWords;
      long tot=0, tot8=0;
      long ones=0, twos=0, fours=0;

      int i;
      for (i = wordOffset; i <= n - 8; i+=8)
      {
        /***  C macro from Hacker's Delight
         #define CSA(h,l, a,b,c) \
         {unsigned u = a ^ b; unsigned v = c; \
         h = (a & b) | (u & v); l = u ^ v;}
         ***/

        long twosA,twosB,foursA,foursB,eights;

        // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
        {
          long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
          long u=ones ^ b;
          twosA=(ones & b)|( u & c);
          ones=u^c;
        }
        // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
        {
          long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
          long u=ones^b;
          twosB =(ones&b)|(u&c);
          ones=u^c;
        }
        //CSA(foursA, twos, twos, twosA, twosB)
        {
          long u=twos^twosA;
          foursA=(twos&twosA)|(u&twosB);
          twos=u^twosB;
        }
        //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
        {
          long b=(A[i+4] | B[i+4]), c=(A[i+5] | B[i+5]);
          long u=ones^b;
          twosA=(ones&b)|(u&c);
          ones=u^c;
        }
        // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
        {
          long b=(A[i+6] | B[i+6]), c=(A[i+7] | B[i+7]);
          long u=ones^b;
          twosB=(ones&b)|(u&c);
          ones=u^c;
        }
        //CSA(foursB, twos, twos, twosA, twosB)
        {
          long u=twos^twosA;
          foursB=(twos&twosA)|(u&twosB);
          twos=u^twosB;
        }

        //CSA(eights, fours, fours, foursA, foursB)
        {
          long u=fours^foursA;
          eights=(fours&foursA)|(u&foursB);
          fours=u^foursB;
        }
        tot8 += pop(eights);
      }


      if (i<=n-4)
      {
        long twosA, twosB, foursA, eights;
        {
          long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
          long u=ones ^ b;
          twosA=(ones & b)|( u & c);
          ones=u^c;
        }
        {
          long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
          long u=ones^b;
          twosB =(ones&b)|(u&c);
          ones=u^c;
        }
        {
          long u=twos^twosA;
          foursA=(twos&twosA)|(u&twosB);
          twos=u^twosB;
        }
        eights=fours&foursA;
        fours=fours^foursA;

        tot8 += pop(eights);
        i+=4;
      }

      if (i<=n-2)
      {
        long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
        long u=ones ^ b;
        long twosA=(ones & b)|( u & c);
        ones=u^c;

        long foursA=twos&twosA;
        twos=twos^twosA;

        long eights=fours&foursA;
        fours=fours^foursA;

        tot8 += pop(eights);
        i+=2;
      }

      if (i<n)
      {
        tot += pop((A[i] | B[i]));
      }

      tot += (pop(fours)<<2)
              + (pop(twos)<<1)
              + pop(ones)
              + (tot8<<3);

      return tot;
    }

   /** Returns the popcount or cardinality of A & ~B
    * Neither array is modified.
    */
   public static long pop_andnot(long A[], long B[], int wordOffset, int numWords)
   {
     // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
     int n = wordOffset+numWords;
     long tot=0, tot8=0;
     long ones=0, twos=0, fours=0;

     int i;
     for (i = wordOffset; i <= n - 8; i+=8)
     {
       /***  C macro from Hacker's Delight
        #define CSA(h,l, a,b,c) \
        {unsigned u = a ^ b; unsigned v = c; \
        h = (a & b) | (u & v); l = u ^ v;}
        ***/

       long twosA,twosB,foursA,foursB,eights;

       // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
       {
         long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
       {
         long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursA, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
       {
         long b=(A[i+4] & ~B[i+4]), c=(A[i+5] & ~B[i+5]);
         long u=ones^b;
         twosA=(ones&b)|(u&c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
       {
         long b=(A[i+6] & ~B[i+6]), c=(A[i+7] & ~B[i+7]);
         long u=ones^b;
         twosB=(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursB, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursB=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }

       //CSA(eights, fours, fours, foursA, foursB)
       {
         long u=fours^foursA;
         eights=(fours&foursA)|(u&foursB);
         fours=u^foursB;
       }
       tot8 += pop(eights);
     }


     if (i<=n-4)
     {
       long twosA, twosB, foursA, eights;
       {
         long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       {
         long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=4;
     }

     if (i<=n-2)
     {
       long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
       long u=ones ^ b;
       long twosA=(ones & b)|( u & c);
       ones=u^c;

       long foursA=twos&twosA;
       twos=twos^twosA;

       long eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=2;
     }

     if (i<n)
     {
       tot += pop((A[i] & ~B[i]));
     }

     tot += (pop(fours)<<2)
             + (pop(twos)<<1)
             + pop(ones)
             + (tot8<<3);

     return tot;
   }

   public static long pop_xor(long A[], long B[], int wordOffset, int numWords)
   {
     int n = wordOffset+numWords;
     long tot=0, tot8=0;
     long ones=0, twos=0, fours=0;

     int i;
     for (i = wordOffset; i <= n - 8; i+=8)
     {
       /***  C macro from Hacker's Delight
        #define CSA(h,l, a,b,c) \
        {unsigned u = a ^ b; unsigned v = c; \
        h = (a & b) | (u & v); l = u ^ v;}
        ***/

       long twosA,twosB,foursA,foursB,eights;

       // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
       {
         long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
       {
         long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursA, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
       {
         long b=(A[i+4] ^ B[i+4]), c=(A[i+5] ^ B[i+5]);
         long u=ones^b;
         twosA=(ones&b)|(u&c);
         ones=u^c;
       }
       // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
       {
         long b=(A[i+6] ^ B[i+6]), c=(A[i+7] ^ B[i+7]);
         long u=ones^b;
         twosB=(ones&b)|(u&c);
         ones=u^c;
       }
       //CSA(foursB, twos, twos, twosA, twosB)
       {
         long u=twos^twosA;
         foursB=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }

       //CSA(eights, fours, fours, foursA, foursB)
       {
         long u=fours^foursA;
         eights=(fours&foursA)|(u&foursB);
         fours=u^foursB;
       }
       tot8 += pop(eights);
     }


     if (i<=n-4)
     {
       long twosA, twosB, foursA, eights;
       {
         long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
         long u=ones ^ b;
         twosA=(ones & b)|( u & c);
         ones=u^c;
       }
       {
         long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
         long u=ones^b;
         twosB =(ones&b)|(u&c);
         ones=u^c;
       }
       {
         long u=twos^twosA;
         foursA=(twos&twosA)|(u&twosB);
         twos=u^twosB;
       }
       eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=4;
     }

     if (i<=n-2)
     {
       long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
       long u=ones ^ b;
       long twosA=(ones & b)|( u & c);
       ones=u^c;

       long foursA=twos&twosA;
       twos=twos^twosA;

       long eights=fours&foursA;
       fours=fours^foursA;

       tot8 += pop(eights);
       i+=2;
     }

     if (i<n)
     {
       tot += pop((A[i] ^ B[i]));
     }

     tot += (pop(fours)<<2)
             + (pop(twos)<<1)
             + pop(ones)
             + (tot8<<3);

     return tot;
   }

   /* python code to generate ntzTable
   def ntz(val):
     if val==0: return 8
     i=0
     while (val&0x01)==0:
       i = i+1
       val >>= 1
     return i
   print ','.join([ str(ntz(i)) for i in range(256) ])
   ***/
   /** keyspaceName of number of trailing zeros in a byte */
   public static final byte[] ntzTable = {8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};


   /** Returns number of trailing zeros in a 64 bit long value. */
   public static int ntz(long val)
   {
     // A full binary search to determine the low byte was slower than
     // a linear search for nextSetBit().  This is most likely because
     // the implementation of nextSetBit() shifts bits to the right, increasing
     // the probability that the first non-zero byte is in the rhs.
     //
     // This implementation does a single binary search at the top level only
     // so that all other bit shifting can be done on ints instead of longs to
     // remain friendly to 32 bit architectures.  In addition, the case of a
     // non-zero first byte is checked for first because it is the most common
     // in dense bit arrays.

     int lower = (int)val;
     int lowByte = lower & 0xff;
     if (lowByte != 0) return ntzTable[lowByte];

     if (lower!=0)
     {
       lowByte = (lower>>>8) & 0xff;
       if (lowByte != 0) return ntzTable[lowByte] + 8;
       lowByte = (lower>>>16) & 0xff;
       if (lowByte != 0) return ntzTable[lowByte] + 16;
       // no need to mask off low byte for the last byte in the 32 bit word
       // no need to check for zero on the last byte either.
       return ntzTable[lower>>>24] + 24;
     }
     else
     {
       // grab upper 32 bits
       int upper=(int)(val>>32);
       lowByte = upper & 0xff;
       if (lowByte != 0) return ntzTable[lowByte] + 32;
       lowByte = (upper>>>8) & 0xff;
       if (lowByte != 0) return ntzTable[lowByte] + 40;
       lowByte = (upper>>>16) & 0xff;
       if (lowByte != 0) return ntzTable[lowByte] + 48;
       // no need to mask off low byte for the last byte in the 32 bit word
       // no need to check for zero on the last byte either.
       return ntzTable[upper>>>24] + 56;
     }
   }

   /** Returns number of trailing zeros in a 32 bit int value. */
   public static int ntz(int val)
   {
     // This implementation does a single binary search at the top level only.
     // In addition, the case of a non-zero first byte is checked for first
     // because it is the most common in dense bit arrays.

     int lowByte = val & 0xff;
     if (lowByte != 0) return ntzTable[lowByte];
     lowByte = (val>>>8) & 0xff;
     if (lowByte != 0) return ntzTable[lowByte] + 8;
     lowByte = (val>>>16) & 0xff;
     if (lowByte != 0) return ntzTable[lowByte] + 16;
     // no need to mask off low byte for the last byte.
     // no need to check for zero on the last byte either.
     return ntzTable[val>>>24] + 24;
   }

   /** returns 0 based index of first set bit
    * (only works for x!=0)
    * <br/> This is an alternate implementation of ntz()
    */
   public static int ntz2(long x)
   {
    int n = 0;
    int y = (int)x;
    if (y==0) {n+=32; y = (int)(x>>>32); }   // the only 64 bit shift necessary
    if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
    if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
    return (ntzTable[ y & 0xff ]) + n;
   }

   /** returns 0 based index of first set bit
    * <br/> This is an alternate implementation of ntz()
    */
   public static int ntz3(long x)
   {
    // another implementation taken from Hackers Delight, extended to 64 bits
    // and converted to Java.
    // Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
    int n = 1;

    // do the first step as a long, all others as ints.
    int y = (int)x;
    if (y==0) {n+=32; y = (int)(x>>>32); }
    if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
    if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
    if ((y & 0x0000000F) == 0) { n+=4; y>>>=4; }
    if ((y & 0x00000003) == 0) { n+=2; y>>>=2; }
    return n - (y & 1);
   }


   /** returns true if v is a power of two or zero*/
   public static boolean isPowerOfTwo(int v)
   {
     return ((v & (v-1)) == 0);
   }

   /** returns true if v is a power of two or zero*/
   public static boolean isPowerOfTwo(long v)
   {
     return ((v & (v-1)) == 0);
   }

   /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
   public static int nextHighestPowerOfTwo(int v)
   {
     v--;
     v |= v >> 1;
     v |= v >> 2;
     v |= v >> 4;
     v |= v >> 8;
     v |= v >> 16;
     v++;
     return v;
   }

   /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
    public static long nextHighestPowerOfTwo(long v)
    {
     v--;
     v |= v >> 1;
     v |= v >> 2;
     v |= v >> 4;
     v |= v >> 8;
     v |= v >> 16;
     v |= v >> 32;
     v++;
     return v;
   }

 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.apache.cassandra.utils.obs;

	/** A variety of high efficiency bit twiddling routines.
	* @lucene.internal
	*/
	final class BitUtil
	{

	/** Returns the number of bits set in the long */
	public static int pop(long x)
	{
	/* Hacker's Delight 32 bit pop function:
	* http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
	*
	int pop(unsigned x) {
	x = x - ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x + (x >> 4)) & 0x0F0F0F0F;
	x = x + (x >> 8);
	x = x + (x >> 16);
	return x & 0x0000003F;
	}
	***/

	// 64 bit java version of the C function from above
	x = x - ((x >>> 1) & 0x5555555555555555L);
	x = (x & 0x3333333333333333L) + ((x >>>2 ) & 0x3333333333333333L);
	x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
	x = x + (x >>> 8);
	x = x + (x >>> 16);
	x = x + (x >>> 32);
	return ((int)x) & 0x7F;
	}

	/*** Returns the number of set bits in an array of longs. */
	public static long pop_array(long A[], int wordOffset, int numWords)
	{
	/*
	* Robert Harley and David Seal's bit counting algorithm, as documented
	* in the revisions of Hacker's Delight
	* http://www.hackersdelight.org/revisions.pdf
	* http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
	*
	* This function was adapted to Java, and extended to use 64 bit words.
	* if only we had access to wider registers like SSE from java...
	*
	* This function can be transformed to compute the popcount of other functions
	* on bitsets via something like this:
	* sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
	*
	*/
	int n = wordOffset+numWords;
	long tot=0, tot8=0;
	long ones=0, twos=0, fours=0;

	int i;
	for (i = wordOffset; i <= n - 8; i+=8)
	{
	/*** C macro from Hacker's Delight
	#define CSA(h,l, a,b,c) \
	{unsigned u = a ^ b; unsigned v = c; \
	h = (a & b) \| (u & v); l = u ^ v;}
	***/

	long twosA,twosB,foursA,foursB,eights;

	// CSA(twosA, ones, ones, A[i], A[i+1])
	{
	long b=A[i], c=A[i+1];
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, A[i+2], A[i+3])
	{
	long b=A[i+2], c=A[i+3];
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursA, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	//CSA(twosA, ones, ones, A[i+4], A[i+5])
	{
	long b=A[i+4], c=A[i+5];
	long u=ones^b;
	twosA=(ones&b)\|(u&c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, A[i+6], A[i+7])
	{
	long b=A[i+6], c=A[i+7];
	long u=ones^b;
	twosB=(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursB, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursB=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}

	//CSA(eights, fours, fours, foursA, foursB)
	{
	long u=fours^foursA;
	eights=(fours&foursA)\|(u&foursB);
	fours=u^foursB;
	}
	tot8 += pop(eights);
	}

	// handle trailing words in a binary-search manner...
	// derived from the loop above by setting specific elements to 0.
	// the original method in Hackers Delight used a simple for loop:
	// for (i = i; i < n; i++) // Add in the last elements
	// tot = tot + pop(A[i]);

	if (i<=n-4)
	{
	long twosA, twosB, foursA, eights;
	{
	long b=A[i], c=A[i+1];
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	{
	long b=A[i+2], c=A[i+3];
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=4;
	}

	if (i<=n-2)
	{
	long b=A[i], c=A[i+1];
	long u=ones ^ b;
	long twosA=(ones & b)\|( u & c);
	ones=u^c;

	long foursA=twos&twosA;
	twos=twos^twosA;

	long eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=2;
	}

	if (i<n)
	{
	tot += pop(A[i]);
	}

	tot += (pop(fours)<<2)
	+ (pop(twos)<<1)
	+ pop(ones)
	+ (tot8<<3);

	return tot;
	}

	/** Returns the popcount or cardinality of the two sets after an intersection.
	* Neither array is modified.
	*/
	public static long pop_intersect(long A[], long B[], int wordOffset, int numWords)
	{
	// generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
	int n = wordOffset+numWords;
	long tot=0, tot8=0;
	long ones=0, twos=0, fours=0;

	int i;
	for (i = wordOffset; i <= n - 8; i+=8)
	{
	long twosA,twosB,foursA,foursB,eights;

	// CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
	{
	long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
	{
	long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursA, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	//CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
	{
	long b=(A[i+4] & B[i+4]), c=(A[i+5] & B[i+5]);
	long u=ones^b;
	twosA=(ones&b)\|(u&c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
	{
	long b=(A[i+6] & B[i+6]), c=(A[i+7] & B[i+7]);
	long u=ones^b;
	twosB=(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursB, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursB=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}

	//CSA(eights, fours, fours, foursA, foursB)
	{
	long u=fours^foursA;
	eights=(fours&foursA)\|(u&foursB);
	fours=u^foursB;
	}
	tot8 += pop(eights);
	}


	if (i<=n-4)
	{
	long twosA, twosB, foursA, eights;
	{
	long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	{
	long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=4;
	}

	if (i<=n-2)
	{
	long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
	long u=ones ^ b;
	long twosA=(ones & b)\|( u & c);
	ones=u^c;

	long foursA=twos&twosA;
	twos=twos^twosA;

	long eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=2;
	}

	if (i<n)
	{
	tot += pop((A[i] & B[i]));
	}

	tot += (pop(fours)<<2)
	+ (pop(twos)<<1)
	+ pop(ones)
	+ (tot8<<3);

	return tot;
	}

	/** Returns the popcount or cardinality of the union of two sets.
	* Neither array is modified.
	*/
	public static long pop_union(long A[], long B[], int wordOffset, int numWords)
	{
	// generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \\| B[\1]\)/g'
	int n = wordOffset+numWords;
	long tot=0, tot8=0;
	long ones=0, twos=0, fours=0;

	int i;
	for (i = wordOffset; i <= n - 8; i+=8)
	{
	/*** C macro from Hacker's Delight
	#define CSA(h,l, a,b,c) \
	{unsigned u = a ^ b; unsigned v = c; \
	h = (a & b) \| (u & v); l = u ^ v;}
	***/

	long twosA,twosB,foursA,foursB,eights;

	// CSA(twosA, ones, ones, (A[i] \| B[i]), (A[i+1] \| B[i+1]))
	{
	long b=(A[i] \| B[i]), c=(A[i+1] \| B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+2] \| B[i+2]), (A[i+3] \| B[i+3]))
	{
	long b=(A[i+2] \| B[i+2]), c=(A[i+3] \| B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursA, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	//CSA(twosA, ones, ones, (A[i+4] \| B[i+4]), (A[i+5] \| B[i+5]))
	{
	long b=(A[i+4] \| B[i+4]), c=(A[i+5] \| B[i+5]);
	long u=ones^b;
	twosA=(ones&b)\|(u&c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+6] \| B[i+6]), (A[i+7] \| B[i+7]))
	{
	long b=(A[i+6] \| B[i+6]), c=(A[i+7] \| B[i+7]);
	long u=ones^b;
	twosB=(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursB, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursB=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}

	//CSA(eights, fours, fours, foursA, foursB)
	{
	long u=fours^foursA;
	eights=(fours&foursA)\|(u&foursB);
	fours=u^foursB;
	}
	tot8 += pop(eights);
	}


	if (i<=n-4)
	{
	long twosA, twosB, foursA, eights;
	{
	long b=(A[i] \| B[i]), c=(A[i+1] \| B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	{
	long b=(A[i+2] \| B[i+2]), c=(A[i+3] \| B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=4;
	}

	if (i<=n-2)
	{
	long b=(A[i] \| B[i]), c=(A[i+1] \| B[i+1]);
	long u=ones ^ b;
	long twosA=(ones & b)\|( u & c);
	ones=u^c;

	long foursA=twos&twosA;
	twos=twos^twosA;

	long eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=2;
	}

	if (i<n)
	{
	tot += pop((A[i] \| B[i]));
	}

	tot += (pop(fours)<<2)
	+ (pop(twos)<<1)
	+ pop(ones)
	+ (tot8<<3);

	return tot;
	}

	/** Returns the popcount or cardinality of A & ~B
	* Neither array is modified.
	*/
	public static long pop_andnot(long A[], long B[], int wordOffset, int numWords)
	{
	// generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
	int n = wordOffset+numWords;
	long tot=0, tot8=0;
	long ones=0, twos=0, fours=0;

	int i;
	for (i = wordOffset; i <= n - 8; i+=8)
	{
	/*** C macro from Hacker's Delight
	#define CSA(h,l, a,b,c) \
	{unsigned u = a ^ b; unsigned v = c; \
	h = (a & b) \| (u & v); l = u ^ v;}
	***/

	long twosA,twosB,foursA,foursB,eights;

	// CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
	{
	long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
	{
	long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursA, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	//CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
	{
	long b=(A[i+4] & ~B[i+4]), c=(A[i+5] & ~B[i+5]);
	long u=ones^b;
	twosA=(ones&b)\|(u&c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
	{
	long b=(A[i+6] & ~B[i+6]), c=(A[i+7] & ~B[i+7]);
	long u=ones^b;
	twosB=(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursB, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursB=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}

	//CSA(eights, fours, fours, foursA, foursB)
	{
	long u=fours^foursA;
	eights=(fours&foursA)\|(u&foursB);
	fours=u^foursB;
	}
	tot8 += pop(eights);
	}


	if (i<=n-4)
	{
	long twosA, twosB, foursA, eights;
	{
	long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	{
	long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=4;
	}

	if (i<=n-2)
	{
	long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
	long u=ones ^ b;
	long twosA=(ones & b)\|( u & c);
	ones=u^c;

	long foursA=twos&twosA;
	twos=twos^twosA;

	long eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=2;
	}

	if (i<n)
	{
	tot += pop((A[i] & ~B[i]));
	}

	tot += (pop(fours)<<2)
	+ (pop(twos)<<1)
	+ pop(ones)
	+ (tot8<<3);

	return tot;
	}

	public static long pop_xor(long A[], long B[], int wordOffset, int numWords)
	{
	int n = wordOffset+numWords;
	long tot=0, tot8=0;
	long ones=0, twos=0, fours=0;

	int i;
	for (i = wordOffset; i <= n - 8; i+=8)
	{
	/*** C macro from Hacker's Delight
	#define CSA(h,l, a,b,c) \
	{unsigned u = a ^ b; unsigned v = c; \
	h = (a & b) \| (u & v); l = u ^ v;}
	***/

	long twosA,twosB,foursA,foursB,eights;

	// CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
	{
	long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
	{
	long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursA, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	//CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
	{
	long b=(A[i+4] ^ B[i+4]), c=(A[i+5] ^ B[i+5]);
	long u=ones^b;
	twosA=(ones&b)\|(u&c);
	ones=u^c;
	}
	// CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
	{
	long b=(A[i+6] ^ B[i+6]), c=(A[i+7] ^ B[i+7]);
	long u=ones^b;
	twosB=(ones&b)\|(u&c);
	ones=u^c;
	}
	//CSA(foursB, twos, twos, twosA, twosB)
	{
	long u=twos^twosA;
	foursB=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}

	//CSA(eights, fours, fours, foursA, foursB)
	{
	long u=fours^foursA;
	eights=(fours&foursA)\|(u&foursB);
	fours=u^foursB;
	}
	tot8 += pop(eights);
	}


	if (i<=n-4)
	{
	long twosA, twosB, foursA, eights;
	{
	long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
	long u=ones ^ b;
	twosA=(ones & b)\|( u & c);
	ones=u^c;
	}
	{
	long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
	long u=ones^b;
	twosB =(ones&b)\|(u&c);
	ones=u^c;
	}
	{
	long u=twos^twosA;
	foursA=(twos&twosA)\|(u&twosB);
	twos=u^twosB;
	}
	eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=4;
	}

	if (i<=n-2)
	{
	long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
	long u=ones ^ b;
	long twosA=(ones & b)\|( u & c);
	ones=u^c;

	long foursA=twos&twosA;
	twos=twos^twosA;

	long eights=fours&foursA;
	fours=fours^foursA;

	tot8 += pop(eights);
	i+=2;
	}

	if (i<n)
	{
	tot += pop((A[i] ^ B[i]));
	}

	tot += (pop(fours)<<2)
	+ (pop(twos)<<1)
	+ pop(ones)
	+ (tot8<<3);

	return tot;
	}

	/* python code to generate ntzTable
	def ntz(val):
	if val==0: return 8
	i=0
	while (val&0x01)==0:
	i = i+1
	val >>= 1
	return i
	print ','.join([ str(ntz(i)) for i in range(256) ])
	***/
	/** keyspaceName of number of trailing zeros in a byte */
	public static final byte[] ntzTable = {8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};


	/** Returns number of trailing zeros in a 64 bit long value. */
	public static int ntz(long val)
	{
	// A full binary search to determine the low byte was slower than
	// a linear search for nextSetBit(). This is most likely because
	// the implementation of nextSetBit() shifts bits to the right, increasing
	// the probability that the first non-zero byte is in the rhs.
	//
	// This implementation does a single binary search at the top level only
	// so that all other bit shifting can be done on ints instead of longs to
	// remain friendly to 32 bit architectures. In addition, the case of a
	// non-zero first byte is checked for first because it is the most common
	// in dense bit arrays.

	int lower = (int)val;
	int lowByte = lower & 0xff;
	if (lowByte != 0) return ntzTable[lowByte];

	if (lower!=0)
	{
	lowByte = (lower>>>8) & 0xff;
	if (lowByte != 0) return ntzTable[lowByte] + 8;
	lowByte = (lower>>>16) & 0xff;
	if (lowByte != 0) return ntzTable[lowByte] + 16;
	// no need to mask off low byte for the last byte in the 32 bit word
	// no need to check for zero on the last byte either.
	return ntzTable[lower>>>24] + 24;
	}
	else
	{
	// grab upper 32 bits
	int upper=(int)(val>>32);
	lowByte = upper & 0xff;
	if (lowByte != 0) return ntzTable[lowByte] + 32;
	lowByte = (upper>>>8) & 0xff;
	if (lowByte != 0) return ntzTable[lowByte] + 40;
	lowByte = (upper>>>16) & 0xff;
	if (lowByte != 0) return ntzTable[lowByte] + 48;
	// no need to mask off low byte for the last byte in the 32 bit word
	// no need to check for zero on the last byte either.
	return ntzTable[upper>>>24] + 56;
	}
	}

	/** Returns number of trailing zeros in a 32 bit int value. */
	public static int ntz(int val)
	{
	// This implementation does a single binary search at the top level only.
	// In addition, the case of a non-zero first byte is checked for first
	// because it is the most common in dense bit arrays.

	int lowByte = val & 0xff;
	if (lowByte != 0) return ntzTable[lowByte];
	lowByte = (val>>>8) & 0xff;
	if (lowByte != 0) return ntzTable[lowByte] + 8;
	lowByte = (val>>>16) & 0xff;
	if (lowByte != 0) return ntzTable[lowByte] + 16;
	// no need to mask off low byte for the last byte.
	// no need to check for zero on the last byte either.
	return ntzTable[val>>>24] + 24;
	}

	/** returns 0 based index of first set bit
	* (only works for x!=0)
	* <br/> This is an alternate implementation of ntz()
	*/
	public static int ntz2(long x)
	{
	int n = 0;
	int y = (int)x;
	if (y==0) {n+=32; y = (int)(x>>>32); } // the only 64 bit shift necessary
	if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
	if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
	return (ntzTable[ y & 0xff ]) + n;
	}

	/** returns 0 based index of first set bit
	* <br/> This is an alternate implementation of ntz()
	*/
	public static int ntz3(long x)
	{
	// another implementation taken from Hackers Delight, extended to 64 bits
	// and converted to Java.
	// Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
	int n = 1;

	// do the first step as a long, all others as ints.
	int y = (int)x;
	if (y==0) {n+=32; y = (int)(x>>>32); }
	if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
	if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
	if ((y & 0x0000000F) == 0) { n+=4; y>>>=4; }
	if ((y & 0x00000003) == 0) { n+=2; y>>>=2; }
	return n - (y & 1);
	}


	/** returns true if v is a power of two or zero*/
	public static boolean isPowerOfTwo(int v)
	{
	return ((v & (v-1)) == 0);
	}

	/** returns true if v is a power of two or zero*/
	public static boolean isPowerOfTwo(long v)
	{
	return ((v & (v-1)) == 0);
	}

	/** returns the next highest power of two, or the current value if it's already a power of two or zero*/
	public static int nextHighestPowerOfTwo(int v)
	{
	v--;
	v \|= v >> 1;
	v \|= v >> 2;
	v \|= v >> 4;
	v \|= v >> 8;
	v \|= v >> 16;
	v++;
	return v;
	}

	/** returns the next highest power of two, or the current value if it's already a power of two or zero*/
	public static long nextHighestPowerOfTwo(long v)
	{
	v--;
	v \|= v >> 1;
	v \|= v >> 2;
	v \|= v >> 4;
	v \|= v >> 8;
	v \|= v >> 16;
	v \|= v >> 32;
	v++;
	return v;
	}

	}