Class BitUtil


  • public class BitUtil
    extends java.lang.Object
    A variety of high efficiency bit twiddling routines.
    Version:
    $Id: BitUtil.java,v 1.1 2011/03/10 12:18:16 pcingola Exp $
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static byte[] ntzTable
      table of number of trailing zeros in a byte
    • Constructor Summary

      Constructors 
      Constructor Description
      BitUtil()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static boolean isPowerOfTwo​(int v)
      returns true if v is a power of two or zero
      static boolean isPowerOfTwo​(long v)
      returns true if v is a power of two or zero
      static int nextHighestPowerOfTwo​(int v)
      returns the next highest power of two, or the current value if it's already a power of two or zero
      static long nextHighestPowerOfTwo​(long v)
      returns the next highest power of two, or the current value if it's already a power of two or zero
      static int ntz​(int val)
      Returns number of trailing zeros in a 32 bit int value.
      static int ntz​(long val)
      Returns number of trailing zeros in a 64 bit long value.
      static int ntz2​(long x)
      returns 0 based index of first set bit (only works for x!=0)
      This is an alternate implementation of ntz()
      static int ntz3​(long x)
      returns 0 based index of first set bit
      This is an alternate implementation of ntz()
      static int pop​(long x)
      Returns the number of bits set in the long
      static long pop_andnot​(long[] A, long[] B, int wordOffset, int numWords)
      Returns the popcount or cardinality of A & ~B Neither array is modified.
      static long pop_array​(long[] A, int wordOffset, int numWords)
      Returns the number of set bits in an array of longs.
      static long pop_intersect​(long[] A, long[] B, int wordOffset, int numWords)
      Returns the popcount or cardinality of the two sets after an intersection.
      static long pop_union​(long[] A, long[] B, int wordOffset, int numWords)
      Returns the popcount or cardinality of the union of two sets.
      static long pop_xor​(long[] A, long[] B, int wordOffset, int numWords)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • ntzTable

        public static final byte[] ntzTable
        table of number of trailing zeros in a byte
    • Constructor Detail

      • BitUtil

        public BitUtil()
    • Method Detail

      • isPowerOfTwo

        public static boolean isPowerOfTwo​(int v)
        returns true if v is a power of two or zero
      • isPowerOfTwo

        public static boolean isPowerOfTwo​(long v)
        returns true if v is a power of two or zero
      • nextHighestPowerOfTwo

        public static int nextHighestPowerOfTwo​(int v)
        returns the next highest power of two, or the current value if it's already a power of two or zero
      • nextHighestPowerOfTwo

        public static long nextHighestPowerOfTwo​(long v)
        returns the next highest power of two, or the current value if it's already a power of two or zero
      • ntz

        public static int ntz​(int val)
        Returns number of trailing zeros in a 32 bit int value.
      • ntz

        public static int ntz​(long val)
        Returns number of trailing zeros in a 64 bit long value.
      • ntz2

        public static int ntz2​(long x)
        returns 0 based index of first set bit (only works for x!=0)
        This is an alternate implementation of ntz()
      • ntz3

        public static int ntz3​(long x)
        returns 0 based index of first set bit
        This is an alternate implementation of ntz()
      • pop

        public static int pop​(long x)
        Returns the number of bits set in the long
      • pop_andnot

        public static long pop_andnot​(long[] A,
                                      long[] B,
                                      int wordOffset,
                                      int numWords)
        Returns the popcount or cardinality of A & ~B Neither array is modified.
      • pop_array

        public static long pop_array​(long[] A,
                                     int wordOffset,
                                     int numWords)
        Returns the number of set bits in an array of longs.
      • pop_intersect

        public static long pop_intersect​(long[] A,
                                         long[] B,
                                         int wordOffset,
                                         int numWords)
        Returns the popcount or cardinality of the two sets after an intersection. Neither array is modified.
      • pop_union

        public static long pop_union​(long[] A,
                                     long[] B,
                                     int wordOffset,
                                     int numWords)
        Returns the popcount or cardinality of the union of two sets. Neither array is modified.
      • pop_xor

        public static long pop_xor​(long[] A,
                                   long[] B,
                                   int wordOffset,
                                   int numWords)