org.uncommons.maths.binary
Class BitString

java.lang.Object
  org.uncommons.maths.binary.BitString

All Implemented Interfaces:

Serializable, Cloneable

public final class BitString
extends Object
implements Cloneable, Serializable

Implementation of a fixed-length bit-string. Internally, bits are packed into an array of ints. This implementation makes more efficient use of space than the alternative approach of using an array of booleans.

This class is preferable to BitSet if a fixed number of bits is required.

Author:

Daniel Dyer

See Also:

Serialized Form

Constructor Summary

BitString(int length)
Creates a bit string of the specified length with all bits initially set to zero (off).

BitString(int length, Random rng)
Creates a bit string of the specified length with each bit set randomly (the distribution of bits is uniform so long as the output from the provided RNG is also uniform).

BitString(String value)
Initialises the bit string from a character string of 1s and 0s in big-endian order.

Method Summary

BitString	clone()
int	countSetBits()
int	countUnsetBits()
boolean	equals(Object o)
void	flipBit(int index) Inverts the value of the bit at the specified index.
boolean	getBit(int index) Returns the bit at the specified index.
int	getLength()
int	hashCode() Over-ridden to be consistent with equals(Object).
void	setBit(int index, boolean set) Sets the bit at the specified index.
void	swapSubstring(BitString other, int start, int length) An efficient method for exchanging data between two bit strings.
BigInteger	toNumber() Interprets this bit string as being a binary numeric value and returns the integer that it represents.
String	toString() Creates a textual representation of this bit string in big-endian order (index 0 is the right-most bit).

Methods inherited from class java.lang.Object

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

Constructor Detail

BitString

public BitString(int length)

Creates a bit string of the specified length with all bits initially set to zero (off).

Parameters:

length - The number of bits.

BitString

public BitString(int length,
                 Random rng)

Creates a bit string of the specified length with each bit set randomly (the distribution of bits is uniform so long as the output from the provided RNG is also uniform). Using this constructor is more efficient than creating a bit string and then randomly setting each bit individually.

Parameters:

length - The number of bits.

rng - A source of randomness.

BitString

public BitString(String value)

Initialises the bit string from a character string of 1s and 0s in big-endian order.

Parameters:

value - A character string of ones and zeros.

Method Detail

getLength

public int getLength()

Returns:

The length of this bit string.

getBit

public boolean getBit(int index)

Returns the bit at the specified index.

Parameters:

index - The index of the bit to look-up (0 is the least-significant bit).

Returns:

A boolean indicating whether the bit is set or not.

Throws:

IndexOutOfBoundsException - If the specified index is not a bit position in this bit string.

setBit

public void setBit(int index,
                   boolean set)

Sets the bit at the specified index.

Parameters:

index - The index of the bit to set (0 is the least-significant bit).

set - A boolean indicating whether the bit should be set or not.

Throws:

IndexOutOfBoundsException - If the specified index is not a bit position in this bit string.

flipBit

public void flipBit(int index)

Inverts the value of the bit at the specified index.

Parameters:

index - The bit to flip (0 is the least-significant bit).

Throws:

IndexOutOfBoundsException - If the specified index is not a bit position in this bit string.

countSetBits

public int countSetBits()

Returns:

The number of bits that are 1s rather than 0s.

countUnsetBits

public int countUnsetBits()

Returns:

The number of bits that are 0s rather than 1s.

toNumber

public BigInteger toNumber()

Interprets this bit string as being a binary numeric value and returns the integer that it represents.

Returns:

A BigInteger that contains the numeric value represented by this bit string.

swapSubstring

public void swapSubstring(BitString other,
                          int start,
                          int length)

An efficient method for exchanging data between two bit strings. Both bit strings must be long enough that they contain the full length of the specified substring.

Parameters:

other - The bitstring with which this bitstring should swap bits.

start - The start position for the substrings to be exchanged. All bit indices are big-endian, which means position 0 is the rightmost bit.

length - The number of contiguous bits to swap.

toString

public String toString()

Creates a textual representation of this bit string in big-endian order (index 0 is the right-most bit).

Overrides:

toString in class Object

Returns:

This bit string rendered as a String of 1s and 0s.

clone

public BitString clone()

Overrides:

clone in class Object

Returns:

An identical copy of this bit string.

equals

public boolean equals(Object o)

Overrides:

equals in class Object

Returns:

True if the argument is a BitString instance and both bit strings are the same length with identical bits set/unset.

hashCode

public int hashCode()

Over-ridden to be consistent with equals(Object).

Overrides:

hashCode in class Object