Package org.apache.lucene.util
Class BitUtil
 java.lang.Object

 org.apache.lucene.util.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 int
countBits(long[] bits, int numLongs)
Counts all bits set in the provided longs.static int
countBitsUpTo(long[] bits, int numLongs, int bitIndex)
Counts the bits set up to the given bit zerobased index, exclusive.static long
deinterleave(long b)
Extract just the evenbits value as a long from the bitinterleaved valuestatic long
flipFlop(long b)
flip flops odd with even bitsstatic long
interleave(int even, int odd)
Interleaves the first 32 bits of each long value Adapted from: http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMNstatic boolean
isBitSet(long[] bits, int numLongs, int bitIndex)
Returns whether the bit at given zerobased index is set.static int
nextBitSet(long[] bits, int numLongs, int bitIndex)
Returns the index of the next bit set following the given bit zerobased index.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 zerostatic long
nextHighestPowerOfTwo(long v)
returns the next highest power of two, or the current value if it's already a power of two or zerostatic long
pop_andnot(long[] arr1, long[] arr2, int wordOffset, int numWords)
Returns the popcount or cardinality ofA & ~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
previousBitSet(long[] bits, int numLongs, int bitIndex)
Returns the index of the previous bit set preceding the given bit zerobased index.static int
zigZagDecode(int i)
Decode an int previously encoded withzigZagEncode(int)
.static long
zigZagDecode(long l)
Decode a long previously encoded withzigZagEncode(long)
.static int
zigZagEncode(int i)
Same aszigZagEncode(long)
but on integers.static long
zigZagEncode(long l)
Zigzag 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 ofA & ~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 evenbits value as a long from the bitinterleaved value

flipFlop
public static final long flipFlop(long b)
flip flops odd with even bits

zigZagEncode
public static int zigZagEncode(int i)
Same aszigZagEncode(long)
but on integers.

zigZagEncode
public static long zigZagEncode(long l)
Zigzag 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 withzigZagEncode(int)
.

zigZagDecode
public static long zigZagDecode(long l)
Decode a long previously encoded withzigZagEncode(long)
.

isBitSet
public static boolean isBitSet(long[] bits, int numLongs, int bitIndex)
Returns whether the bit at given zerobased index is set.
Example: bitIndex 66 means the third bit on the right of the second long. Parameters:
bits
 The bits stored in an array of long for efficiency.numLongs
 The number of longs inbits
to consider.bitIndex
 The bit zerobased index. It must be greater than or equal to 0, and strictly less thannumLongs * Long.SIZE
.

countBits
public static int countBits(long[] bits, int numLongs)
Counts all bits set in the provided longs. Parameters:
bits
 The bits stored in an array of long for efficiency.numLongs
 The number of longs inbits
to consider.

countBitsUpTo
public static int countBitsUpTo(long[] bits, int numLongs, int bitIndex)
Counts the bits set up to the given bit zerobased index, exclusive.
In other words, how many 1s there are up to the bit at the given index excluded.
Example: bitIndex 66 means the third bit on the right of the second long. Parameters:
bits
 The bits stored in an array of long for efficiency.numLongs
 The number of longs inbits
to consider.bitIndex
 The bit zerobased index, exclusive. It must be greater than or equal to 0, and less than or equal tonumLongs * Long.SIZE
.

nextBitSet
public static int nextBitSet(long[] bits, int numLongs, int bitIndex)
Returns the index of the next bit set following the given bit zerobased index.
For example with bits 100011: the next bit set after index=1 is at index=0; the next bit set after index=0 is at index=1; the next bit set after index=1 is at index=5; there is no next bit set after index=5. Parameters:
bits
 The bits stored in an array of long for efficiency.numLongs
 The number of longs inbits
to consider.bitIndex
 The bit zerobased index. It must be greater than or equal to 1, and strictly less thannumLongs * Long.SIZE
. Returns:
 The zerobased index of the next bit set after the provided
bitIndex
; or 1 if none.

previousBitSet
public static int previousBitSet(long[] bits, int numLongs, int bitIndex)
Returns the index of the previous bit set preceding the given bit zerobased index.
For example with bits 100011: there is no previous bit set before index=0. the previous bit set before index=1 is at index=0; the previous bit set before index=5 is at index=1; the previous bit set before index=64 is at index=5; Parameters:
bits
 The bits stored in an array of long for efficiency.numLongs
 The number of longs inbits
to consider.bitIndex
 The bit zerobased index. It must be greater than or equal to 0, and less than or equal tonumLongs * Long.SIZE
. Returns:
 The zerobased index of the previous bit set before the provided
bitIndex
; or 1 if none.

