位操作类与函数的实现更多...

类
struct	bit_reference
	位引用类更多...
struct	bitmap_iterator< IsConst, BitMap >
	位图迭代器更多...
class	bitmap
	位图容器更多...
class	bitset< N >
	固定大小的位集更多...

函数
constexpr int	popcount64 (const uint64_t x) noexcept
	计算64位整数中1的个数
constexpr int	clz64 (uint64_t x) noexcept
	计算64位整数前导零的个数
constexpr int	popcount32 (const uint32_t x) noexcept
	计算32位整数中1的个数
constexpr int	clz32 (uint32_t x) noexcept
	计算32位整数前导零的个数
constexpr int	popcount (const uintptr_t x) noexcept
	计算整数中1的个数
constexpr int	countl_zero (const uintptr_t x) noexcept
	计算整数前导零的个数
constexpr int	countl_one (const uintptr_t x) noexcept
	计算整数前导1的个数
constexpr int	countr_zero (const uintptr_t x) noexcept
	计算整数尾随零的个数
constexpr int	countr_one (const uintptr_t x) noexcept
	计算整数尾随1的个数
constexpr int	lowest_set_bit_pos (const intptr_t x) noexcept
	获取最低设置位的位置，从0开始
constexpr int	highest_set_bit_pos (const intptr_t x) noexcept
	获取最高设置位的位置
constexpr bool	parity32 (uint32_t x) noexcept
	计算32位整数的奇偶性
constexpr bool	parity64 (uint64_t x) noexcept
	计算64位整数的奇偶性
constexpr bool	parity (const uintptr_t x) noexcept
	计算整数的奇偶性
constexpr int	bit_width (const uintptr_t x) noexcept
	计算表示整数所需的最小位宽
constexpr uintptr_t	bit_floor (const uintptr_t x) noexcept
	获取不大于x的最大2的幂
constexpr uint64_t	bit_ceil (const uintptr_t x) noexcept
	获取不小于x的最小2的幂
constexpr bool	has_single_bit (const uintptr_t x) noexcept
	检查整数是否为2的幂
constexpr uint32_t	rotate_l32 (const uint32_t x, const int s) noexcept
	32位整数循环左移
constexpr uint32_t	rotate_r32 (const uint32_t x, const int s) noexcept
	32位整数循环右移
constexpr uint64_t	rotate_l64 (const uint64_t x, const int s) noexcept
	64位整数循环左移
constexpr uint64_t	rotate_r64 (const uint64_t x, const int s) noexcept
	64位整数循环右移
constexpr uintptr_t	rotate_l (const uintptr_t x, const int s) noexcept
	整数循环左移
constexpr uintptr_t	rotate_r (const uintptr_t x, const int s) noexcept
	整数循环右移
constexpr uintptr_t	bit_extract (const uintptr_t x, const int pos, const int len) noexcept
	从整数中提取指定位段
constexpr uintptr_t	bit_insert (const uintptr_t x, const uintptr_t bits, const int pos, const int len) noexcept
	向整数中插入指定位段
constexpr uint32_t	reverse_bits32 (uint32_t x) noexcept
	反转32位整数的位顺序
constexpr uint64_t	reverse_bits64 (uint64_t x) noexcept
	反转64位整数的位顺序
constexpr uintptr_t	reverse_bits (const uintptr_t x) noexcept
	反转整数的位顺序
constexpr uintptr_t	mask_from_to (const int from, const int to) noexcept
	生成从from到to的位掩码

变量
constexpr uint32_t	BITMAP_WORD_SIZE = 8 * sizeof(uint32_t)
	每个字的位数
constexpr byte_t	POPCOUNT_TABLE [256]
	popcount查找表

详细描述

位操作类与函数的实现

函数说明

◆ bit_ceil()

uint64_t bit_ceil ( const uintptr_t x )

constexprnoexcept

获取不小于x的最小2的幂

参数

x 无符号整数

返回: 不小于x的最小2的幂，如果x为0则返回1

在文件 bit.hpp 第 307 行定义.

引用了 bit_floor() , 以及 floor().

◆ bit_extract()

uintptr_t bit_extract	(	const uintptr_t	x,
		const int	pos,
		const int	len )

constexprnoexcept

从整数中提取指定位段

参数

x	源整数
pos	起始位置，从0开始
len	要提取的位数

返回: 提取的位段

在文件 bit.hpp 第 408 行定义.

◆ bit_floor()

uintptr_t bit_floor ( const uintptr_t x )

constexprnoexcept

获取不大于x的最大2的幂

参数

x 无符号整数

返回: 不大于x的最大2的幂，如果x为0则返回0

在文件 bit.hpp 第 300 行定义.

引用了 bit_width().

被这些函数引用 bit_ceil().

◆ bit_insert()

uintptr_t bit_insert	(	const uintptr_t	x,
		const uintptr_t	bits,
		const int	pos,
		const int	len )

constexprnoexcept

向整数中插入指定位段

参数

x	目标整数
bits	要插入的位段
pos	插入位置，从0开始
len	要插入的位数

返回: 插入后的整数

在文件 bit.hpp 第 420 行定义.

◆ bit_width()

int bit_width ( const uintptr_t x )

constexprnoexcept

计算表示整数所需的最小位宽

参数

x 无符号整数

返回: 表示x所需的最小位数

在文件 bit.hpp 第 287 行定义.

引用了 countl_zero().

被这些函数引用 bit_floor().

◆ clz32()

int clz32 ( uint32_t x )

constexprnoexcept

计算32位整数前导零的个数

参数

x 32位无符号整数

返回: x中前导零的个数，如果x为0则返回32

使用二分查找法优化前导零计数。

在文件 bit.hpp 第 126 行定义.

被这些函数引用 countl_zero() , 以及 highest_set_bit_pos().

◆ clz64()

int clz64 ( uint64_t x )

constexprnoexcept

计算64位整数前导零的个数

参数

x 64位无符号整数

返回: x中前导零的个数，如果x为0则返回64

使用二分查找法优化前导零计数。

在文件 bit.hpp 第 74 行定义.

被这些函数引用 _udiv128(), countl_zero() , 以及 highest_set_bit_pos().

◆ countl_one()

int countl_one ( const uintptr_t x )

constexprnoexcept

计算整数前导1的个数

参数

x 无符号整数

返回: x中前导1的个数

通过对x按位取反后计算前导零个数。

在文件 bit.hpp 第 190 行定义.

引用了 countl_zero().

◆ countl_zero()

int countl_zero ( const uintptr_t x )

constexprnoexcept

计算整数前导零的个数

参数

x 无符号整数

返回: x中前导零的个数

根据平台位数调用相应的clz函数。

在文件 bit.hpp 第 175 行定义.

引用了 clz32() , 以及 clz64().

被这些函数引用 bit_width() , 以及 countl_one().

◆ countr_one()

int countr_one ( const uintptr_t x )

constexprnoexcept

计算整数尾随1的个数

参数

x 无符号整数

返回: x中尾随1的个数

通过对x按位取反后计算尾随零个数。

在文件 bit.hpp 第 208 行定义.

引用了 countr_zero().

◆ countr_zero()

int countr_zero ( const uintptr_t x )

constexprnoexcept

计算整数尾随零的个数

参数

x 无符号整数

返回: x中尾随零的个数

使用位运算技巧得到最低有效位的掩码。

在文件 bit.hpp 第 199 行定义.

引用了 popcount().

被这些函数引用 countr_one() , 以及 lowest_set_bit_pos().

◆ has_single_bit()

bool has_single_bit ( const uintptr_t x )

constexprnoexcept

检查整数是否为2的幂

参数

x 无符号整数

返回: 如果x是2的幂则返回true，否则返回false

在文件 bit.hpp 第 320 行定义.

◆ highest_set_bit_pos()

int highest_set_bit_pos ( const intptr_t x )

constexprnoexcept

获取最高设置位的位置

参数

x 有符号整数

返回: 最高设置位的位置，如果没有设置位则返回-1

在文件 bit.hpp 第 223 行定义.

引用了 clz32() , 以及 clz64().

◆ lowest_set_bit_pos()

int lowest_set_bit_pos ( const intptr_t x )

constexprnoexcept

获取最低设置位的位置，从0开始

参数

x 有符号整数

返回: 最低设置位的位置，如果没有设置位则返回-1

在文件 bit.hpp 第 216 行定义.

引用了 countr_zero().

◆ mask_from_to()

uintptr_t mask_from_to	(	const int	from,
		const int	to )

constexprnoexcept

生成从from到to的位掩码

参数

from	起始位置（包含）
to	结束位置（包含）

返回: 从from位到to位为1，其他位为0的掩码

在文件 bit.hpp 第 478 行定义.

◆ parity()

bool parity ( const uintptr_t x )

constexprnoexcept

计算整数的奇偶性

参数

x 无符号整数

返回: 如果x中1的个数为奇数返回true，否则返回false

根据平台位数调用相应的奇偶性计算函数。

在文件 bit.hpp 第 273 行定义.

引用了 parity32() , 以及 parity64().

◆ parity32()

bool parity32 ( uint32_t x )

constexprnoexcept

计算32位整数的奇偶性

参数

x 32位无符号整数

返回: 如果x中1的个数为奇数返回true，否则返回false

使用分治法计算奇偶性。

在文件 bit.hpp 第 242 行定义.

被这些函数引用 parity().

◆ parity64()

bool parity64 ( uint64_t x )

constexprnoexcept

计算64位整数的奇偶性

参数

x 64位无符号整数

返回: 如果x中1的个数为奇数返回true，否则返回false

在文件 bit.hpp 第 256 行定义.

被这些函数引用 parity().

◆ popcount()

int popcount ( const uintptr_t x )

constexprnoexcept

计算整数中1的个数

参数

x 无符号整数

返回: x中1的个数

根据平台位数调用相应的popcount函数。

在文件 bit.hpp 第 160 行定义.

引用了 popcount32() , 以及 popcount64().

被这些函数引用 bitset< N >::count() , 以及 countr_zero().

◆ popcount32()

int popcount32 ( const uint32_t x )

constexprnoexcept

计算32位整数中1的个数

参数

x 32位无符号整数

返回: x中1的个数

使用查表法分别计算4个字节的popcount，然后求和。

在文件 bit.hpp 第 112 行定义.

被这些函数引用 popcount().

◆ popcount64()

int popcount64 ( const uint64_t x )

constexprnoexcept

计算64位整数中1的个数

参数

x 64位无符号整数

返回: x中1的个数

使用查表法分别计算8个字节的popcount，然后求和。

在文件 bit.hpp 第 56 行定义.

被这些函数引用 popcount().

◆ reverse_bits()

uintptr_t reverse_bits ( const uintptr_t x )

constexprnoexcept

反转整数的位顺序

参数

x 无符号整数

返回: 位反转后的整数

根据平台位数调用相应的位反转函数。

在文件 bit.hpp 第 463 行定义.

引用了 reverse_bits32() , 以及 reverse_bits64().

◆ reverse_bits32()

uint32_t reverse_bits32 ( uint32_t x )

constexprnoexcept

反转32位整数的位顺序

参数

x 32位无符号整数

返回: 位反转后的整数

在文件 bit.hpp 第 432 行定义.

被这些函数引用 reverse_bits().

◆ reverse_bits64()

uint64_t reverse_bits64 ( uint64_t x )

constexprnoexcept

反转64位整数的位顺序

参数

x 64位无符号整数

返回: 位反转后的整数

在文件 bit.hpp 第 446 行定义.

被这些函数引用 reverse_bits().

◆ rotate_l()

uintptr_t rotate_l	(	const uintptr_t	x,
		const int	s )

constexprnoexcept

整数循环左移

参数

x	无符号整数
s	旋转位数

返回: 循环左移后的结果

根据平台位数调用相应的循环左移函数。

在文件 bit.hpp 第 376 行定义.

引用了 rotate_l32() , 以及 rotate_l64().

◆ rotate_l32()

uint32_t rotate_l32	(	const uint32_t	x,
		const int	s )

constexprnoexcept

32位整数循环左移

参数

x	32位无符号整数
s	旋转位数

返回: 循环左移后的结果

在文件 bit.hpp 第 328 行定义.

被这些函数引用 rotate_l() , 以及 rotate_r32().

◆ rotate_l64()

uint64_t rotate_l64	(	const uint64_t	x,
		const int	s )

constexprnoexcept

64位整数循环左移

参数

x	64位无符号整数
s	旋转位数

返回: 循环左移后的结果

在文件 bit.hpp 第 351 行定义.

被这些函数引用 rotate_l() , 以及 rotate_r64().

◆ rotate_r()

uintptr_t rotate_r	(	const uintptr_t	x,
		const int	s )

constexprnoexcept

整数循环右移

参数

x	无符号整数
s	旋转位数

返回: 循环右移后的结果

根据平台位数调用相应的循环右移函数。

在文件 bit.hpp 第 392 行定义.

引用了 rotate_r32() , 以及 rotate_r64().

◆ rotate_r32()

uint32_t rotate_r32	(	const uint32_t	x,
		const int	s )

constexprnoexcept

32位整数循环右移

参数

x	32位无符号整数
s	旋转位数

返回: 循环右移后的结果

在文件 bit.hpp 第 343 行定义.

引用了 rotate_l32().

被这些函数引用 rotate_r().

◆ rotate_r64()

uint64_t rotate_r64	(	const uint64_t	x,
		const int	s )

constexprnoexcept

64位整数循环右移

参数

x	64位无符号整数
s	旋转位数

返回: 循环右移后的结果

在文件 bit.hpp 第 366 行定义.

引用了 rotate_l64().

被这些函数引用 rotate_r().

变量说明

◆ POPCOUNT_TABLE

byte_t POPCOUNT_TABLE[256]

inlineconstexpr

初始值:

                               = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2,
3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4,
5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}

popcount查找表

预计算的popcount表，用于快速计算字节中1的个数。包含0-255所有可能字节值的popcount值。

在文件 bit.hpp 第 30 行定义.