jwutil.math
Class BitString

java.lang.Object
  jwutil.math.BitString

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable

public final class BitString
extends java.lang.Object
implements java.lang.Cloneable, java.io.Serializable

BitString implements a vector of bits much like java.util.BitSet, except that this implementation actually works. Also, BitString has some groovy features which BitSet doesn't; mostly related to efficient iteration over true and false components.

Each component of the BitString has a boolean value. The bits of a BitString are indexed by non-negative integers (that means they are zero-based, of course). Individual indexed bits can be examined, set, or cleared. One BitString may be used to modify the contents of another BitString through logical AND, logical inclusive OR, and logical exclusive OR operations.

By default, all bits in the set initially have the value false.

Every bit set has a current size, which is the number of bits of space currently in use by the bit set. Note that the size is related to the implementation of a bit set, so it may change with implementation. The length of a bit set related to the logical length of a bit set and is defined independently of implementation.

Version:

$Id: BitString.java 2279 2005-05-28 10:24:54Z joewhaley $

Author:

John Whaley

See Also:

Serialized Form

Nested Class Summary

class	BitString.BackwardBitStringIterator Iterator for iterating through a bit string in backward order.
static class	BitString.BitStringIterator Abstract bit string iterator class.
class	BitString.ForwardBitStringIterator Iterator for iterating through a bit string in forward order.

Constructor Summary

BitString(int nbits)
Creates an empty string with the specified size.

Method Summary

boolean	and(BitString set) Logically ANDs this bit set with the specified set of bits.
BitString.BackwardBitStringIterator	backwardsIterator() Returns an iterator that iterates through the bits in backward order.
BitString.BackwardBitStringIterator	backwardsIterator(int i) Returns an iterator that iterates through the bits in backward order, starting at the given index.
static int	bsf(int b) Utility function to return the index of the first (lowest-order) one bit in the given integer.
static int	bsr(int v) Utility function to return the index of the last one bit in the given integer.
void	clear(int bit) Clears a bit.
void	clearAll() Clears all bits.
void	clearUpTo(int bit) Clears all bits up to and including the given bit.
java.lang.Object	clone() Clones the BitString.
boolean	contains(BitString other) Check if this set contains all bits of the given set.
void	copyBits(BitString set) Copies the values of the bits in the specified set into this set.
boolean	equals(java.lang.Object obj) Compares this object against the specified object.
int	firstSet() Returns the first index in the bit string which is set, or -1 if there is no such index.
int	firstSet(int where) Returns the first index greater than where in the bit string which is set, or -1 if there is no such index.
boolean	get(int bit) Gets a bit.
int	hashCode() Returns a hash code value for this bit string whose value depends only on which bits have been set within this BitString.
boolean	intersectionEmpty(BitString other) Check if the intersection of the two sets is empty
boolean	isZero() Returns whether this BitString is all zeroes.
BitString.ForwardBitStringIterator	iterator() Returns an iterator that iterates through the bits in forward order.
int	lastSet() Returns the last index in the bit string which is set, or -1 if there is no such index.
int	lastSet(int where) Returns the last index less than where in the bit string which is set, or -1 if there is no such index.
int	length() Returns the "logical size" of this BitString: the index of the highest set bit in the BitString plus one.
boolean	minus(BitString set) Logically subtracts this bit set with the specified set of bits.
int	numberOfOnes() Returns the number of ones in this BitString.
int	numberOfOnes(int where) Returns the number of ones in this BitString up to a given index.
boolean	or_upTo(BitString set, int bit) Logically ORs this bit set with the specified set of bits.
boolean	or(BitString set) Logically ORs this bit set with the specified set of bits.
static byte	popcount(int b) Utility function to return the number of 1 bits in the given integer value.
static byte	popcount(long b) Utility function to return the number of 1 bits in the given long value.
void	set(int bit) Sets a bit.
void	setAll() Sets all bits.
void	setUpTo(int bit) Sets all bits up to and including the given bit.
void	shl(int amt) Performs a left-shift operation.
void	shr(int amt) Performs a right-shift operation.
int	size() Returns the number of bits of space actually in use by this BitString to represent bit values.
java.lang.String	toString() Converts the BitString to a String.
boolean	xor(BitString set) Logically XORs this bit set with the specified set of bits.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

BitString

public BitString(int nbits)

Creates an empty string with the specified size.

Parameters:

nbits - the size of the string

Method Detail

firstSet

public int firstSet()

Returns the first index in the bit string which is set, or -1 if there is no such index.

firstSet

public int firstSet(int where)

Returns the first index greater than where in the bit string which is set, or -1 if there is no such index.

Parameters:

where - the starting point for the search. May be negative.

popcount

public static final byte popcount(int b)

Utility function to return the number of 1 bits in the given integer value.

Parameters:

b - value to check

Returns:

byte number of one bits

popcount

public static final byte popcount(long b)

Utility function to return the number of 1 bits in the given long value.

Parameters:

b - value to check

Returns:

byte number of one bits

bsf

public static final int bsf(int b)

Utility function to return the index of the first (lowest-order) one bit in the given integer. Returns zero if the given number is zero.

Parameters:

b - value to check

Returns:

byte index of first one bit, or zero if the number is zero

bsr

public static final int bsr(int v)

Utility function to return the index of the last one bit in the given integer. Returns zero if the given number is zero.

Parameters:

v - value to check

Returns:

byte index of first one bit, or zero if the number is zero

lastSet

public int lastSet(int where)

Returns the last index less than where in the bit string which is set, or -1 if there is no such index.

Parameters:

where - the starting point for the search.

lastSet

public int lastSet()

Returns the last index in the bit string which is set, or -1 if there is no such index.

setAll

public void setAll()

Sets all bits.

setUpTo

public void setUpTo(int bit)

Sets all bits up to and including the given bit.

Parameters:

bit - the bit to be set up to (zero-based)

set

public void set(int bit)

Sets a bit.

Parameters:

bit - the bit to be set (zero-based)

clearAll

public void clearAll()

Clears all bits.

clearUpTo

public void clearUpTo(int bit)

Clears all bits up to and including the given bit.

Parameters:

bit - the bit to be set up to (zero-based)

clear

public void clear(int bit)

Clears a bit.

Parameters:

bit - the bit to be cleared (zero-based)

get

public boolean get(int bit)

Gets a bit.

Parameters:

bit - the bit to be gotten (zero-based)

and

public boolean and(BitString set)

Logically ANDs this bit set with the specified set of bits. Returns true if this was modified in response to the operation.

Parameters:

set - the bit set to be ANDed with

or

public boolean or(BitString set)

Logically ORs this bit set with the specified set of bits. Returns true if this was modified in response to the operation.

Parameters:

set - the bit set to be ORed with

or_upTo

public boolean or_upTo(BitString set,
                       int bit)

Logically ORs this bit set with the specified set of bits. Returns true if this was modified in response to the operation.

Parameters:

set - the bit set to be ORed with

xor

public boolean xor(BitString set)

Logically XORs this bit set with the specified set of bits. Returns true if this was modified in response to the operation.

Parameters:

set - the bit set to be XORed with

minus

public boolean minus(BitString set)

Logically subtracts this bit set with the specified set of bits. Returns true if this was modified in response to the operation.

Parameters:

set - the bit set to subtract

intersectionEmpty

public boolean intersectionEmpty(BitString other)

Check if the intersection of the two sets is empty

Parameters:

other - the set to check intersection with

contains

public boolean contains(BitString other)

Check if this set contains all bits of the given set.

Parameters:

other - the set to check containment with

shl

public void shl(int amt)

Performs a left-shift operation.

Parameters:

amt - number of bits to shift, can be negative

shr

public void shr(int amt)

Performs a right-shift operation.

Parameters:

amt - number of bits to shift

copyBits

public void copyBits(BitString set)

Copies the values of the bits in the specified set into this set.

Parameters:

set - the bit set to copy the bits from

hashCode

public int hashCode()

Returns a hash code value for this bit string whose value depends only on which bits have been set within this BitString.

Overrides:

hashCode in class java.lang.Object

length

public int length()

Returns the "logical size" of this BitString: the index of the highest set bit in the BitString plus one. Returns zero if the BitString contains no set bits.

size

public int size()

Returns the number of bits of space actually in use by this BitString to represent bit values. The maximum element in the set is the size - 1st element. The minimum element in the set is the zero'th element.

equals

public boolean equals(java.lang.Object obj)

Compares this object against the specified object.

Overrides:

equals in class java.lang.Object

Parameters:

obj - the object to compare with

Returns:

true if the contents of the bitsets are the same; false otherwise.

isZero

public boolean isZero()

Returns whether this BitString is all zeroes.

Returns:

true if it is all zeroes.

numberOfOnes

public int numberOfOnes()

Returns the number of ones in this BitString.

Returns:

number of bits set.

numberOfOnes

public int numberOfOnes(int where)

Returns the number of ones in this BitString up to a given index.

Returns:

number of bits set.

clone

public java.lang.Object clone()

Clones the BitString.

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

Converts the BitString to a String.

Overrides:

toString in class java.lang.Object

iterator

public BitString.ForwardBitStringIterator iterator()

Returns an iterator that iterates through the bits in forward order.

backwardsIterator

public BitString.BackwardBitStringIterator backwardsIterator()

Returns an iterator that iterates through the bits in backward order.

backwardsIterator

public BitString.BackwardBitStringIterator backwardsIterator(int i)

Returns an iterator that iterates through the bits in backward order, starting at the given index.