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.
    • 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.
    • 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).