位运算讲解

🏝️专栏：https://blog.csdn.net/2301_81831423/category_12845252.html 🌅主页：猫咪-9527-CSDN博客 “欲穷千里目，更上一层楼。会当凌绝顶，一览众山小。”

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

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

修改后的值不发生变化 普通除法位运算除法x/2^nx>>n普通乘法位运算乘法x*2^nx<<n 修改后x的值发生变化 普通除法位运算除法x/=2^nx>>=n普通乘法位运算乘法x*=2^nx<<=n

实际场景应用：

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

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

以二进制000101为例 当两个二进制都为1是为1，其余为0 &000110 --------------------------- 000100 比特位1比特位2结果100111010000 注：01也可以表示真假

实际场景应用：资源分配

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

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

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

补充示例：

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

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

判断某灯的状态：

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

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

以二进制000101为例 当两个二进制都为0是为0，其余为1 &000110 --------------------------- 000111 比特位1比特位2结果101111011000 注：01也可以表示真假

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

实际场景应用：占用资源

将某段的状态设置为 1：

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

释放资源：

将某段的状态设置为 0：

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

示例：

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

开第 55 盏灯：

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

关第 22 盏灯：

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

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

公式：

n&(−n) 注：如果这里看不懂请复习数据在计算机的存储 1.负数在计算机中存储的是补码

实际场景应用：

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

示例：

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 注：想为2的n次幂说明只能比特位里面只能由一个1，其余均为0，（n&(n-1)）可以去除最后的1，所以可以判断

示例：

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

实际场景应用：判断一个数的奇偶

n&1==1为奇数 n&1==0为偶数

综合运算小技巧：如何让一个数更快的变为1，这个数不可以含有小数运算

偶数运算：n>>=1 奇数运算： (n==3),n++ 原因：011 减1化为010，位运算01 (n>3),n++ 原因：111 加1化为1000，位运算更方便 普通奇数, n--;

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 资源