在 C++ 中，位运算（Bit Manipulation）常用于高效处理二进制数据、优化计算或实现特定算法。以下是常用的位运算函数和操作：

1. 基本位运算符

运算符 含义 示例
& 按位与 a & b
\| 按位或 a \| b
^ 按位异或 a ^ b
~ 按位取反 ~a
<< 左移（乘以 2ⁿ） a << n
>> 右移（除以 2ⁿ） a >> n

2. C++20 <bit>头文件提供的位操作函数

C++20 引入了 <bit>头文件，提供了一些高效的位运算函数：

(1) std::popcount- 计算 1 的个数

#include <bit>
unsigned int count = std::popcount(0b10101010); // 返回 4

(2) std::has_single_bit- 检查是否是 2 的幂

bool is_power_of_two = std::has_single_bit(8); // true
bool is_power_of_two = std::has_single_bit(7); // false

(3) std::bit_width- 计算最小位宽

int width = std::bit_width(5); // 3（因为 5 = 0b101，需要 3 位）

(4) std::rotl/ std::rotr- 循环左移/右移

unsigned int x = 0b1101;
unsigned int rot_left = std::rotl(x, 1);  // 0b1011
unsigned int rot_right = std::rotr(x, 1); // 0b1110

(5) std::countl_zero/ std::countr_zero- 前导/后导零计数

unsigned int x = 0b00011010;
int leading_zeros = std::countl_zero(x);  // 3（前导 3 个 0）
int trailing_zeros = std::countr_zero(x); // 1（后导 1 个 0）

3. 常用位运算技巧

(1) 判断奇偶

bool is_odd = (x & 1); // true 为奇数，false 为偶数

(2) 交换两个数（无临时变量）

a ^= b;
b ^= a;
a ^= b;

(3) 取最低位的 1（lowbit）

int lowbit = x & (-x); // 例如 x=6 (0b110) → 2 (0b010)

(4) 判断是否是 2 的幂

bool is_power_of_two = (x & (x - 1)) == 0;

(5) 计算绝对值（无分支）

int abs_val = (x ^ (x >> 31)) - (x >> 31);

(6) 掩码操作

// 取低 4 位
int lower_bits = x & 0xF; // 0xF = 0b1111

// 设置第 3 位为 1
x |= (1 << 2);

// 清除第 3 位
x &= ~(1 << 2);

// 切换第 3 位（0→1，1→0）
x ^= (1 << 2);

4. 位运算应用场景

  • 位掩码（Bitmask）：用于权限控制、状态压缩
  • 快速乘除：x << n相当于 x * 2ⁿ，x >> n相当于 x / 2ⁿ
  • 哈希优化：某些哈希算法使用位运算加速
  • 位图（Bitmap）：用于高效存储布尔数组
  • 位级并行计算：如 SIMD 优化

5. 示例：位掩码权限控制

enum Permissions 
{
    READ = 1 << 0,   // 0b0001
    WRITE = 1 << 1,  // 0b0010
    EXECUTE = 1 << 2 // 0b0100
};

int user_perms = READ | WRITE; // 0b0011（可读可写）

// 检查权限
bool can_write = user_perms & WRITE; // true

// 添加权限
user_perms |= EXECUTE; // 0b0111（添加执行权限）

// 移除权限
user_perms &= ~WRITE; // 0b0101（移除写权限）

总结

功能 C++ 方法
计算 1 的个数 std::popcount
检查 2 的幂 std::has_single_bit
计算最小位宽 std::bit_width
循环移位 std::rotl, std::rotr
前导/后导零计数 std::countl_zero, std::countr_zero
位掩码操作 &, \|, ^, ~

这些位运算技巧在算法竞赛、系统编程和性能优化中非常有用！🚀