复习 C 语言基础位运算操作符，补充位图思想及常用技巧（如提取最右侧 1、修改指定位）。通过多个 LeetCode 算法题实例，讲解如何利用位运算解决位计数、汉明距离、寻找只出现一次的数字及两整数之和等问题。内容涵盖原理分析与 C++ 代码实现，帮助读者深入理解位运算在算法中的应用。
在之前 C 语言的常用操作符学习中，我们已经了解了移位操作符：<<、>>，按位与：&，按位或：|，按位异或：^，按位取反：~。
接下来复习这些操作符的特点并补充一些在算法题中常用的使用方法。
1. 基础的位运算逻辑
<<和>>分别实现的是数据二进制位的左移和右移动
&进行两个操作数的运算时将两个数据的二进制位进行按位与运算，规则是相应位置两个二进制元素都为 1 时运算的结果才为 1，否则就为 0
|进行两个操作数的运算时将两个数据的二进制位进行按位或运算，规则是相应位置两个二进制元素都为 0 时运算的结果才为 0，否则就为 1
^进行两个操作数的运算时将两个数据的二进制位进行按位异或运算，规则是两个二进制元素不相同时运算的结果为 1，相同就为 0
以上位运算的操作符简单总结就是：
&：有 0 就为 0
|：有 1 就为 1
^：相同为 0，相异为 1
2. 给定一个数判定它的二进制表示是 0 还是 1
如果要从给定的数当中判断其二进制的第 x 位是 0 还是 1，其实就需要使用按位与运算符，之后再将该数的二进制进行右移 x 位，最后再将结果和常量 1 进行按位与&，最后如果结果为 1 就说明原来给定的数的二进制位第 x 位为 1，否则就为 0。
例如以下示例：
要判断数字 185 的二进制位当中的第四位是 1 还是 0 就使用以上描述的方式来求解
通过以上求解就可以看出其第四位是 1
那么以上表述的解决过程使用运算符表示就是：
(n>>x)&1 结果为 1 就表示对应的二进制位值为 1，否则就为 0
注：在此 x 为要查询的数字的二进制位置，n 表示对应的数字
3. 将一个数 n 的二进制表示第 x 位修改为 1
在此要将给定的数字 n 的二进制表示的第 x 位修改为 1 就需要使用到按位或和左移操作符，具体过程就是先将数字 1 使用左移操作符将其的二进制位左移 x 位，之后再得到的结果和要进行判定的数进行按位或 | 运算，这样就可以将原来的数字的二进制位第 x 位就被修改为 1
在以上的实现过程当中就使用到了按位或运算符的实现原理，当两个操作数有 1 时计算的结果就为 1。这就使得在原来给定的数二进制位当中的 x 位与 1 进行按位或运算时无论原来的是 1 还是 0 结果都会被修改为 1
例如以下示例：
那么以上表述的解决过程使用运算符表示就是：
n|=(1<<x)
注：在此 x 为要修改的数字的二进制位置，n 表示对应的数字
4. 将一个数 n 的二进制表示第 x 位修改为 0
在此要将给定的数字 n 的二进制表示的第 x 位修改为 0 就需要使用到按位与和左移操作符以及按位取反，具体过程就是先将数字 1 使用左移操作符将其的二进制位左移 x 位，之后再得到的结果和要进行按位取反，再将以上得到的结果和要进行判定的数进行按位与 & 运算，这样原来的数字的二进制位第 x 位就被修改为 0
在以上的实现过程当中就使用到了按位与运算符的实现原理，当两个操作数有 0 时计算的结果就为 0。在此我们使用按位与之前先使用了按位取反，这就使得除了第 x 位以外二进制表示都变成 1，x 位变成了 0，这就使得在原来给定的数二进制位当中的 x 位进行按位与运算时无论原来的是 x 位是 1 还是 0 结果都会被修改为 0
例如以下示例：
那么以上表述的解决过程使用运算符表示就是：
n&=(~(1<<x))
注：在此 x 为要修改的数字的二进制位置，n 表示对应的数字
5. 位图的思想
位图其实就是在哈希表的基础之上进一步优化出来的，在之前我们一般都是创建整型的数组来模拟哈希表，但当使用哈希表每个下标只需要表示其元素存在或者不存在时也就是元素的情况只有 0 或者 1 的情况时，并且当要存储的数据量很大时使用整型来创建数组所需的内存空间也很大，因此在这种情况之下为了能进行更好的优化就引出了位图。
在此位图的基本思想就是将每一个二进制位来表示原先的数组下标的元素是否存在，如果存在此时对应的二进制位的值就为 1，反之就为 0。这样一个整型变量就可以表示，此时一个整型变量就可以来表示 32 个元素是否存在。这样相比原来使用数组来模拟哈希表的情况就可以大大的节约空间。
6. 提取一个数 (n) 二进制表示中最右侧的 1
如果要提取出给定的一个数二进制表示当中最右侧的 1 就需要使用到以下的操作：
n&-n
以上进行的操作就是先将给定的 n 变为其的相反数之后再将得到的结果和原来的 n 进行按位与操作，这样最终得到的结果就可以将原来的二进制表示当中的最右侧的 1 提取出来。
那么以上的操作是具体是如何实现的，接下来就来看以下的示例
如果我们要将以上的 n 的二进制表示的最右侧的 1 提取出来，先将得到原来的相反数这个操作在二进制表示当中就是进行按位取反再加一
通过以上的图示就可以看出在进行按位取反和加 1 操作之后得到的结果和原先的 n 相比在二进制表示当中从最右侧的 1 左边的二进制相比原先的二进制都进行的取反，右侧的 0 保持不变。
以上得到的结果再和原来的 n 进行按位与就能得到原来 n 最右侧的 1。
7. 去掉一个数 (n) 二进制表示中最右侧的 1
如果要去掉出给定的一个数二进制表示当中最右侧的 1 就需要使用到以下的操作：
n&(n-1)
以上进行的操作就是先将给定的 n 减一之后再将得到的结果和原来的 n 进行按位与操作，这样最终得到的结果就可以将原来的二进制表示当中的最右侧的 1 去掉。
那么以上的操作是具体是如何实现的，接下来就来看以下的示例
如果我们要将以上的 n 的二进制表示的最右侧的 1 去掉，先将得到原来 n-1 与原来的 n 进行按位与操作
通过以上的图示就可以看出在进行 n-1 操作之后得到的结果和原先的 n 相比在二进制表示当中从最右侧的 1 右侧边（包含最右侧的 1）的二进制相比原先的二进制都进行的取反，左侧的 0 保持不变。
以上得到的结果再和原来的 n 进行按位与就能将原来 n 二进制表示最右侧的 1 去掉。
8. 位运算符的优先级
在此你可能对& | 等位运算的操作符的优先级已经遗忘了，但其实在使用位运算操作符当中只要记住能加括号就加括号这样就一定不会出现错误。
9. 异或 (^) 运算的运算律
通过之前的学习就知道按位异或有以下的规律：
- a^0=a
- a^a=0
- a^b^c=a^(b^c)
接下来我们将通过以下的几道算法题来巩固以上我们复习的位运算的知识
通过以上的题目描述就可以看出该算法题要我们实现的求出给定的正整数当中二进制表示当中 1 的个数。
那么要解决这道题就需要使用到以上提到的将给定数当中最右侧的 1 去除的操作，在此只需要再创建一个变量 count 来统计进行去除操作的次数即可，最终当 n 为 0 时此时变量 count 的个数就是原给定的正整数二进制表示当中 1 的个数
实现代码：
class Solution {
public:
int hammingWeight(int n) {
//使用 count 变量来统计 n 内二进制 1 的个数
int count=0;
while(n>0) {
//将 n 内最右侧的 1 去除
n=n&(n-1);
count++;
}
return count;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是从 0 到给定数 n 之间的全部数的二进制标示中 1 的个数存储到对应的数组下标位置。
那么要解决这道题就需要从 0 到 n 对各个元素进行二进制表示中 1 的计算，此时还是使用 n=n&(n-1) 来进行 1 个数的计算。
代码实现：
class Solution {
public:
vector<int> countBits(int n) {
//返回的 ret 数组
vector<int> ret(n+1);
for(int i=0;i<=n;i++) {
//创建变量 count 来统计 1 的个数
int count=0,tmp=i;
while(tmp>0) {
tmp=tmp&(tmp-1);
count++;
}
ret[i]=count;
}
return ret;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是求出给定的两个整数 x 和 y 二进制表示不同位的个数。
那么要解决这道题就可以使用按位异或再结合去除给定数二进制表示最右侧 1。由于我们要求的是给定的 x 和 y 二进制表示当中不同位的个数，那么就可以先将 ret=x^y，因为按位异或的运算逻辑，此时得到的 ret 当中二进制为 1 的为就表示该位置 x 和 y 的二进制表示是不同的。之后再使用 ret=ret&(ret-1) 得到 ret 二进制表示当中 1 的位数，使用 count 来统计个数，最终返回 count 即可。
代码实现：
class Solution {
public:
int hammingDistance(int x, int y) {
//创建 count 变量来统计 ret 内二进制表示 1 的个数
int ret=x^y,count=0;
while(ret>0) {
ret=ret&(ret-1);
count++;
}
return count;
}
};
在这道算法题当中要我们实现的就是从给定数组当中找出只出现一次的数。
在此由于在数组当中其他的数都是出现两次，而只有一个数出现一次此时就可以使用按位异或操作来实现。具体的实现过程就是只需要将数组的元素全部使用按位异或，最终得到的结果就是只出现一次的数，在此就是使用到 a^a=0；a^0=0
代码实现：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(auto x:nums) {
ret^=x;
}
return ret;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是在给定的数组当中找出两个只出现一次的数。
那么要解决这道算法题就需要使用到按位异或以及求给定数 n 二进制表示最右侧的 1；首先由于给定的数组当中只有两个只出现一次的数，其他的数都是出现两次的，这就使得将数组全部数进行按位异或之后结果就为两个只出现一次的数按位异或的结果。由于这两个数进行按位异或时最终二进制位当中为 1 的位一定是两个数在对应位置不同的结果。那么此时就可以依据该位置来将原来的数组划分为两部分，一部分就是在指定的二进制位为 1；另一部分就是在指定的二进制位为 0，这样两个只出现一次的数就会分别被划分到这两部分内。这样将两部分的元素分别进行按位异或就可以得到这两个数。
代码实现
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
//防止溢出将 t 定义为有符号整型
unsigned int t=0;
//将数组 nums 的所有元素进行按位异或操作
for(auto x:nums) {
t^=x;
}
int t1=0,t2=0;
//得到 t 当中的二进制表示最右侧的 1
int c=t&(-t);
//变量原数组进行分类
for(auto x:nums) {
if((x&c)==0)t1^=x;
else t2^=x;
}
return {t1,t2};
}
};
在以上我们对之前了解过的算法题进行了复习，那么接下来就通过几道算法题来对学习的位运算知识进行巩固和提升，在此我们还是按照题目解析、算法原理讲解、代码实现三步来实现。
在此根据题目描述就可以看出该算法题要我们实现的是对给定的字符串进行判断如果字符串当中没有出现重复的字符就将返回 true，否则就返回 false。
在此我们可以通过先创建一个 map 对象之后遍历给定的字符串每次将遍历到的字符存储到 map 对象内，遍历完之后在遍历 map 对象如果其内部出现一个键值对的值大于 1 就说明原字符串内字符不唯一。
以上的算法确实能解决这道算法题，但是在此我们使用到了 map 这个额外的数据结构，那么有什么不使用额外的数据结构的算法呢？
在此其实就需要使用到位图的思想了，由于题目给定的字符串只会包含小写的字符，那么在我们就只需要创建一个整型变量用其的二进制位表示就可以存储所有的情况。之后就只需要遍历原数组，每次遍历到字符元素再将其**减去'a'**之后再位图当中寻找此时的二进制位值是否为 1，是的话就说明原字符串当中出现了相同的字符，如果遍历到字符串的结束还没有出现相同的字符就说明原字符串当中所有字符都是唯一的。
在此其实还要一个点可以优化就是根据'鸽巢原理'；当字符串的长度大于 26 时，此时的字符串内一定会出现重复的字符
代码实现
class Solution {
public:
bool isUnique(string astr) {
//判断原字符串长度是否大于 26，是的话直接返回 false
if(astr.size()>26)return false;
int t=0;
//遍历字符串 astr
for(auto x:astr) {
int cur=int(x-'a');
//当对应二进制位值变为 0 就直接返回 false
if((t>>cur)&1)return false;
//若二进制位值为 0 就将该位置值修改为 1
else t|=(1<<cur);
}
return true;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的数组当中找出 [0,n] 未出现的那个数。
例如以上示例 1 当中 n 未 3 时那么要求数组当中数字的范围就是 [0,3]，那么在通过查找就可以发现数组当中缺少的是数字 2，那么返回的数字就是 2
在该算法题当中要解决其实有很多的方式，但是在题目当中有以下的进阶提示
也就是说我们能否用 O(n) 的时间复杂度，O(1) 的空间复杂度解决呢？
在此如果不创建额外的空间解决就不能使用哈希表了，那么其实就只剩下位运算和高斯求和可以解决问题了
在此位运算的方法是将 0 到 n 的数字全部按位异或起来，之后再将结果和数组当中元素全部按位异或起来最后得到的结果就是数组当中没有出现的那个数
高斯求和的方式就是先将 0 到 n 的等差数列求和的结果，之后遍历数组将之前得到的结果减去数组的全部元素值，最后得到的结果就是数组当中没有出现的那个数
位运算法：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n=nums.size();
int ret=0;
for(int i=0;i<=n;i++) {
ret^=i;
}
for(auto x:nums) {
ret^=x;
}
return ret;
}
};
高斯求和法：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n=nums.size();
int sum=(n*(n+1))/2;
for(auto x:nums) {
sum-=x;
}
return sum;
}
};
通过以上的题目解析就可以看出该算法题要我们实现的是不使用 + 和 -，求出给定的两个数 a 和 b 的和
要不使用 + 和 - 解决就需要使用其他的运算来解决，在此其实就需要使用按位异或来解决，因为我们知道按位异或计算的本质就是无进位相加，那么再使用了按位异或之后只需要再将进位得到就可以算出最终的结果。
接下来就通过一个示例来分析算法的具体实现过程是什么样的
例如要计算 13 加 14，先来看这两个数二进制位进行按位异或的结果是什么样的
接下来就需要计算进位，我们知道进位只有在两个数的二进制位都为 1 时才会出现，那么按位与就能满足要求，并且计算之后进位还要使用<<1 ,之后将得到的结果再和赋值给 b 之前 a^b 的结果赋值给 a 进行按位异或操作，之后一直重复直到进位计算出的结果为 0 时 a 和 b 按位异或的结果就是一开始 a+b 的结果
class Solution {
public:
int getSum(int a, int b) {
while(b) {
int x=a^b;
//防止负数出现越界问题将进位 y 定义为无符号整形
unsigned int y=(unsigned int)((a&b)<<1);
a=x,b=y;
}
return a;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的数组当中找出只出现一次的数字，在此除该数字以外其他的数在数组当中都出现 3 次
在这道题当中由于数组当中其他的数是出现了基数次，那么就不能像之前其他元素出现两次那样将所有元素直接进行按位异或操作，而是要先设数位 ret 为 0。
由于整个数组中，需要找的元素只出现了「一次」，其余的数都出现的「三次」，因此我们可以根据所有数的「某一个比特位」的总和 %3 的结果，快速定位到 ret 的「一个比特位上」的值是 0 还是 1。
这样，我们通过 ret 的每一个比特位上的值，就可以将 ret 给还原出来。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
//将 32 个比特位依次计算
for(int i=0;i<32;i++) {
int sum=0;
for(auto x:nums) {
if((x>>i)&1==1)sum++;
}
int t=sum%3;
if(t==1)ret|=(1<<i);
}
return ret;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的数组找出 [1,n] 当中两个缺失的数字。
这道题如果在是直接上手来写的就会比较困难，但是在之前我们已经解决了 丢失的数字 以及 只出现一次的数字||| 那么这道题其实也不是那么难了。
在此就只需要结合之前两道算法题的思想，先将将 0 到 n 的数以及给定数组当中的全部元素进行按位异或，那么得到的结果就是两个缺失的数字进行按位异或的结果。接下来就是 0 到 n 的数字以及给定的数组当中找出两个只出现一次的数字，这就和之前解决只出现一次的数字那道算法题一样了
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
//创建变量 s 统计两个缺失的元素按位异或的结果
unsigned int s=0;
//变量 n 为数组加上缺少的元素之后的元素个数
int n=nums.size()+2;
for(int i=1;i<=n;i++) {
s^=i;
}
for(auto x:nums) {
s^=x;
}
int t=s&(-s);
int ret1=0,ret2=0;
//进行分类
for(auto x:nums) {
if(x&t)ret1^=x;
else ret2^=x;
}
for(int i=1;i<=n;i++) {
if(i&t)ret1^=i;
else ret2^=i;
}
return {ret1,ret2};
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online