content: /*
   * 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;
    }
  
  }
  