BitString

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> [ Util overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

SOURCE |

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

Util
Class BitString

java.lang.Object
  Util.BitString

All Implemented Interfaces:: java.lang.Cloneable, java.io.Serializable

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,v 1.12 2003/06/16 17:10:59 joewhaley Exp $

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.

Field Summary

private int[] bits


private static int BITS_PER_UNIT


private static byte[] bytemsb
          Highest bit set in a byte.

private static int MASK


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.

private static int[] bit_reverse(int serSize, int[] newSer)


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.

private static void shld(int[] bits, int i1, int i2, int amt)


void shr(int amt)
          Performs a right-shift operation.

private static void shrd(int[] bits, int i1, int i2, int amt)


int size()
          Returns the number of bits of space actually in use by this BitString to represent bit values.

private static int subscript(int bitIndex)
          Convert bitIndex to a subscript into the bits[] array.

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

Field Detail

BITS_PER_UNIT

private static final int BITS_PER_UNIT

See Also:: Constant Field Values

MASK

private static final int MASK

See Also:: Constant Field Values

bits

private int[] bits

bytemsb

private static final byte[] bytemsb

Highest bit set in a byte.

Constructor Detail

BitString

public BitString(int nbits)

Creates an empty string with the specified size.

Method Detail

subscript

private static int subscript(int bitIndex)

Convert bitIndex to a subscript into the bits[] array.

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.

popcount

public static final byte popcount(int b)

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

popcount

public static final byte popcount(long b)

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

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.

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.

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.

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.

set

public void set(int bit)

Sets a bit.

clearAll

public void clearAll()

Clears all bits.

clearUpTo

public void clearUpTo(int bit)

Clears all bits up to and including the given bit.

clear

public void clear(int bit)

Clears a bit.

get

public boolean get(int bit)

Gets a bit.

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.

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.

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.

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.

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.

intersectionEmpty

public boolean intersectionEmpty(BitString other)

Check if the intersection of the two sets is empty

contains

public boolean contains(BitString other)

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

shld

private static void shld(int[] bits,
                         int i1,
                         int i2,
                         int amt)

shl

public void shl(int amt)

Performs a left-shift operation.

shrd

private static void shrd(int[] bits,
                         int i1,
                         int i2,
                         int amt)

shr

public void shr(int amt)

Performs a right-shift operation.

copyBits

public void copyBits(BitString set)

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

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.

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.

isZero

public boolean isZero()

Returns whether this BitString is all zeroes.

numberOfOnes

public int numberOfOnes()

Returns the number of ones in this BitString.

numberOfOnes

public int numberOfOnes(int where)

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

clone

public java.lang.Object clone()

Clones the BitString.

toString

public java.lang.String toString()

Converts the BitString to a String.

bit_reverse

private static int[] bit_reverse(int serSize,
                                 int[] newSer)

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.

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> [ Util overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

SOURCE |

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

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.

Field Summary
`private int[]`	`bits`
`private static int`	`BITS_PER_UNIT`
`private static byte[]`	`bytemsb` Highest bit set in a byte.
`private static int`	`MASK`

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.
`private static int[]`	`bit_reverse(int serSize, int[] newSer)`
`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.
`private static void`	`shld(int[] bits, int i1, int i2, int amt)`
`void`	`shr(int amt)` Performs a right-shift operation.
`private static void`	`shrd(int[] bits, int i1, int i2, int amt)`
`int`	`size()` Returns the number of bits of space actually in use by this `BitString` to represent bit values.
`private static int`	`subscript(int bitIndex)` Convert bitIndex to a subscript into the bits[] array.
`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.

Util Class BitString

BITS_PER_UNIT

MASK

bits

bytemsb

BitString

subscript

firstSet

firstSet

popcount

popcount

bsf

bsr

lastSet

lastSet

setAll

setUpTo

set

clearAll

clearUpTo

clear

get

and

or

or_upTo

xor

minus

intersectionEmpty

contains

shld

shl

shrd

shr

copyBits

hashCode

length

size

equals

isZero

numberOfOnes

numberOfOnes

clone

toString

bit_reverse

iterator

backwardsIterator

backwardsIterator

Util
Class BitString