bitset.h File Reference

#include <string.h>
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <string>
#include <tuple>
#include <vector>
#include "absl/log/check.h"
#include "ortools/base/logging.h"

Go to the source code of this file.

Classes
class	operations_research::Bitset64< IndexType >
class	operations_research::Bitset64< IndexType >::ConstView
	When speed matter, caching the base pointer helps. More...
class	operations_research::Bitset64< IndexType >::View
class	operations_research::Bitset64< IndexType >::Iterator
class	operations_research::BitQueue64
class	operations_research::SparseBitset< IntegerType >

Namespaces
namespace	operations_research
	In SWIG mode, we don't want anything besides these top-level includes.

Macros
#define	USE_DEBRUIJN   true

Functions
uint64_t	operations_research::OneBit64 (int pos)
	Returns a word with only bit pos set.
uint32_t	operations_research::OneBit32 (int pos)
uint64_t	operations_research::BitCount64 (uint64_t n)
	Returns the number of bits set in n.
uint32_t	operations_research::BitCount32 (uint32_t n)
uint64_t	operations_research::LeastSignificantBitWord64 (uint64_t n)
	Returns a word with only the least significant bit of n set.
uint32_t	operations_research::LeastSignificantBitWord32 (uint32_t n)
int	operations_research::LeastSignificantBitPosition64DeBruijn (uint64_t n)
int	operations_research::LeastSignificantBitPosition64Default (uint64_t n)
int	operations_research::LeastSignificantBitPosition64 (uint64_t n)
int	operations_research::LeastSignificantBitPosition32DeBruijn (uint32_t n)
int	operations_research::LeastSignificantBitPosition32Default (uint32_t n)
int	operations_research::LeastSignificantBitPosition32 (uint32_t n)
int	operations_research::MostSignificantBitPosition64Default (uint64_t n)
	Returns the most significant bit position in n.
int	operations_research::MostSignificantBitPosition64 (uint64_t n)
int	operations_research::MostSignificantBitPosition32Default (uint32_t n)
int	operations_research::MostSignificantBitPosition32 (uint32_t n)
uint64_t	operations_research::OneRange64 (uint64_t s, uint64_t e)
	Returns a word with bits from s to e set.
uint32_t	operations_research::OneRange32 (uint32_t s, uint32_t e)
uint64_t	operations_research::IntervalUp64 (uint64_t s)
	Returns a word with s least significant bits unset.
uint32_t	operations_research::IntervalUp32 (uint32_t s)
uint64_t	operations_research::IntervalDown64 (uint64_t s)
	Returns a word with the s most significant bits unset.
uint32_t	operations_research::IntervalDown32 (uint32_t s)
uint32_t	operations_research::BitPos64 (uint64_t pos)
	Bit operators used to manipulates bitsets.
uint32_t	operations_research::BitPos32 (uint32_t pos)
uint64_t	operations_research::BitOffset64 (uint64_t pos)
	Returns the word number corresponding to bit number pos.
uint32_t	operations_research::BitOffset32 (uint32_t pos)
uint64_t	operations_research::BitLength64 (uint64_t size)
	Returns the number of words needed to store size bits.
uint32_t	operations_research::BitLength32 (uint32_t size)
uint64_t	operations_research::BitShift64 (uint64_t v)
	Returns the bit number in the bitset of the first bit of word number v.
uint32_t	operations_research::BitShift32 (uint32_t v)
bool	operations_research::IsBitSet64 (const uint64_t *const bitset, uint64_t pos)
	Returns true if the bit pos is set in bitset.
bool	operations_research::IsBitSet32 (const uint32_t *const bitset, uint32_t pos)
void	operations_research::SetBit64 (uint64_t *const bitset, uint64_t pos)
	Sets the bit pos to true in bitset.
void	operations_research::SetBit32 (uint32_t *const bitset, uint32_t pos)
void	operations_research::ClearBit64 (uint64_t *const bitset, uint64_t pos)
	Sets the bit pos to false in bitset.
void	operations_research::ClearBit32 (uint32_t *const bitset, uint32_t pos)
uint64_t	operations_research::BitCountRange64 (const uint64_t *bitset, uint64_t start, uint64_t end)
	Returns the number of bits set in bitset between positions start and end.
uint32_t	operations_research::BitCountRange32 (const uint32_t *bitset, uint32_t start, uint32_t end)
bool	operations_research::IsEmptyRange64 (const uint64_t *bitset, uint64_t start, uint64_t end)
	Returns true if no bits are set in bitset between start and end.
bool	operations_research::IsEmptyRange32 (const uint32_t *bitset, uint32_t start, uint32_t end)
int64_t	operations_research::LeastSignificantBitPosition64 (const uint64_t *bitset, uint64_t start, uint64_t end)
	Returns the first bit set in bitset between start and max_bit.
int	operations_research::LeastSignificantBitPosition32 (const uint32_t *bitset, uint32_t start, uint32_t end)
int64_t	operations_research::MostSignificantBitPosition64 (const uint64_t *bitset, uint64_t start, uint64_t end)
	Returns the last bit set in bitset between min_bit and start.
int	operations_research::MostSignificantBitPosition32 (const uint32_t *bitset, uint32_t start, uint32_t end)
int64_t	operations_research::UnsafeLeastSignificantBitPosition64 (const uint64_t *bitset, uint64_t start, uint64_t end)
int32_t	operations_research::UnsafeLeastSignificantBitPosition32 (const uint32_t *bitset, uint32_t start, uint32_t end)
int64_t	operations_research::UnsafeMostSignificantBitPosition64 (const uint64_t *bitset, uint64_t start, uint64_t end)
int32_t	operations_research::UnsafeMostSignificantBitPosition32 (const uint32_t *bitset, uint32_t start, uint32_t end)
uint64_t	operations_research::TwoBitsFromPos64 (uint64_t pos)
	Returns a mask with the bits pos % 64 and (pos ^ 1) % 64 sets.

Variables
static const uint64_t	operations_research::kAllBits64 = uint64_t{0xFFFFFFFFFFFFFFFF}
	Basic bit operations.
static const uint64_t	operations_research::kAllBitsButLsb64 = uint64_t{0xFFFFFFFFFFFFFFFE}
static const uint32_t	operations_research::kAllBits32 = 0xFFFFFFFFU

Macro Definition Documentation

USE_DEBRUIJN

#define USE_DEBRUIJN   true

Returns the least significant bit position in n. Discussion around lsb computation: De Bruijn is almost as fast as the bsr/bsf-instruction-based intrinsics. Both are always much faster than the Default algorithm.

Definition at line 74 of file bitset.h.