位运算技巧总结.docxVIP

位运算技巧总结

一、位运算基础概述

位运算是指对二进制数的位进行操作的运算，主要包括与（）、或（|）、异或（^）、非（~）、左移（）、右移（）等。位运算具有高效、简洁的特点，常用于算法优化、数据加密、位图处理等领域。

（一）基本运算定义

1.与运算（）：两数按位与，若对应位都为1，则结果为1，否则为0。

示例：53→5（二进制101）3（二进制011）→1（二进制001）

2.或运算（|）：两数按位或，若对应位至少有一个为1，则结果为1，否则为0。

礅例：5|3→5（二进制101）|3（二进制011）→7（二进制111）

3.异或运算（^）：两数按位异或，若对应位不同，则结果为1，否则为0。

示例：5^3→5（二进制101）^3（二进制011）→6（二进制110）

4.非运算（~）：单数按位取反，即0变1，1变0。注意：非运算是单目运算。

示例：~5→5（二进制101）取反→-6（补码表示）

5.左移运算（）：将二进制位向左移动指定位数，右补0。

示例：51→5（二进制101）左移1位→10（二进制1010）

6.右移运算（）：将二进制位向右移动指定位数，符号位右补。

示例：51→5（二进制101）右移1位→2（二进制10）

（二）位运算性质

1.交换律：ab=ba；a|b=b|a

2.结合律：(ab)c=a(bc)；(a|b)|c=a|(b|c)

3.分配律：a(b|c)=(ab)|(ac)；a|(bc)=(a|b)(a|c)

4.零律：a0=0；a|1=a

5.自反律：aa=a；a|a=a

6.异或律：a^a=0；a^0=a；a^b^a=b

二、位运算常用技巧

（一）快速判断奇偶性

1.奇数：最低位为1，a1=1

2.偶数：最低位为0，a1=0

（二）翻转指定位

1.翻转第k位：a^(1k)

示例：翻转5（101）的第2位→5^(12)=5^4=1（二进制001）

（三）设置指定位

1.设置第k位为1：a|(1k)

示例：设置3（011）的第1位为1→3|(11)=3|2=7（二进制111）

（四）清除指定位

1.清除第k位（保留低k位）：a~(1k)

示例：清除4（100）的第2位→4~(12)=43=0（二进制000）

（五）提取指定位

1.提取第k位：((ak)1)

示例：提取5（101）的第2位→(52)1=11=1

（六）位运算优化

1.检查整数是否为2的幂：a(a-1)==0（仅当a为2^n时成立）

示例：8（1000）7（0111）=0，成立

2.计算整数二进制中1的个数（BrianKernighan算法）：

```

count=0

whilea:

a=a-1

count+=1

```

示例：5（101）→54=4（100）；43=0，count=2

三、位运算实际应用

（一）数据压缩与加密

1.位运算可用于高效存储数据，如用1位表示布尔值。

2.简单加密示例：a^key（异或密钥）解密需相同操作。

（二）算法优化

1.位运算常用于快速求和、查找等操作，如Fenwick树（二叉索引树）利用位运算实现。

2.示例：快速计算n的平方根（近似）可结合位运算分步处理。

（三）硬件交互

1.位运算用于配置寄存器，如设置GPIO引脚状态。

2.示例：a|=(13)表示点亮第3号LED。

四、总结

位运算通过直接操作二进制位实现高效计算，需熟练掌握基本运算与常用技巧。结合实际场景可显著提升代码性能与可读性。建议通过练习题巩固理解，如leetcode中的位运算题目。

二、位运算常用技巧（续）

（一）快速判断奇偶性（续）

1.奇数：整数的最低位（LeastSignificantBit,LSB）为1时，该数为奇数。可通过与1进行按位与（）操作快速判断。如果结果为1，则该数是奇数；如果结果为0，则该数是偶数。

原理：任何奇数在二进制表示中最低位一定是1，而偶数的最低位一定是0。因此，`a1`的结果直接反映了最低位的值。

示例：

判断5是否为奇数：5的二进制为`101`。计算`51`，即`1011`，结果为`1`。因此，5是奇数。

判断8是否为奇数：8的二进制为