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 循环移位函数。这些函数替代了以前需要手写的位操作技巧,编译器通常会将它们编译为高效的硬件指令。