我们先来整理一下常见的C位运算符号以及作用运算符名称描述示例 (a5, b3)与​两位都为1时结果才为1101 011 001(1)\|或​两位有一个为1时结果就为1101 \| 011 111(7)^异或​两位相异时结果为1101 ^ 011 110(6)~取反​按位取反0变11变0~00000101 11111010(-6)左移​将二进制位全部左移若干位高位丢弃低位补05 1 1010(10)右移​将二进制位全部右移若干位低位丢弃高位补符号位算术右移5 1 10(2)下面介绍一些实用的位运算技巧1判断奇偶性示例if (x 1) { // 奇数 } else { // 偶数 }原理二进制最后一位为奇数为1为偶数为0。2取出二进制最右边的1示例int lowbit x -x;原理-x是x的补码等于~x 1。这个操作会将x最右边的 1 保留其余位都变成 0。应用1树状数组2统计二进制中 1 的个数。3消除二进制的最右边的 1示例int count 0; while (x ! 0) { x x (x - 1); count; }原理x-1会把x最右边的 1 变成 0而该位右边的所有 0 都变成 1。相与后最右边的 1 就被消掉了。应用1判断一个数是否是2的幂2的幂的二进制表示中只有一位是1。(x (x-1)) 0。2计算一个数的二进制表示中 1 的个数。4异或的性质1.归零x ^ x 02.恒等x ^ 0 x3.交换律和结合律a ^ b ^ c a ^ (b ^ c)4.自反a ^ b ^ a b示例1不使用临时变量交换两个变量a a ^ b; b a ^ b; a a ^ b;2找出数组中只出现一次的数字问题一个非空整数数组除了某个元素只出现一次外其余每个元素均出现两次。找出那个只出现一次的元素。解法将所有数字进行异或操作成对的数字会异或为0最后剩下的就是只出现一次的数字。int singleNumber(vectorint nums) { int res 0; for (int num : nums) { res ^ num; } return res; }5掩码掩码是一个用于标识、设置或清除特定位模式的二进制数。1.获取第n位int bit (x n) 1;2.将第n位设置为1x x | (1 n);3.将第n位设置为0x x ~(1 n);4.将第n位取反x x ^ (1 n);5.乘/除2的幂用移位代替乘除法效率比乘除法高int a 10; int b a 2; // b 40 //(10 * 4) int c a 1; // c 5 //(10 / 2)例题算法思路使用位图来记录每个字符是否出现过利用一个整数的二进制位作为标记位。如果字符串长度超过26英文字母总数根据鸽巢原理必定有重复字符直接返回false。然后用一个int变量map作为位图初始值为0每个二进制位代表一个字母是否出现过。之后遍历字符串对每个字符计算它在字母表中的位置i ch - a检查位图的第i位(map i) 1如果为1则重复返回false。如果遍历成功则没有重复返回ture。class Solution { public: bool isUnique(string astr) { if(astr.size() 26) { return false; } int map 0; for(auto ch : astr) { int i ch - a; if(((map i) 1) 1) return false; map | 1 i; } return true; } };消失的两个数字算法思路先将数组中的数和 [1, n 2] 区间内的所有数「异或」在⼀起问题就变成了有两个数出 现了「⼀次」其余所有的数出现了「两次」。就变成了上述找出只出现一个数字的例题。class Solution { public: vectorint missingTwo(vectorint nums) { int tmp 0; for(auto x : nums) { tmp ^ x; } for(int i 1;i nums.size()2;i) { tmp ^ i; } int diff 0; while(1) { if((tmp diff) 1 1) { break; } else { diff; } } int a 0,b 0; for(auto x : nums) { if((x diff) 1 1) { b ^ x; } else { a ^ x; } } for(int i 1;i nums.size()2;i) { if((i diff) 1 1) { b ^ i; } else { a ^ i; } } return {a,b}; } };示例演示 假设数组为[1, 2, 4, 5]缺失3和6 第一步tmp 1^2^4^5 ^ 1^2^3^4^5^6 3^6 5二进制101 第二步找到第0位为1两个缺失数字在第0位不同 第三步按第0位分组最终得到a3b6