Class BitUtil


  • public final class BitUtil
    extends java.lang.Object
    A variety of high efficiency bit twiddling routines.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static long MAGIC0  
      private static long MAGIC1  
      private static long MAGIC2  
      private static long MAGIC3  
      private static long MAGIC4  
      private static long MAGIC5  
      private static long MAGIC6  
      private static long SHIFT0  
      private static long SHIFT1  
      private static long SHIFT2  
      private static long SHIFT3  
      private static long SHIFT4  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private BitUtil()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static long deinterleave​(long b)
      Extract just the even-bits value as a long from the bit-interleaved value
      static long flipFlop​(long b)
      flip flops odd with even bits
      static long interleave​(int even, int odd)
      Interleaves the first 32 bits of each long value Adapted from: http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
      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 long pop_andnot​(long[] arr1, long[] arr2, int wordOffset, int numWords)
      Returns the popcount or cardinality of A & ~B.
      static long pop_array​(long[] arr, int wordOffset, int numWords)
      Returns the number of set bits in an array of longs.
      static long pop_intersect​(long[] arr1, long[] arr2, int wordOffset, int numWords)
      Returns the popcount or cardinality of the two sets after an intersection.
      static long pop_union​(long[] arr1, long[] arr2, int wordOffset, int numWords)
      Returns the popcount or cardinality of the union of two sets.
      static long pop_xor​(long[] arr1, long[] arr2, int wordOffset, int numWords)
      Returns the popcount or cardinality of A ^ B Neither array is modified.
      static int zigZagDecode​(int i)
      Decode an int previously encoded with zigZagEncode(int).
      static long zigZagDecode​(long l)
      Decode a long previously encoded with zigZagEncode(long).
      static int zigZagEncode​(int i)
      Same as zigZagEncode(long) but on integers.
      static long zigZagEncode​(long l)
      Zig-zag encode the provided long.
      • Methods inherited from class java.lang.Object

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

      • BitUtil

        private BitUtil()
    • Method Detail

      • pop_array

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

        public static long pop_intersect​(long[] arr1,
                                         long[] arr2,
                                         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[] arr1,
                                     long[] arr2,
                                     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[] arr1,
                                      long[] arr2,
                                      int wordOffset,
                                      int numWords)
        Returns the popcount or cardinality of A & ~B. Neither array is modified.
      • pop_xor

        public static long pop_xor​(long[] arr1,
                                   long[] arr2,
                                   int wordOffset,
                                   int numWords)
        Returns the popcount or cardinality of A ^ B Neither array is modified.
      • 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
      • interleave

        public static long interleave​(int even,
                                      int odd)
        Interleaves the first 32 bits of each long value Adapted from: http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
      • deinterleave

        public static long deinterleave​(long b)
        Extract just the even-bits value as a long from the bit-interleaved value
      • flipFlop

        public static long flipFlop​(long b)
        flip flops odd with even bits
      • zigZagEncode

        public static int zigZagEncode​(int i)
        Same as zigZagEncode(long) but on integers.
      • zigZagEncode

        public static long zigZagEncode​(long l)
        Zig-zag encode the provided long. Assuming the input is a signed long whose absolute value can be stored on n bits, the returned value will be an unsigned long that can be stored on n+1 bits.
      • zigZagDecode

        public static int zigZagDecode​(int i)
        Decode an int previously encoded with zigZagEncode(int).
      • zigZagDecode

        public static long zigZagDecode​(long l)
        Decode a long previously encoded with zigZagEncode(long).