std::bit_ceil / std::bit_floor / std::bit_width / std::popcount
概述
C++20 在 <bit> 头文件中引入了一组位操作函数,用于处理整数的二进制位。这些函数都是 constexpr 和 noexcept 的,只接受无符号整数类型。
| 函数 | 说明 | 示例 |
|---|---|---|
bit_ceil(x) | 不小于 x 的最小的 2 的幂 | bit_ceil(5) = 8 |
bit_floor(x) | 不大于 x 的最大的 2 的幂 | bit_floor(5) = 4 |
bit_width(x) | 表示 x 所需的最少位数 | bit_width(5) = 3 |
popcount(x) | x 的二进制中 1 的个数 | popcount(5) = 2 |
has_single_bit(x) | x 是否是 2 的幂 | has_single_bit(4) = true |
countl_zero(x) | 从最高位开始连续 0 的个数 | countl_zero(1) = 31 (32位) |
countl_one(x) | 从最高位开始连续 1 的个数 | countl_one(0xFF000000) = 8 |
countr_zero(x) | 从最低位开始连续 0 的个数 | countr_zero(8) = 3 |
countr_one(x) | 从最低位开始连续 1 的个数 | countr_one(7) = 3 |
rotl(x, s) | 循环左移 s 位 | rotl(0x12, 4) |
rotr(x, s) | 循环右移 s 位 | rotr(0x12, 4) |
基本示例
cpp
#include <iostream>
#include <bit>
#include <cstdint>
#include <bitset>
#include <vector>
#include <iomanip>
// ============================
// 示例1:bit_ceil——向上取到 2 的幂
// ============================
void bit_ceil_demo() {
std::cout << "bit_ceil:" << std::endl;
// bit_ceil 返回不小于 x 的最小的 2 的幂
std::cout << " bit_ceil(1) = " << std::bit_ceil(1u) << std::endl; // 1
std::cout << " bit_ceil(2) = " << std::bit_ceil(2u) << std::endl; // 2
std::cout << " bit_ceil(3) = " << std::bit_ceil(3u) << std::endl; // 4
std::cout << " bit_ceil(5) = " << std::bit_ceil(5u) << std::endl; // 8
std::cout << " bit_ceil(7) = " << std::bit_ceil(7u) << std::endl; // 8
std::cout << " bit_ceil(8) = " << std::bit_ceil(8u) << std::endl; // 8
std::cout << " bit_ceil(9) = " << std::bit_ceil(9u) << std::endl; // 16
std::cout << " bit_ceil(100)= " << std::bit_ceil(100u) << std::endl; // 128
// 典型用途:分配对齐到 2 的幂的缓冲区大小
unsigned requested = 1000;
unsigned aligned = std::bit_ceil(requested);
std::cout << " 请求 " << requested << " 字节,对齐后: "
<< aligned << " 字节" << std::endl; // 1024
}
// ============================
// 示例2:bit_floor——向下取到 2 的幂
// ============================
void bit_floor_demo() {
std::cout << "bit_floor:" << std::endl;
// bit_floor 返回不大于 x 的最大的 2 的幂(x=0 时返回 0)
std::cout << " bit_floor(0) = " << std::bit_floor(0u) << std::endl; // 0
std::cout << " bit_floor(1) = " << std::bit_floor(1u) << std::endl; // 1
std::cout << " bit_floor(3) = " << std::bit_floor(3u) << std::endl; // 2
std::cout << " bit_floor(5) = " << std::bit_floor(5u) << std::endl; // 4
std::cout << " bit_floor(8) = " << std::bit_floor(8u) << std::endl; // 8
std::cout << " bit_floor(9) = " << std::bit_floor(9u) << std::endl; // 8
std::cout << " bit_floor(100)= " << std::bit_floor(100u) << std::endl; // 64
std::cout << " bit_floor(255)= " << std::bit_floor(255u) << std::endl; // 128
}
// ============================
// 示例3:bit_width——需要的位数
// ============================
void bit_width_demo() {
std::cout << "bit_width:" << std::endl;
// bit_width 返回表示 x 所需的最少位数
std::cout << " bit_width(0) = " << std::bit_width(0u) << std::endl; // 0
std::cout << " bit_width(1) = " << std::bit_width(1u) << std::endl; // 1
std::cout << " bit_width(2) = " << std::bit_width(2u) << std::endl; // 2
std::cout << " bit_width(3) = " << std::bit_width(3u) << std::endl; // 2
std::cout << " bit_width(4) = " << std::bit_width(4u) << std::endl; // 3
std::cout << " bit_width(7) = " << std::bit_width(7u) << std::endl; // 3
std::cout << " bit_width(8) = " << std::bit_width(8u) << std::endl; // 4
std::cout << " bit_width(255) = " << std::bit_width(255u) << std::endl; // 8
std::cout << " bit_width(256) = " << std::bit_width(256u) << std::endl; // 9
// 实际用途:计算存储某个最大值需要多少位
unsigned max_id = 1000;
int bits_needed = std::bit_width(max_id);
std::cout << " 存储最大值 " << max_id << " 需要 "
<< bits_needed << " 位" << std::endl; // 10 位
}
// ============================
// 示例4:popcount——计算 1 的个数
// ============================
void popcount_demo() {
std::cout << "popcount:" << std::endl;
std::uint8_t values[] = {0, 0b00011101, 0b11111111, 0b10101010};
for (auto v : values) {
std::cout << " popcount(" << std::bitset<8>(v) << ") = "
<< std::popcount(v) << std::endl;
}
// popcount(00000000) = 0
// popcount(00011101) = 4
// popcount(11111111) = 8
// popcount(10101010) = 4
// 实际用途:计算集合的大小(位图中有多少个元素)
std::uint32_t bitmap = 0b1010'1100'0011'0001;
std::cout << " 位图中的元素数: " << std::popcount(bitmap) << std::endl;
}
// ============================
// 示例5:has_single_bit——判断是否是 2 的幂
// ============================
void has_single_bit_demo() {
std::cout << "has_single_bit:" << std::endl;
std::cout << std::boolalpha;
unsigned values[] = {0, 1, 2, 3, 4, 5, 8, 16, 15, 64, 100, 128};
for (auto v : values) {
std::cout << " has_single_bit(" << v << ") = "
<< std::has_single_bit(v) << std::endl;
}
}
// ============================
// 示例6:countl_zero 和 countr_zero
// ============================
void count_zeros_demo() {
std::cout << "countl_zero / countr_zero (uint8_t):" << std::endl;
std::uint8_t values[] = {0b00000001, 0b00001000, 0b10000000, 0b00110000};
for (auto v : values) {
std::cout << " " << std::bitset<8>(v)
<< " -> countl_zero=" << std::countl_zero(v)
<< ", countr_zero=" << std::countr_zero(v) << std::endl;
}
// 00000001 -> countl_zero=7, countr_zero=0
// 00001000 -> countl_zero=4, countr_zero=3
// 10000000 -> countl_zero=0, countr_zero=7
// 00110000 -> countl_zero=2, countr_zero=4
}
// ============================
// 示例7:rotl 和 rotr——循环移位
// ============================
void rotate_demo() {
std::cout << "rotl / rotr (uint8_t):" << std::endl;
std::uint8_t value = 0b00110001;
auto left = std::rotl(value, 2);
auto right = std::rotr(value, 2);
std::cout << " 原值: " << std::bitset<8>(value) << std::endl;
std::cout << " rotl(2): " << std::bitset<8>(left) << std::endl;
std::cout << " rotr(2): " << std::bitset<8>(right) << std::endl;
// 00110001 rotl 2 = 11000100
// 00110001 rotr 2 = 01001100
}
// ============================
// 示例8:编译期使用
// ============================
void constexpr_demo() {
// 所有函数都是 constexpr
static_assert(std::bit_ceil(5u) == 8);
static_assert(std::bit_floor(5u) == 4);
static_assert(std::bit_width(5u) == 3);
static_assert(std::popcount(5u) == 2);
static_assert(std::has_single_bit(8u));
static_assert(!std::has_single_bit(5u));
static_assert(std::countl_zero(std::uint8_t(1)) == 7);
static_assert(std::countr_zero(std::uint8_t(8)) == 3);
std::cout << "所有 static_assert 通过" << std::endl;
}
// ============================
// 示例9:实际应用——哈希表大小对齐
// ============================
void hashtable_demo() {
// 哈希表通常需要大小为 2 的幂(用位与代替取模)
unsigned requested_size = 1500;
unsigned table_size = std::bit_ceil(requested_size);
std::cout << "请求容量: " << requested_size
<< ", 实际分配: " << table_size << std::endl;
// 用位与代替取模
unsigned hash = 12345;
unsigned index = hash & (table_size - 1); // 等价于 hash % table_size
std::cout << "hash " << hash << " 的索引: " << index << std::endl;
}
int main() {
std::cout << "=== bit_ceil ===" << std::endl;
bit_ceil_demo();
std::cout << "\n=== bit_floor ===" << std::endl;
bit_floor_demo();
std::cout << "\n=== bit_width ===" << std::endl;
bit_width_demo();
std::cout << "\n=== popcount ===" << std::endl;
popcount_demo();
std::cout << "\n=== has_single_bit ===" << std::endl;
has_single_bit_demo();
std::cout << "\n=== count zeros ===" << std::endl;
count_zeros_demo();
std::cout << "\n=== rotate ===" << std::endl;
rotate_demo();
std::cout << "\n=== constexpr ===" << std::endl;
constexpr_demo();
std::cout << "\n=== 哈希表 ===" << std::endl;
hashtable_demo();
return 0;
}适用场景
- 内存分配器中对齐到 2 的幂
- 哈希表大小的 2 的幂对齐
- 位图(bitmap)操作中计算置位数
- 计算存储值需要的位数
- 密码学和校验算法中的位操作
- 替代手写的位操作技巧
常见问题
这些函数只接受无符号整数吗?
是的。所有 <bit> 中的位操作函数都只接受无符号整数类型。传入有符号整数会导致编译错误。
bit_ceil(0) 的结果是什么?
bit_ceil(0) 返回 1(因为 2^0 = 1 是不小于 0 的最小的 2 的幂)。但注意如果结果超过类型能表示的范围,行为未定义。
popcount 在现代 CPU 上效率如何?
大多数现代 CPU(x86 的 POPCNT 指令、ARM 的 CNT 指令)有硬件支持,编译器会编译为单条指令。
bit_width 和 log2 的关系是什么?
bit_width(x) 等价于 floor(log2(x)) + 1(x > 0 时)。它是整数版的 log2 向上取整。
注意事项
- 所有函数只接受无符号整数类型
- bit_ceil 的结果如果溢出类型范围,行为未定义
- bit_floor(0) 返回 0,bit_width(0) 返回 0
- 这些函数都是 constexpr 和 noexcept 的
- 需要
<bit>头文件
总结
C++20 的 <bit> 头文件提供了一套完整的位操作函数。bit_ceil 和 bit_floor 用于向上/向下取到 2 的幂,bit_width 计算表示值需要的位数,popcount 计算二进制中 1 的个数,has_single_bit 判断是否为 2 的幂。还有 countl_zero、countr_zero 等计数函数和 rotl、rotr 循环移位函数。这些函数替代了以前需要手写的位操作技巧,编译器通常会将它们编译为高效的硬件指令。