C 位运算符全扩展技巧面试必背文章目录C 位运算符全扩展技巧面试必背[toc]一、基础位运算符回顾原码反码补码1. 对于**正数**和**0**二、⭐ 判断1.判断奇偶2. 判断 2 的幂3. 判断 符号是否相同4. 判断第 n 位是否为 1n 从 0 开始计数三、⭐ 修改1. 置 12. 置 03. 翻转4. ‼️ 把最低位的 1置05. 保留最低位的 1其他位全部清零为什么必须用 long long6. ‼️交换两个整数四、数学1. 乘 2 的 n 次方2. 除以 2 的 n 次方仅适用于正数3. 对 2 的 n 次方取模4. 求整数的绝对值不用 if 分支五、算法类技巧面试高频1. 二进制中 1 的个数2. 加法3. 缺失的数字4. 只出现一次的数字系列七、重要注意事项必看坑面试必背速查表一、基础位运算符回顾原码反码补码数值原码反码补码50000 01010000 0101正数与原码相同0000 0101正数与原码相同-51000 0101最高位1表示负和5同1111 1010符号位不变其余位取反1111 1011反码 100000 0000或1000 0000存在0和-00000 0000或1111 1111同样两个00000 0000唯一零-0的补码也是01. 对于正数和**0**原码 反码 补码符号位为0数值位不变。内存中数字以32位数存储原反补的关系原码二进制数字前面加上1负数或0整数反码原码除了表示正负号的第一位不变其他都取反补码反码1➡️内存中储存并使用的形式**-1是全1**对于负数补码和原码相互是取反加一的关系当然第一位代表符号不看有符号整型signed int)整数原反补相同负数原反补都不同无符号整型(unsigned int)都相同6的原码反码补码0000000000000000000001103的原码反码补码000000000000000000000011-5的原码100000000000000000000101-5的反码111111111111111111111010-5的补码111111111111111111111011运算符名称运算规则例子十进制例子二进制按位与全 1 为 1有 0 为 06 3 2110 011 010按位或有 1 为 1全 0 为 06^按位异或相同为 0相异为 16 ^ 3 5110 ^ 011 101~按位取反0 变 11 变 0~6 -7补码表示左移所有位左移 n 位低位补 06 1 12110 1 1100右移所有位右移 n 位高位补符号位6 1 3110 1 011二、⭐ 判断1.判断奇偶判断最后一位是0是1boolis_odd(intx){returnx1;}2. 判断 2 的幂判断一个数的二进制位是否只有一个1boolis_power_of_two(intx){returnx0(x(x-1))0;}例子8 7 0是6 5 4不是原理2 的幂的二进制只有一个 1减 1 后所有低位都变成 1与运算结果为 0对应 LeetCode231. 2 的幂3. 判断 符号是否相同整体数字异或只看结果的符号位同0正数异1负数boolsame_sign(intx,inty){return(x^y)0;}例子3 ^ 5 6 0同号3 ^ (-5) -8 0异号4. 判断第 n 位是否为 1n 从 0 开始计数boolis_bit_set(intx,intn){return(xn)1;}三、⭐ 修改1. 置 1intset_bit(intx,intn){returnx|(1n);}例子set_bit(4, 1) 6100 | 010 1102. 置 0intclear_bit(intx,intn){returnx~(1n);}例子clear_bit(6, 1) 4110 101 1003. 翻转异或同0异1int toggle_bit(int x, int n) { return x ^ (1 n); }例子toggle_bit(6, 0) 7110 ^ 001 1114. ‼️ 把最低位的 1置0intclear_lowest_one(intx){returnx(x-1);}例子6 5 4110 → 100最低位的 1 被清零核心用途统计二进制中 1 的个数判断 2 的幂求最大公约数5. 保留最低位的 1其他位全部清零// 注意用long long避免INT_MIN溢出longlongget_lowest_one(longlongx){returnx(-x);}例子 1正数 6二进制 0110x 6 → 0000 0110 补码~6 1 1111 1001 1 1111 1010 -x补码 ~-6 1 ~1000 01101 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 11001 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) 2110 → 010为什么必须用 long longINT_MIN 的坑int的最小值是INT_MIN -2147483648它的二进制是1000 0000 ... 0000只有最高位是 1x INT_MIN → 1000 0000 ... 0000 -x 2147483648 → 这个数超过了int的最大值2147483647溢出了溢出在 C 里是未定义行为不同编译器结果不一样。用long long就不会有这个问题因为 long long 的范围大得多。6. ‼️交换两个整数voidswap(inta,intb){a^b;b^a;//相当于b ^ a ^ b结果是 aa^b;//相当于a ^ a ^ b结果是 b}四、数学1. 乘 2 的 n 次方intmultiply_by_power_of_two(intx,intn){returnxn;}例子3 2 123 * 4 122. 除以 2 的 n 次方仅适用于正数intdivide_by_power_of_two(intx,intn){returnxn;}例子12 2 312 / 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((1n)-1);}例子10 % 4 2→10 3 2原理2 的 n 次方减 1 的二进制是 n 个 1与运算就相当于取后 n 位4. 求整数的绝对值不用 if 分支intabs(intx){intmaskx31;return(x^mask)-mask;}原理正数的 mask 是 0结果还是 x负数的 mask 是 - 1全 1(x ^ mask)取反x ^ (-1)相当于按位取反(x ^ mask) - mask;**加一**减 - 1 相当于加 1就是补码转原码五、算法类技巧面试高频1. 二进制中 1 的个数用到了上面的‼️ 把最低位的 1置0intcount_ones(intx){intcount0;while(x){xx-1;// 每次清零最低位的1count;}returncount;}时间复杂度O (k)k 是 1 的个数比循环 32 次快得多2. 加法intadd(inta,intb){while(b){intcarry(unsignedint)(ab)1;// 计算进位a^b;// 无进位加法bcarry;}returna;}原理异或^做无进位加法与左移 1 位做进位循环直到进位为 03. 缺失的数字所有出现两次的数都会抵消剩下的就是缺失的数intmissingNumber(vectorintnums){intresnums.size();for(inti0;inums.size();i){res^i^nums[i];}returnres;}4. 只出现一次的数字系列一个数出现一次其他出现两次全部异或两个数出现一次其他出现两次先全部异或再用最低位的 1 分组异或一个数出现一次其他出现三次统计每一位 1 的个数模 3七、重要注意事项必看坑有符号数右移是算术右移高位补符号位负数右移结果和除法不同左移溢出是未定义行为不要左移超过类型的位数1 n是 int 类型需要 64 位时用1LL nx (-x)对 INT_MIN 有效但结果是 INT_MIN 本身必须用 long long 避免溢出面试必背速查表常用技巧核心公式主要用途判断奇数x 1所有需要判断奇偶的地方清零最低位的 1x (x - 1)统计 1 的个数、判断 2 的幂保留最低位的 1x (-x)分组、树状数组统计 1 的个数Brian Kernighan 算法位运算基础题不用临时变量交换异或三次面试经典题不用加减乘除加法异或 与左移面试高频题