Class BitUtil


  • public final class BitUtil
    extends Object
    A variety of high efficiency bit twiddling routines.
    NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static byte[] nlzTable
      table of number of leading zeros in a byte
      static byte[] ntzTable
      table of number of trailing zeros in a byte
    • 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 nlz​(long x)
      Returns the number of leading zero bits.
      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)  
    • Field Detail

      • ntzTable

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

        public static final byte[] nlzTable
        table of number of leading zeros in a byte
    • Method Detail

      • pop

        public static int pop​(long x)
        Returns the number of bits set in the long
      • 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_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_xor

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

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

        public static int ntz​(int val)
        Returns number of trailing zeros in a 32 bit int 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()
      • nlz

        public static int nlz​(long x)
        Returns the number of leading zero bits.
      • 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