在计算机中所有数据都是以二进制形式进行存储, 而位运算就是直接对内存中的二进制数据进行操作, 因此处理速度非常快.
1. 基本操作
运算符 | 用法示例 | 运算规则 |
按位与 AND | a & b | 只有两个操作数相应的比特位都为 1 时,结果才为 1,否则为 0 |
按位或 OR | a | b | 只有两个操作数相应的比特位都为 0 时,结果才为 0,否则为 1 |
按位异或 XOR | a ^ b | 两个操作数相应比特位不相同时,结果为 1,否则为 0 |
按位取反 NOT | ~a | 操作数相应比特位取反,0 变为 1, 1 变为 0 |
左移 | a << b | 将 a 的二进制形式向左移 b 个 bit,右侧填充 0 |
右移 | a >> b | 将 a 的二进制形式向右移 b 个 bit,有符号数逻辑移位,无符号数算术移位 |
C/C++ 中移位运算包含逻辑移位 (Logical shift) 和算术移位 (Arithmetic shift) 两种, 其中逻辑移位的意思是, 移出去的位直接舍弃, 空缺位用 0 填充; 算术移位的意思是, 移出去的位直接舍弃, 空缺位用符号位填充.
对于无符号数, 无论是左移还是右移都是逻辑移位, 如 0011 0110 左移两位结果为 1101 1000, 右移两位结果为 0000 1101.
对于有符号数, 左移仍然是逻辑移位, 右移则略有不同, 进行的是算术移位, 如 1011 0110 左移两位结果为 1101 1000, 右移两位结果为 1110 1101(前面两位填充的是符号位 1).
2. 常见应用
对 n 的指定位进行操作, 其它位保持不变.
- n &= ~(1 <<5); // 1 左移 5 位得到 0010 0000, 按位取反得 1101 1111, 与 n 按位与使其第 6 位被清零, 其它位不变
- n |= (1 << 5); // 1 左移 5 位得到 0010 0000, 与 n 按位或使其第 6 位被置 1, 其它位不变
- n ^= (1 << 5); // 将 n 第 6 位取反, 其它位不变
判断给定正整数 n 的奇偶
1 1 bool flag = a & 1; // a 对应二进制数末位为 0 则为偶数, 否则为奇数. 相比 bool flag = (a % 2 == 0); 运算速度快了很多.
判断 n 是否为 2 的正整数次幂
- 1 /*===============================================================================================
- 2 * 将 2 的次幂写成二进制容易发现, 二进制中只有一个 1, 后面跟了 n 个 0.
- 3 * 如果将这个数减 1, 仅有的一个 1 变成了 0, 后面的 n 个 0 变成了 1. 时间复杂度 O(1).
- 4 *===============================================================================================
- */
- 5 bool isPowerOfTwo(int n) {
- 6 return (n & (n - 1) == 0);
- 7 }
- /*==============================================================================================
- * 常规思路: 利用循环判断 n 是否能被 2 整除, 如果是除以 2, 继续循环.
- * 最终结果若为 1 则表明其是 2 的正整数次幂, 否则不是. 时间复杂度 O(log n).
- *==============================================================================================
- */
- bool isPowerOfTwo(int n) {
- while (n % 2 ==0) {
- n /= 2;
- }
- return (n == 1);
- }
统计给定正整数的二进制中 1 的个数
- /*==============================================================================================
- * 与上述判断 n 是否为 2 的正整数次幂时相似, n&(n -1) 作用是将 n 的二进制中最右边的 1 置为 0, 如此循环以统计 n 中 1 的个数
- *==============================================================================================
- */
- int count1Bit(int n) {
- int countOneBit = 0;
- while (n) {
- countOneBit ++;
- n &= n -1;
- }
- return countOneBit;
- }
- /*==============================================================================================
- * 另一种四步分组法, 以 34520(1000011011011000)为例
- * 第一步: 每 2 位为一组, 组内高低位相加.
- * 10 00 01 10 11 01 10 00 -> 01 00 01 01 10 01 01 00
- * (10 高位为 1, 低位为 0, 相加得 01;11 高位为 1, 低位也为 1, 相加得 10......).
- * 第二步: 将第一步得到的结果每 4 位分为一组, 组内高低位相加.
- * 0100 0101 1001 0100 -> 0001 0010 0011 0001
- * (0100 高位为 01 低位为 00, 相加得 01;1001 高位为 10 低位为 01, 相加得 11......).
- * 第三步: 将第二步得到的结果每 8 位分为一组, 组内高低位相加.
- * 00010010 00110001 -> 00000011 00000100.
- * 第四步: 将第三步得到的结果每 16 位分为一组, 组内高低位相加.
- * 0000001100000100 -> 00000111.
- * 这样最后得到的结果 7 即为给定整数中 1 的个数.
- *==============================================================================================
- */
- int count1Bit(int n) {
- n = ((n & 0xAAAA)>> 1) + (n & 0x5555);
- n = ((n & 0xCCCC)>> 2) + (n & 0x3333);
- n = ((n & 0xF0F0)>> 4) + (n & 0x0F0F);
- n = ((n & 0xFF00)>> 8) + (n & 0x00FF);
- return n;
- }
不需要额外变量交换两个整数的值
- void Swap(int &m, int &n) {
- if ( m != n ) {
- m ^= n; // m = (m ^ n)
- n ^= m; // n = n ^ (m ^ n) = n ^ m ^ n = n ^ n ^ m =m, 一个数和自身异或结果为 0, 一个数和 0 异或结果为其自身
- m ^= n; // m = m ^ n = m ^ n ^ m = n
- }
- }
- void Swap(int &m, int &n) {
- if ( m != n ) {
- int temp = a; // 常规思路: 借由中间变量实现交换.
- a = b;
- b = temp;
- }
- }
16 位无符号整型数高低位交换
- /*=========================================================================================
- * 对于 16 位无符号整型数据, 分为高 8 位和低 8 位, 高八位右移时高位填充 0, 低八位左移时末位填充 0, 将两者相加即可.
- *=========================================================================================
- */
- unsigned int lowHighExchange(unsigned int n) {
- return ((a>> 8) + (a <<8));
- }
二进制逆序操作
- /*========================================================================================
- * 通过四步分组法得到 16 位整型数据的二进制逆序. 以 34520(1000 0110 1101 1000)为例,
- * 第一步: 每 2 位为一组, 组内高低位交换.
- * 10 00 01 10 11 01 10 00->01 00 10 01 11 10 01 00.
- * 第二步: 每 4 位为一组, 组内高低位交换. 0100 1001 1110 0100 -> 0001 0110 1011 0001.
- * 第三步: 每 8 位为一组, 组内高低位交换. 00010110 10110001 -> 01100001 00011011.
- * 第四步: 每 16 位为一组, 组内高低位交换. 0110000100011011 -> 00011011 01100001.
- * 改进: 对第一步先分别取原数据的奇数位和偶数位
- * 空位以下划线表示: 1_0_0_1_1_0_1_0_, _0_0_1_0_1_1_0_0,
- * 将下划线填充 0 得原数 1000 0110 1101 1000
- * 奇数位 1000 0010 1000 1000, 偶数位 0000 0100 0101 0000
- * 再将奇数位右移一位, 偶数位左移一位, 将移位后的两数按位或可使奇偶位数据交换.
- * 原数 1000 0110 1101 1000, 奇数位右移一位 0100 0001 0100 0100
- * 偶数位左移一位 0000 1000 1010 0000, 按位或得 0100 1001 1110 0111
- *=======================================================================================
- */
- int binaryReverse( int n ) {
- n = ((n & 0xAAAA)>> 1) | ((a & 0x5555) <<1);
- n = ((n & 0xCCCC)>> 2) | ((a & 0x3333) <<2);
- n = ((n & 0xF0F0)>> 4) | ((a & 0x0F0F) <<4);
- return (((n & 0xFF00)>> 8) | ((a & 0x00FF) << 8));
- }
3. 拓展应用
题目: 不使用加减乘除四则运算实现两个正整数相加.
解析: 首先理解十进制加法工作原理, 主要分为三步, 以 4+9 为例: 1)相加相应位的值, 不算进位, 得 3;2)计算进位值, 得 10, 如果进位值为 0 则第一步得到的就是最终结果; 3)把前两步的结果相加, 重复此过程得结果 13.
再来看二进制相加过程. 1)相加相应位的值, 不算进位, 100 + 1001, 得 1101;2)计算进位值, 得 0000, 如果进位为 0 则第一步得到的就是最终结果; 3)把前两步的结果相加, 重复此过程的结果 1101.
- /*==================================================================================================
- * 相加相应位的值可按位异或, 因为如果不考虑进位的和, 只有 0+1 或者 1+0 才是 1, 刚好符合异或的性质: 0100 ^ 1001 = 1101
- * 计算进位可使用按位与, 因为只有 1+1 才会发生进位并需要将这个进位左移 1 位: (0100 & 1001) << 1 = 0000
- * 然后一直循环直到进位为 0, 此时的结果就是输入两数之和了.
- *==================================================================================================
- */
- int Add(int num1, int num2) {
- return num2 ? Add(num1 ^ num2, (num1 & num2)<<1) : num1; }
题目: 给定一个非空整数数组, 其中有一个元素只出现一次, 其它元素均出现两次, 请找出只出现一次的元素.(要求实现算法具有线性时间复杂度, 并且不实用额外空间)
示例: 输入[2, 2, 1], 输出 1. 输入[3, 1, 2, 3, 1], 输出 2.
解析: 由于要求时间复杂度 O(n), 空间复杂度 O(1), 不能用排序, 也不能使用 map. 考虑使用位操作运算求解. 因为任何数与自身异或结果为 0, 任何数与 0 异或结果为其自身, 将所有元素做异或运算, 即 a[1]⊕a[2]⊕...⊕a[n], 那么结果就是只出现一次的元素, 时间复杂度 O(n). 过程如下图:
题目: 给定一个非空整数数组, 其中有两个元素只出现一次, 其它元素均出现两次, 请找出只出现一次的两个元素.(要求实现算法具有线性时间复杂度, 而且只能开辟固定大小的内存空间, 即与 n 无关)
示例: 输入[1, 2, 2, 1, 3, 4], 输出[3, 4].
解析: 根据前面找一个不同数的思路, 如果这里再把所有元素异或, 得到的结果是只出现一次的两个元素异或得到的值. 然后由于这两个只出现一次的元素一定不相同, 那么这两个元素的二进制形式肯定至少有一位不同, 即 1 个为 0, 另一个为 1, 先在需要找出这一位. 根据异或的性质: 任何数与自身异或结果为 0, 得到这个数字二进制形式中任意一个为 1 的位都是我们要找的. 之后以这一位是 0 还是 1 为标准, 将数组的 n 个元素分成两部分. 将这一位为 0 的所有元素异或得到的结果就是只出现一次的两个元素中的一个. 将这一位为 1 的所有元素异或得到的结果就是只出现一次的两个元素中的另一个. 如果忽略寻找不同位的过程, 公遍历数组两次, 时间复杂度 O(n). 过程如下图:
Reference:
[1] https://www.cnblogs.com/zhoug2020/p/4978822.html
[2] https://blog.csdn.net/qq_16137569/article/details/82790378
[3] https://www.cnblogs.com/thrillerz/p/4530108.html
[4] https://www.cnblogs.com/fivestudy/p/10275446.html
[5] https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
来源: https://www.cnblogs.com/phillee/p/10540512.html