1. 基础位运算与有0就是0。或|有1就是1。非~按位取反。异或^相同为0相异为1可以理解为无进位相加。2. 特定位的检查与修改检查第 x 位是 0 还是 1公式(n x) 1解释将 n 右移 x 位再与 1 进行与运算。结果为 1 则原位为 1为 0 则原位为 0。将第 x 位修改为 1公式n | (1 x)解释构造一个只有第 x 位为 1 的数1 x与原数进行或运算。将第 x 位修改为 0公式n (~(1 x))解释将1 x取反得到一个除了第 x 位是 0 其余全是 1 的面具与原数进行与运算从而清零第 x 位。3. 位图 (Bitmap) 思想利用整数数组来模拟位数组。应用场景状态压缩、布隆过滤器、海量数据处理如 int 数组的每个 bit 可以表示一个数据的存在与否。4. 常用技巧公式提取最右侧的 1 (lowbit)公式n -n作用得到 n 中最右边那个 1 及其右边的所有 0 组成的数。常用于树状数组 (Fenwick Tree) 或统计二进制中 1 的个数。干掉最右侧的 1公式n (n - 1)作用将 n 的最右边那个 1 变成 0。常用于判断一个数是否是 2 的幂如果是则n (n-1) 0或用于统计二进制中 1 的个数。5. 运算优先级位运算的优先级普遍较低且容易混淆。建议在实际编程中能加括号就加括号避免因优先级问题导致逻辑错误。6. 异或 (XOR) 运算律a ^ 0 a0 是异或的单位元a ^ a 0自己异或自己等于 0常用于“消消乐”a ^ b ^ c a ^ (b ^ c)满足结合律特性交换律。1.判断字符是否唯一面试题 01.01. 判定字符是否唯一实现一个算法确定一个字符串s的所有字符是否全都不同。class Solution { public: bool isUnique(string astr) { if(astr.size()26) return false;//鸽巢原理 int bitMap0; for(auto e:astr) { int ie-a; if(((bitMapi)1)1)return false; else bitMap|(1i); } return true; } };2.只出现一次的数字系列136. 只出现一次的数字https://leetcode.cn/problems/single-number/给你一个 非空 整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。class Solution { public: int singleNumber(vectorint nums) { int i0; for(auto e:nums) { ii^e; } return i; } };137. 只出现一次的数字 IIhttps://leetcode.cn/problems/single-number-ii/给你一个整数数组nums除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题class Solution { public: int singleNumber(vectorint nums) { int bitMap0; for(int i0;i32;i) { int sum0; for(auto e:nums) { if(((ei)1)1) sum; } sum%3; if(sum1) bitMapbitMap|(1i); } return Map; } };260. 只出现一次的数字 IIIhttps://leetcode.cn/problems/single-number-iii/给你一个整数数组nums其中恰好有两个元素只出现一次其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题class Solution { public: int getfirst1(int i) { int index0; while((i1)0index32) { i1; index; } return index; } vectorint singleNumber(vectorint nums) { if(nums.size()2) return nums; int i0; for(auto e:nums) { i^e; //x1^x2 } int x10,x20; int indexgetfirst1(i); for(auto ch:nums) { if(((chindex)1)0) x1^ch; else x2^ch; } return {x1,x2}; } };3.位1的个数LCR 133. 位 1 的个数https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/编写一个函数输入是一个无符号整数以二进制串的形式返回其二进制表达式中数字位数为 1 的个数也被称为 汉明重量).。class Solution { public: int hammingWeight(uint32_t n) { int count0,index0; while(index32) { if(n11)count; n1; index; } return count; } };4.比特位计数LCR 003. 比特位计数https://leetcode.cn/problems/w3tCBm/给定一个非负整数n请计算0到n之间的每个数字的二进制表示中 1 的个数并输出一个数组class Solution { public: int hammingWeight(int n) { int count0,index0; while(index32) { if((n1)1)count; n1; index; } return count; } vectorint countBits(int n) { int i0;vectorint v;; while(in) { v.emplace_back(hammingWeight(i)); } return v; } };5.汉明距离461. 汉明距离https://leetcode.cn/problems/hamming-distance/两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数x和y计算并返回它们之间的汉明距离。class Solution { public: int hammingDistance(int x, int y) { int count0,index0; while(index32) { if((x1)!(y1)) count; index;x1;y1; } return count; } };6.丢失的数字268. 丢失的数字https://leetcode.cn/problems/missing-number/给定一个包含[0, n]中n个数的数组nums找出[0, n]这个范围内没有出现在数组中的那个数class Solution { public: int missingNumber(vectorint nums) { int sum0; for(auto e:nums)sum^e; for(int i0;inums.size();i)sum^i; return sum; } };7.两整数之和371. 两整数之和https://leetcode.cn/problems/sum-of-two-integers/给你两个整数a和b不使用 运算符和-计算并返回两整数之和。class Solution { public: int getSum(int a, int b) { u_int c1,d; while(c!0) { cab;c1; da^b; ac;bd; } return d; } };8.消失的两个数字面试题 17.19. 消失的两个数字https://leetcode.cn/problems/missing-two-lcci/给定一个数组包含从 1 到 N 所有的整数但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗class Solution { public: int getfirst1(int i) { int index0; while((i1)0index32) { index; i1; } return index; } vectorint missingTwo(vectorint nums) { int ch0; for(int i1;inums.size()2;i) { ch^i; } for(auto e:nums) { ch^e; } //得到两个数字的异或 int f1getfirst1(ch); int x10,x20; for(auto e:nums) { if(((ef1)1)0) x1^e; else x2^e; } for (int i 1; i nums.size()2 ; i) { if (((if1)1) 0) x1 ^ i; else x2 ^ i; } return{x1,x2}; } };