【位运算符】爆肝整理！C++位运算从入门到精通（面试必背），原反补+奇技淫巧，手撕算法题就靠它！

C++ 位运算符全扩展技巧（面试必背）

文章目录

• C++ 位运算符全扩展技巧（面试必背）
• • @[toc]
  • 一、基础位运算符回顾
  • • 原码，反码，补码
    • 1. 对于**正数**和**+0**
  • 二、⭐ 判断
  • • 1.判断奇偶
    • 2. 判断 2 的幂
    • 3. 判断 符号是否相同
    • 4. 判断第 n 位是否为 1（n 从 0 开始计数）
  • 三、⭐ 修改
  • • 1. 置 1
    • 2. 置 0
    • 3. 翻转
    • 4. ‼️ 把最低位的 1置0
    • 5. 保留最低位的 1，其他位全部清零
    • • 为什么必须用 long long？
    • 6. ‼️交换两个整数
  • 四、数学
  • • 1. 乘 2 的 n 次方
    • 2. 除以 2 的 n 次方（仅适用于正数）
    • 3. 对 2 的 n 次方取模
    • 4. 求整数的绝对值（不用 if 分支）
  • 五、算法类技巧（面试高频）
  • • 1. 二进制中 1 的个数
    • 2. 加法
    • 3. 缺失的数字
    • 4. 只出现一次的数字系列
  • 七、重要注意事项（必看坑）
  • 面试必背速查表

一、基础位运算符回顾

原码，反码，补码

1. 对于正数和**+0**

• 原码 = 反码 = 补码（符号位为0，数值位不变）。

内存中，数字以32位数存储

原反补的关系

原码：二进制数字，前面加上1（负数）或0（整数）

反码：原码除了表示正负号的第一位不变，其他都取反

补码：反码+1➡️内存中储存并使用的形式**（-1是全1）**

对于负数：补码和原码相互是取反加一的关系，当然，第一位代表符号，不看

1. 有符号整型（signed int)
   1. 整数：原反补相同
   2. 负数：原反补都不同
2. 无符号整型(unsigned int)：都相同

6的原码，反码，补码：000000000000000000000110

3的原码，反码，补码：000000000000000000000011

-5的原码：100000000000000000000101

-5的反码：111111111111111111111010

-5的补码：111111111111111111111011

二、⭐ 判断

1.判断奇偶

• 判断最后一位是0是1

boolis_odd(intx){returnx&1;}

2. 判断 2 的幂

• 判断一个数的二进制位是否只有一个1

boolis_power_of_two(intx){returnx>0&&(x&(x-1))==0;}

• 例子：8 & 7 = 0（是），6 & 5 = 4（不是）
• 原理：2 的幂的二进制只有一个 1，减 1 后所有低位都变成 1，与运算结果为 0
• 对应 LeetCode：231. 2 的幂

3. 判断 符号是否相同

• 整体数字异或，只看结果的符号位：同0（正数）异1（负数）

boolsame_sign(intx,inty){return(x^y)>=0;}

• 例子：3 ^ 5 = 6 >= 0（同号），3 ^ (-5) = -8 < 0（异号）

4. 判断第 n 位是否为 1（n 从 0 开始计数）

boolis_bit_set(intx,intn){return(x>>n)&1;}

三、⭐ 修改

1. 置 1

intset_bit(intx,intn){returnx|(1<<n);}

• 例子：set_bit(4, 1) = 6（100 | 010 = 110）

2. 置 0

intclear_bit(intx,intn){returnx&~(1<<n);}

• 例子：clear_bit(6, 1) = 4（110 & 101 = 100）

3. 翻转

• 异或：同0异1

int toggle_bit(int x, int n) { return x ^ (1 << n); }

• 例子：toggle_bit(6, 0) = 7（110 ^ 001 = 111）

4. ‼️ 把最低位的 1置0

intclear_lowest_one(intx){returnx&(x-1);}

• 例子：6 & 5 = 4（110 → 100，最低位的 1 被清零）

• 核心用途：

  • 统计二进制中 1 的个数
  • 判断 2 的幂
  • 求最大公约数

5. 保留最低位的 1，其他位全部清零

// 注意：用long long避免INT_MIN溢出longlongget_lowest_one(longlongx){returnx&(-x);}

例子 1：正数 6（二进制 0110）

x = 6 → 0000 0110 （补码：~6 + 1 = 1111 1001 + 1 = 1111 1010） （-x补码： ~（-6） + 1 = ~（1000 0110）+1 = 1111 1001 + 1 = 1111 1010） -x = -6 → 1111 1010 x & (-x) → 0000 0010 = 2

✅ 结果是 2，正好是 6 最低位的 1（第 1 位）

x = 12 → 0000 1100 （-x补码： ~（-12） + 1 = ~（1000 1100）+1 = 1111 0011 + 1 = 1111 0100） -x = -12 → 1111 0100 x & (-x) → 0000 0100 = 4

✅ 结果是 4，正好是 12 最低位的 1（第 2 位）。

x = -6 → 1111 1010 （-x补码： 就是6 ） -x = 6 → 0000 0110 x & (-x) → 0000 0010 = 2

✅ 结果还是 2，和正数 6 一样，因为最低位的 1 的位置没变。

• 例子：6 & (-6) = 2（110 → 010）

为什么必须用 long long？

（INT_MIN 的坑）

int的最小值是INT_MIN = -2147483648，它的二进制是1000 0000 ... 0000（只有最高位是 1）

x = INT_MIN → 1000 0000 ... 0000 -x = 2147483648 → 这个数超过了int的最大值（2147483647），溢出了！

溢出在 C++ 里是未定义行为，不同编译器结果不一样。用long long就不会有这个问题，因为 long long 的范围大得多。

6. ‼️交换两个整数

voidswap(int&a,int&b){a^=b;b^=a;//相当于b ^ a ^ b结果是 aa^=b;//相当于a ^ a ^ b结果是 b}

四、数学

1. 乘 2 的 n 次方

intmultiply_by_power_of_two(intx,intn){returnx<<n;}

• 例子：3 << 2 = 12（3 * 4 = 12）

2. 除以 2 的 n 次方（仅适用于正数）

intdivide_by_power_of_two(intx,intn){returnx>>n;}

• 例子：12 >> 2 = 3（12 / 4 = 3）
• 坑：负数右移是算术右移，结果和除法不同（-5 >> 1 = -3而不是-2）

-5的二进制：1111 1011 算术右移1位：1111 1101 = -3

而数学上-5 / 2 = -2.5，向零取整是-2。

✅ 所以-5 >> 1 = -3，不等于-5 / 2 = -2。

3. 对 2 的 n 次方取模

x % (2^n)

intmod_power_of_two(intx,intn){returnx&((1<<n)-1);}

• 例子：10 % 4 = 2→10 & 3 = 2
• 原理：2 的 n 次方减 1 的二进制是 n 个 1，与运算就相当于取后 n 位

4. 求整数的绝对值（不用 if 分支）

intabs(intx){intmask=x>>31;return(x^mask)-mask;}

• 原理：
  • 正数的 mask 是 0，结果还是 x；
  • 负数的 mask 是 - 1（全 1），
    • (x ^ mask)取反：x ^ (-1)相当于按位取反
    • (x ^ mask) - mask;**加一：**减 - 1 相当于加 1，就是补码转原码

五、算法类技巧（面试高频）

1. 二进制中 1 的个数

用到了上面的‼️ 把最低位的 1置0

intcount_ones(intx){intcount=0;while(x){x&=x-1;// 每次清零最低位的1count++;}returncount;}

• 时间复杂度：O (k)，k 是 1 的个数，比循环 32 次快得多

2. 加法

intadd(inta,intb){while(b){intcarry=(unsignedint)(a&b)<<1;// 计算进位a^=b;// 无进位加法b=carry;}returna;}

• 原理：

  • 异或^做无进位加法
  • 与&左移 1 位做进位
  • 循环直到进位为 0

3. 缺失的数字

所有出现两次的数都会抵消，剩下的就是缺失的数

intmissingNumber(vector<int>&nums){intres=nums.size();for(inti=0;i<nums.size();i++){res^=i^nums[i];}returnres;}

4. 只出现一次的数字系列

• 一个数出现一次，其他出现两次：全部异或
• 两个数出现一次，其他出现两次：先全部异或，再用最低位的 1 分组异或
• 一个数出现一次，其他出现三次：统计每一位 1 的个数，模 3

七、重要注意事项（必看坑）

1. 有符号数右移是算术右移：高位补符号位，负数右移结果和除法不同
2. 左移溢出是未定义行为：不要左移超过类型的位数
3. 1 << n是 int 类型：需要 64 位时用1LL << n
4. x & (-x)对 INT_MIN 有效：但结果是 INT_MIN 本身，必须用 long long 避免溢出

面试必背速查表