Bitvector Class Reference

#include <genesis/utils/math/bitvector.hpp>

Detailed Description

Definition at line 50 of file bitvector.hpp.

Public Member Functions
	Bitvector ()=default
	Default constructor. Creates an empty Bitvector of size 0. More...
	Bitvector (Bitvector &&)=default
	Bitvector (Bitvector const &)=default
template<class It >
	Bitvector (It first, It last)
	Construct a Bitvector using a range of bools. More...
	Bitvector (size_t size, Bitvector const &other)
	Create a Bitvector of a given size, and copy the content of another Bitvector. More...
	Bitvector (size_t size, bool initial_value=false)
	Constructor that takes a size and an optional bool value to initialize the Bitvector, false by default. More...
	Bitvector (size_t size, std::initializer_list< size_t > list)
	Constructor that takes a size and a list of values (positions) to be set to true. More...
	Bitvector (std::string const &values)
	Constructor that takes a std::string of 0s and 1s to build the Bitvector. More...
	~Bitvector ()=default
bool	any_set () const
	Return if any bits are set at all. More...
size_t	count () const
	Count the number of set bits in the Bitvector, that is, its Hamming weight, or population count (popcnt). More...
size_t	count (size_t first, size_t last) const
	Count the number of set bits between a range of indices in the Bitvector, that is, its Hamming weight, or population count (popcnt), for that range. More...
std::vector< IntType > const &	data () const
std::string	dump () const
std::string	dump_int (IntType x) const
bool	empty () const
	Return whether the Bitvector is empty, that is, has size() == 0. More...
size_t	find_next_set (size_t start) const
	Return the index of the next position in the Bitvector that is set. More...
void	flip (size_t index)
	Flip (negate) the value of a single bit, with boundary check. More...
bool	get (size_t index) const
	Return the value of a single bit, with boundary check. More...
size_t	hash () const
	Return an std::hash value for the Bitvector. More...
void	negate ()
	Flip all bits. More...
void	normalize ()
	Bring the Bitvector in a normalized form, where the first bit is always zero. More...
bool	operator!= (const Bitvector &other) const
Bitvector &	operator&= (Bitvector const &rhs)
Bitvector &	operator= (Bitvector &&)=default
Bitvector &	operator= (Bitvector const &)=default
bool	operator== (const Bitvector &other) const
bool	operator[] (size_t index) const
	Return the value of a single bit, without boundary check. More...
Bitvector &	operator^= (Bitvector const &rhs)
Bitvector &	operator|= (Bitvector const &rhs)
Bitvector	operator~ () const
void	set (size_t first, size_t last, bool value=true)
	Set the value of a contiguous range of bits in the Bitvector. More...
void	set (size_t index)
	Set the value of a single bit to true, with boundary check. More...
void	set (size_t index, bool value)
	Set the value of a single bit to a given bool value, with boundary check. More...
void	set_all (const bool value=false)
	Set all the bits to a specified value. More...
size_t	size () const
	Return the size (number of bits) of this Bitvector. More...
void	toggle (size_t index)
	Alias for flip(), see there for details. More...
void	unset (size_t index)
	Set the value of a single bit to false, with boundary check. More...
IntType	x_hash () const
	Return a hash value of type IntType that is quicker to calculate than hash(). More...

Public Types
using	IntType = uint64_t

Static Public Attributes
static const size_t	IntSize = sizeof(IntType) * 8
static const size_t	npos = std::numeric_limits<size_t>::max()
	Value to indicate that find_next_set() did not find any set bits. More...

Friends
Bitvector	operator& (Bitvector const &lhs, Bitvector const &rhs)
Bitvector	operator^ (Bitvector const &lhs, Bitvector const &rhs)
Bitvector	operator| (Bitvector const &lhs, Bitvector const &rhs)

Constructor & Destructor Documentation

Bitvector() [1/8]

Bitvector ( )

default

Default constructor. Creates an empty Bitvector of size 0.

Bitvector() [2/8]

Bitvector ( size_t  size, bool  initial_value = false  )

inline

Constructor that takes a size and an optional bool value to initialize the Bitvector, false by default.

Definition at line 79 of file bitvector.hpp.

Bitvector() [3/8]

Bitvector ( size_t  size, std::initializer_list< size_t >  list  )

inline

Constructor that takes a size and a list of values (positions) to be set to true.

Definition at line 95 of file bitvector.hpp.

Bitvector() [4/8]

Bitvector ( It  first, It  last  )

inline

Construct a Bitvector using a range of bools.

The given iterator pair first to last needs to dereference to values that are convertible to bool.

Definition at line 110 of file bitvector.hpp.

Bitvector() [5/8]

Bitvector	(	size_t	size,
		Bitvector const &	other
	)

Create a Bitvector of a given size, and copy the content of another Bitvector.

If the other bitvector is smaller, the remaining bits are set to 0. If it is bigger, only the first size many bits of it are used.

Definition at line 95 of file bitvector.cpp.

Bitvector() [6/8]

Bitvector

(

std::string const &

values

)

Constructor that takes a std::string of 0s and 1s to build the Bitvector.

This is for cases where some fixed Bitvector needs to be constructed (e.g., for testing purposes). The constructor throws if any character in the string is not 0 or 1.

Definition at line 120 of file bitvector.cpp.

~Bitvector()

~Bitvector ( )

default

Bitvector() [7/8]

Bitvector ( Bitvector const &  )

default

Bitvector() [8/8]

Bitvector ( Bitvector &&  )

default

Member Function Documentation

any_set()

bool any_set

(

)

const

Return if any bits are set at all.

Definition at line 400 of file bitvector.cpp.

count() [1/2]

size_t count

(

)

const

Count the number of set bits in the Bitvector, that is, its Hamming weight, or population count (popcnt).

Definition at line 314 of file bitvector.cpp.

count() [2/2]

size_t count	(	size_t	first,
		size_t	last
	)		const

Count the number of set bits between a range of indices in the Bitvector, that is, its Hamming weight, or population count (popcnt), for that range.

The range first to last is zero-based, with last being the past-the-end index. Hence, this is the same as

size_t count = 0;
for( size_t i = first; i < last; ++i ) {
    if( bitvector.get( i )) {
        ++count;
    }
}

but faster, as we use whole-word counting internally.

Definition at line 334 of file bitvector.cpp.

data()

std::vector<IntType> const& data ( ) const

inline

Definition at line 382 of file bitvector.hpp.

dump()

std::string dump

(

)

const

Definition at line 580 of file bitvector.cpp.

dump_int()

std::string dump_int

(

IntType

x

)

const

Definition at line 594 of file bitvector.cpp.

empty()

bool empty ( ) const

inline

Return whether the Bitvector is empty, that is, has size() == 0.

Note that this function does not count the number of bits that are set to true. It simply returns whether the Bitvector has any size (false), or was default constructed (true).

Definition at line 296 of file bitvector.hpp.

find_next_set()

size_t find_next_set

(

size_t

start

)

const

Return the index of the next position in the Bitvector that is set.

This returns the first position after start, including start itself, that is set. If no such position exists (because all following bits are false), or if start is beyond the length of the vector, Bitvector::npos is returned instead.

Definition at line 410 of file bitvector.cpp.

flip()

void flip ( size_t  index )

inline

Flip (negate) the value of a single bit, with boundary check.

Definition at line 247 of file bitvector.hpp.

get()

bool get ( size_t  index ) const

inline

Return the value of a single bit, with boundary check.

Definition at line 167 of file bitvector.hpp.

hash()

size_t hash

(

)

const

Return an std::hash value for the Bitvector.

Definition at line 483 of file bitvector.cpp.

negate()

void negate

(

)

Flip all bits.

Definition at line 501 of file bitvector.cpp.

normalize()

void normalize

(

)

Bring the Bitvector in a normalized form, where the first bit is always zero.

If the first bit is zero, nothing happens. However, if is is one, the whole Bitvector is flipped using negate().

Definition at line 512 of file bitvector.cpp.

operator!=()

bool operator!=

(

const Bitvector &

other

)

const

Definition at line 305 of file bitvector.cpp.

operator&=()

Bitvector & operator&=

(

Bitvector const &

rhs

)

Definition at line 219 of file bitvector.cpp.

operator=() [1/2]

Bitvector& operator= ( Bitvector &&  )

default

operator=() [2/2]

Bitvector& operator= ( Bitvector const &  )

default

operator==()

bool operator==

(

const Bitvector &

other

)

const

Definition at line 292 of file bitvector.cpp.

operator[]()

bool operator[] ( size_t  index ) const

inline

Return the value of a single bit, without boundary check.

Definition at line 158 of file bitvector.hpp.

operator^=()

Bitvector & operator^=

(

Bitvector const &

rhs

)

Definition at line 249 of file bitvector.cpp.

operator|=()

Bitvector & operator|=

(

Bitvector const &

rhs

)

Definition at line 234 of file bitvector.cpp.

operator~()

Bitvector operator~

(

)

const

Definition at line 264 of file bitvector.cpp.

set() [1/3]

void set	(	size_t	first,
		size_t	last,
		bool	value = true
	)

Set the value of a contiguous range of bits in the Bitvector.

This function takes the first (inclusive) and last (past-the-end) indices into the Bitvector (with boundary check), and sets them to the given value (true by default).

The range first to last is zero-based, with last being the past-the-end index. Hence, this is the same as

for( size_t i = first; i < last; ++i ) {
    bitvector.set( i, value );
}

but faster for anything beyond a few bits, as we operate on whole words internally.

Definition at line 155 of file bitvector.cpp.

set() [2/3]

void set ( size_t  index )

inline

Set the value of a single bit to true, with boundary check.

Definition at line 184 of file bitvector.hpp.

set() [3/3]

void set ( size_t  index, bool  value  )

inline

Set the value of a single bit to a given bool value, with boundary check.

Definition at line 218 of file bitvector.hpp.

set_all()

void set_all

(

const bool

value = false

)

Set all the bits to a specified value.

Definition at line 519 of file bitvector.cpp.

size()

size_t size ( ) const

inline

Return the size (number of bits) of this Bitvector.

Definition at line 304 of file bitvector.hpp.

toggle()

void toggle ( size_t  index )

inline

Alias for flip(), see there for details.

Definition at line 264 of file bitvector.hpp.

unset()

void unset ( size_t  index )

inline

Set the value of a single bit to false, with boundary check.

Definition at line 201 of file bitvector.hpp.

x_hash()

Bitvector::IntType x_hash

(

)

const

Return a hash value of type IntType that is quicker to calculate than hash().

This can be used for obtaining a simple hash using xor of the words. The avalanche effect is of course not present, but for many applications, this hash is good enough and quite useful.

Definition at line 492 of file bitvector.cpp.

Friends And Related Function Documentation

operator&

Bitvector operator& ( Bitvector const &  lhs, Bitvector const &  rhs  )

friend

Definition at line 271 of file bitvector.cpp.

operator^

Bitvector operator^ ( Bitvector const &  lhs, Bitvector const &  rhs  )

friend

Definition at line 285 of file bitvector.cpp.

operator|

Bitvector operator| ( Bitvector const &  lhs, Bitvector const &  rhs  )

friend

Definition at line 278 of file bitvector.cpp.

Member Typedef Documentation

IntType

using IntType = uint64_t

Definition at line 58 of file bitvector.hpp.

Member Data Documentation

IntSize

const size_t IntSize = sizeof(IntType) * 8

static

Definition at line 59 of file bitvector.hpp.

npos

const size_t npos = std::numeric_limits<size_t>::max()

static

Value to indicate that find_next_set() did not find any set bits.

Definition at line 64 of file bitvector.hpp.

---

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

• bitvector.hpp
• bitvector.cpp