位运算技巧详解：从基础概念到实际应用

位运算技巧详解：从基础概念到实际应用

引用

CSDN

1.

https://blog.csdn.net/2301_81831423/article/details/144317353

位运算在编程中扮演着重要的角色，它不仅能优化代码性能，还能解决许多实际问题。本文将详细介绍位运算的各种技巧及其应用场景，帮助你更好地掌握这一基础且重要的编程概念。

1. 除法（乘法）转位运算

当数字的除数（或乘数）是 2^n 时，可以用移位操作代替除法或乘法：

• 除法: x/2^n=x≫n
• 乘法: x×2^n=x≪n

实际场景应用：

1. 位移处理数组索引：在大数组操作中，用移位快速计算内存地址。
2. 音频/图像缩放：快速按倍数调整采样率或分辨率。

2. 按位与（&）确定资源状态

以段页式存储为例，用二进制表示资源分配状态：

• 1：已占用；
• 0：空闲。

if (1 & (binary >> (n - 1))) {
    // 第 n 段已被占用
} else {
    // 第 n 段空闲
}

补充示例：
用二进制记录一个8位灯的开关状态，例如 11001011：

• 若第 3 位是 1，表示灯开着；
• 若是 0，表示灯关着。

判断某灯的状态：

if (binary & (1 << (3 - 1))) {
    // 第 3 盏灯开着
} else {
    // 第 3 盏灯关着
}

3. 按位或（|）改变资源状态

通过按位或操作，修改资源状态。

占用资源：
将某段的状态设置为 1：

binary = binary | (1 << (n - 1));
// 占用第 n 段资源

释放资源：
将某段的状态设置为 0：

binary = binary & ~(1 << (n - 1));
// 释放第 n 段资源

示例：
假设 binary = 11001011，表示灯的开关状态。

• 开第 5 盏灯：

binary = binary | (1 << (5 - 1)); // 结果: 11101011

• 关第 2 盏灯：

binary = binary & ~(1 << (2 - 1)); // 结果: 11001001

4. 按位与提取整型数字最后面的 1

公式：n&(−n)

实际场景：

• 查找最后一个有效位：用于低级数据结构操作（如位图、哈希表优化）。
• 定位标志位：在状态标志中，提取某些重要的触发事件。

示例：

n = 18; // 二进制 10010
last_bit = n & (-n); // 结果: 10 (二进制)

5. 去掉整型数字最后面的 1

公式：n&(n−1)

实际场景：

• 计数二进制中的 1 数量：常用于优化中断、状态分析等。
• 移除标志位：动态调整任务状态。

示例：

n = 18; // 二进制 10010
n = n & (n - 1); // 结果: 10000

6. 异或（^）的小技巧

交换两数值（无临时变量）：

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

异或加密：
异或操作常用于简单加密，例如：

key = 42; // 密钥
data = 123; // 原始数据
encrypted = data ^ key; // 加密
decrypted = encrypted ^ key; // 解密

示例：

key = 42; // 101010
data = 123; // 1111011
encrypted = 123 ^ 42; // 1111011 ^ 101010 = 10111101
decrypted = 10111101 ^ 101010; // 1111011

7. 补充技巧

统计二进制中 1 的个数
通过移除最后一个 1 的方法高效统计：

int countOnes(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

判断是否是 2^n
n>0&&(n&(n−1))==0

示例：

n = 16; // 二进制 10000
if (n > 0 && (n & (n - 1)) == 0) {
    // 是 2 的幂
} else {
    // 不是 2 的幂
}

8. 实际应用案例：位图法实现内存管理

假设有 32 个资源，状态存储在一个 32 位整型变量中：

• 用 1 表示资源已分配；
• 用 0 表示资源空闲。

分配资源：

for (int i = 0; i < 32; i++) {
    if (!(resources & (1 << i))) { // 找到空闲资源
        resources = resources | (1 << i); // 分配资源
        break;
    }
}

释放资源：

resources = resources & ~(1 << index); // 释放第 index 资源