Bitvector Class Reference

Vector of bits. More...

#include <bitvector.hh>

Classes
class	Bit
	A wrapper class that acts like a single bit. More...

Public Types
enum	{ wbits = 32 , wshift = 5 , wmask = 31 }
typedef bool(Bitvector::*	unspecified_bool_type) () const
typedef uint32_t	word_type

Public Member Functions
	Bitvector ()
	Construct an empty bitvector.
	Bitvector (int n)
	Construct an all-false bitvector with n elements.
	Bitvector (bool bit)
	Construct a bit-valued length-1 bitvector.
	Bitvector (int n, bool bit)
	Construct a bit-valued length-n bitvector.
	Bitvector (const Bitvector &x)
	Construct a bitvector as a copy of x.
	~Bitvector ()
	Destroy a bitvector.
int	size () const
	Return the number of bits in the bitvector.
Bit	operator[] (int i)
	Return the bit at position i.
bool	operator[] (int i) const
Bit	force_bit (int i)
	Return the bit at position i, extending if necessary.
int	word_size () const
	Return the number of valid data words.
int	max_word () const
	Return the index of the maximum valid data word.
word_type *	words ()
	Return a pointer to this bitvector's data words.
const word_type *	words () const
bool	zero () const
	Test if the bitvector's bits are all false.
	operator unspecified_bool_type () const
	Test if the bitvector contains at least one true bit.
bool	operator! () const
	Test if the bitvector contains no true bits.
Bitvector &	assign (int n, bool bit)
	Set the bitvector to bit-valued length-n.
Bitvector &	operator= (const Bitvector &x)
	Set this bitvector to a copy of x.
void	clear ()
	Set all bits to false.
void	resize (int n)
	Resize the bitvector to n bits.
bool	nonzero_intersection (const Bitvector &x) const
	Test whether this bitvector and x have a common true bit.
Bitvector	operator~ () const
	Return the bitwise negation of this bitvector.
void	flip ()
	Flip all bits in this bitvector.
void	negate ()
	Flip all bits in this bitvector.
Bitvector &	operator&= (const Bitvector &x)
	Modify this bitvector by bitwise and with x.
Bitvector &	operator|= (const Bitvector &x)
	Modify this bitvector by bitwise or with x.
Bitvector &	operator^= (const Bitvector &x)
	Modify this bitvector by bitwise exclusive or with x.
Bitvector &	operator-= (const Bitvector &x)
	Modify this bitvector by bitwise subtraction with x.
void	offset_or (const Bitvector &x, int offset)
	Modify this bitvector by bitwise or with an offset x.
void	or_with_difference (const Bitvector &x, Bitvector &difference)
	Modify this bitvector by bitwise or, returning difference.
void	swap (Bitvector &x)
	Swap the contents of this bitvector and x.
void	set_range (int start, int length, bool value)
bool	range (int start, int length)
int	weight () const
	Return the number of true bits.
int	popcnt () const
	Return the number of true bits.
int	weight_range (int start, int length) const
	Return the number of true bits.
int	clz () const
	Return the number of leading zeroes.
bool	parse (const String &str, int min_val, int max_val, int offset=0)
String	unparse (int read_offset=0, int output_offset=0) const

Static Public Member Functions
static Bitvector	from_mask (unsigned long mask)

Detailed Description

Vector of bits.

The Bitvector class implements a vector of individually addressable bits. It supports bitwise operations such as |= and &= as well as the usual assignment and indexing operations.

Bitvectors are stored as arrays of data words with type word_type, each containing wbits bits. For some purposes it may be faster or easier to manipulate data words directly.

Constructor & Destructor Documentation

Bitvector() [1/5]

Bitvector::Bitvector ( )

inline

Construct an empty bitvector.

Bitvector() [2/5]

Bitvector::Bitvector ( int  n )

inlineexplicit

Construct an all-false bitvector with n elements.

Precondition

n >= 0

Bitvector() [3/5]

Bitvector::Bitvector ( bool  bit )

inlineexplicit

Construct a bit-valued length-1 bitvector.

Bitvector() [4/5]

Bitvector::Bitvector ( int  n, bool  b  )

inline

Construct a bit-valued length-n bitvector.

Precondition

n >= 0

Bitvector() [5/5]

Bitvector::Bitvector ( const Bitvector &  x )

inline

Construct a bitvector as a copy of x.

~Bitvector()

Bitvector::~Bitvector ( )

inline

Destroy a bitvector.

All outstanding Bit objects become invalid.

Member Function Documentation

size()

int Bitvector::size ( ) const

inline

Return the number of bits in the bitvector.

operator[]() [1/2]

Bitvector::Bit Bitvector::operator[] ( int  i )

inline

Return the bit at position i.

Precondition

0 <= i < size()

operator[]() [2/2]

bool Bitvector::operator[] ( int  i ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

force_bit()

Bitvector::Bit Bitvector::force_bit ( int  i )

inline

Return the bit at position i, extending if necessary.

If i >= size(), then the bitvector is resize()d to length i+1, which adds false bits to fill out the vector.

Precondition

0 <= i

Postcondition

i < size()

word_size()

int Bitvector::word_size ( ) const

inline

Return the number of valid data words.

max_word()

int Bitvector::max_word ( ) const

inline

Return the index of the maximum valid data word.

words() [1/2]

Bitvector::word_type * Bitvector::words ( )

inline

Return a pointer to this bitvector's data words.

words() [2/2]

const Bitvector::word_type * Bitvector::words ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

zero()

bool Bitvector::zero

(

)

const

Test if the bitvector's bits are all false.

operator unspecified_bool_type()

Bitvector::operator unspecified_bool_type ( ) const

inline

Test if the bitvector contains at least one true bit.

See also

zero()

operator!()

bool Bitvector::operator! ( ) const

inline

Test if the bitvector contains no true bits.

See also

zero()

assign()

Bitvector & Bitvector::assign	(	int	n,
		bool	bit
	)

Set the bitvector to bit-valued length-n.

Precondition

n >= 0

Returns

*this

operator=()

Bitvector & Bitvector::operator=

(

const Bitvector &

x

)

Set this bitvector to a copy of x.

Returns

*this

clear()

void Bitvector::clear

(

)

Set all bits to false.

resize()

void Bitvector::resize

(

int

n

)

Resize the bitvector to n bits.

Precondition

n >= 0

Any bits added to the bitvector are false.

nonzero_intersection()

bool Bitvector::nonzero_intersection

(

const Bitvector &

x

)

const

Test whether this bitvector and x have a common true bit.

This bitvector and x may have different sizes.

operator~()

Bitvector Bitvector::operator~ ( ) const

inline

Return the bitwise negation of this bitvector.

flip()

void Bitvector::flip

(

)

Flip all bits in this bitvector.

negate()

void Bitvector::negate ( )

inline

Flip all bits in this bitvector.

See also

negate()

operator&=()

Bitvector & Bitvector::operator&=

(

const Bitvector &

x

)

Modify this bitvector by bitwise and with x.

Precondition

x.size() == size()

Returns

*this

operator|=()

Bitvector & Bitvector::operator|=

(

const Bitvector &

x

)

Modify this bitvector by bitwise or with x.

Postcondition

new size() == max(old size(), x.size())

Returns

*this

operator^=()

Bitvector & Bitvector::operator^=

(

const Bitvector &

x

)

Modify this bitvector by bitwise exclusive or with x.

Precondition

x.size() == size()

Returns

*this

operator-=()

Bitvector & Bitvector::operator-= ( const Bitvector &  x )

inline

Modify this bitvector by bitwise subtraction with x.

Precondition

x.size() == size()

Returns

*this

Equivalent to *this &= ~x.

offset_or()

void Bitvector::offset_or	(	const Bitvector &	x,
		int	offset
	)

Modify this bitvector by bitwise or with an offset x.

Parameters

x	bitwise or operand
offset	initial offset

Precondition

offset >= 0 && offset + x.size() <= size()

Logically shifts x to start at position offset, then performs a bitwise or. a.offset_or(b, offset) is equivalent to:

for (int i = 0; i < b.size(); ++i)
    a[offset+i] |= b[i];

or_with_difference()

void Bitvector::or_with_difference	(	const Bitvector &	x,
		Bitvector &	difference
	)

Modify this bitvector by bitwise or, returning difference.

Parameters

	x	bitwise or operand
[out]	difference	set to (x - old *this)

Precondition

x.size() == size()

Postcondition

difference.size() == size()

x | *this == *this

(difference & *this & x) == difference

Same as operator|=, but any newly set bits are returned in difference.

swap()

void Bitvector::swap

(

Bitvector &

x

)

Swap the contents of this bitvector and x.

weight()

int Bitvector::weight ( ) const

inline

Return the number of true bits.

popcnt()

int Bitvector::popcnt ( ) const

inline

Return the number of true bits.

See also

weight

weight_range()

int Bitvector::weight_range ( int  start, int  length  ) const

inline

Return the number of true bits.

clz()

int Bitvector::clz ( ) const

inline

Return the number of leading zeroes.

from_mask()

Bitvector Bitvector::from_mask ( unsigned long  mask )

static

never

---

The documentation for this class was generated from the following files:

• include/click/bitvector.hh
• lib/bitvector.cc