企业官网建设流程全解析

🔥 个人专栏: 《C语言》、《数据结构》、《C++》、《Linux》

🗂️ Gitee仓库: 《C语言》、《数据结构》、《C++》、《Linux》

</> 算法专栏: 《算法精选集》

讲解位运算的算法题之前，我们先来补充一点预备知识。

1 ···> 预备知识

1.1、基础位运算符号

1.2、给一个数n，确定它的二进制表示中的第x位是 0 / 1

首先，我们约定，一个数的二进制位，是从0开始，即第0位、第1位、第2位……一直到第31位。

要想确定一个数的二进制表示的第x位，到底是0还是1，我们可以先把这第x位右移到第0位上，再过滤掉除第0位以外所有位上的1，这时我们想到按位与(&)：

确定第x位是0或1的式子得出。验证一个数：

#include<stdio.h>intFunc(intn,intx){return(n>>x)&1;}intmain(){intn=0,x=0;while(~scanf("%d %d",&n,&x))printf("%d\n",Func(n,x));return0;}

5的二进制表示：[0 1 0 1]，第2位：

1.3、运算符的优先级

这里我们不需要背那些复杂的运算符优先级表，只需记住：想让哪一步运算先执行，就给哪一步加上小括号。

1.4、将一个数n的二进制表示的第x位修改成1

将1左移x位，然后按位或n即可。由于我们做的是修改，所以运算结果要反过来写入n。

例如，213修改第3位成“1”后结果是221：

#include<stdio.h>intFunc(intn,intx){returnn|=(1<<x);}intmain(){intn=0,x=0;while(~scanf("%d %d",&n,&x))printf("%d\n",Func(n,x));return0;}

1.5、将一个数n的二进制表示的第x位修改成0

将1左移x位，然后按位取反，再按位与上n即可。

因为我们要将第x位修改成“0”，所以我们就需要保留其它位的“1”。这时我们会想到：“1”按位与上“1”的结果还是“1”，而“0”按位与上任何数的结果都是“0”。

例如，89的第3位修改成0后结果是81：

#include<stdio.h>intFunc(intn,intx){returnn&=(~(1<<x));}intmain(){intn=0,x=0;while(~scanf("%d %d",&n,&x))printf("%d\n",Func(n,x));return0;}

1.6、位图的思想

所谓位图，本质上就是一个缩小版的哈希表。由于有些信息可以转化为0和1，

• 哈希表还要创建一个很大的数据结构，来存储信息；
• 而位图只需要借助一个整型变量(int, unsigned long)，就可以在整型变量的二进制表示中标记0和1。

位图的使用，大大降低了空间复杂度。甚至我们在Linux的“大O(1)调度算法”中，借助位图遍历不同优先级的进程队列，由遍历140次降低到遍历5次，然后通过常数级效率的运算确定当前优先级的进程队列是否为空，还能一定程度上缩短运行时间，提高运行效率。

1.7、提取一个数n二进制表示中最右侧的1

给出计算式：

我们可以举例观察一下：

// int整型有32位// n: 0000 0000 0000 0000 0000 0001 0110 1000// 取负操作: 按位取反，再+1//~n: 1111 1111 1111 1111 1111 1110 1001 0111//-n: 1111 1111 1111 1111 1111 1110 1001 1000

我们发现，以最右侧的“1”为界，

• n与-n的右侧，都是“0”；
• n与-n的左侧，每一位都不同；意味着每一位在n或-n上，一定有一个“0”。

所以n & (-n)，

• 对于左侧：“0”与“0”按位与，结果是“0”；
• 对于右侧：“0”与“1”按位与，结果是“0”。

自然就过滤出最右侧的“1”。

1.8、干掉一个数n二进制表示中最右侧的1

给出计算式：

我们以举例观察一下：

// int整型有32位// n: 0000 0000 0000 0000 0000 0001 0110 1000// n - 1: 0000 0000 0000 0000 0000 0001 0110 0111

所以 n - 1 的本质是：将n二进制表示式的右侧，连同最右侧的1，一同取反。

接着只要 n & (n - 1) ，就可以干掉最右侧的1了。

1.9、异或(^)运算的运算律

根据结合律，可以推断出：所有数异或在一起，结果是唯一的。

我们可以简单演示一下三个数连续异或的计算方法：

#include<stdio.h>intmain(){printf("%d\n",90^21^81);return0;}

1.10、补充应该先做的题

都在leetcode上，

191、位1的个数

其实就是不断出最右侧的“1”，然后统计出了多少次：

classSolution{public:inthammingWeight(intn){intret=0;while(n){n&=(n-1);++ret;}returnret;}};

338、比特位计数

这道题很容易可以想到用循环嵌套的方法来做，即遍历 0 ~ n ，对每一个数都用循环统计“1”的个数。

但是这道题可以用动态规划的思想来优化，我得先好好学一下动态规划，再来自己好好攻克一下。

461、汉明距离

就是求两个数的二进制表示中，有多少位不同。

我们就可以将两个数按位异或起来得到val，这样一来相同的位变成0，不同的位变成1，问题就转化成统计val中“1”的个数即可。

classSolution{public:inthammingDistance(intx,inty){intval=x^y;intret=0;while(val){val&=val-1;++ret;}returnret;}};

136、只出现一次的数

只需按位异或在一起，就可以过滤掉所有出现两次的数。

classSolution{public:intsingleNumber(vector<int>&nums){intret=0;for(auto&i:nums)ret^=i;returnret;}};

260、只出现一次的数Ⅲ

这道题与上面一道题的区别在于，这道题多了一个只出现一次的数需要我们找出来。

在这里，我们不妨把整个数组，分成各包含一个出现一次的数，的两个数组。分离的方法是：

1. 所有数按位异或到一起，得到val；
2. 对于val的二进制表示，我们看最右侧的“1”
   • 一定有一批出现两次的数，以及其中一个出现一次的数，相同位置上也是“1”；
   • 剩下的出现两次的数，以及另一个出现一次的数，相同位置上就是“0”。
3. 我们按照(2)中的规律，再分别将两个数组中的数按位异或起来，就能得到结果。

classSolution{public:vector<int>singleNumber(vector<int>&nums){intval=0;for(auto&i:nums)val^=i;intleft=0,right=0,order=val&(-(unsignedint)val);for(auto&i:nums){if(order&i)left^=i;elseright^=i;}return{left,right};}};

2 ···> 判断字符是否唯一

判断字符是否唯一

我们很容易会想到使用哈希表：

• 遇到不存在的字母，入哈希表；
• 遇到存在的字母，返回false；
• 遍历能够结束，返回true。

但是直接创建一个哈希表，空间浪费还是比较大。

小写英文字母有26个，而int类型变量占32个比特位。我们不妨只用一个int变量代替哈希表，即使用位图。

classSolution{public:boolisUnique(string astr){intret=0;for(auto&c:astr){intlocal=c-'a';if((ret&(1<<local))!=0)returnfalse;elseret|=(1<<local);// 记录存在与否，不是&！！！}returntrue;}};

3 ···> 丢失的数字

丢失的数字

假设数组的长度为x。

原来的数组，应该是：

现在缺了一个数字。那么现在数组的下标排成的一个序列是：

我们只需初始化一个返回值ret为x，然后遍历现数组，将值与下标按位异或在一起，就能将问题转化为“只出现一次的数字”进行求解。

classSolution{public:intmissingNumber(vector<int>&nums){intret=nums.size();for(inti=0;i<nums.size();++i)ret^=i^nums[i];returnret;}};

4 ···> 两整数之和

两整数之和

题目意思很简单，就是计算给出两个整数的加和。但是，我们不能使用“+”“-”完成两个整数的加和。

对于两整数相加，我们很容易想到按位异或，即无进位相加。比如，

// 13: 001101// 28: 011100// 13 ^ 28 = 010001

“1”与“1”相加，肯定是要进位的：

• “1”与“1”：进一位；
• “1”与“0”：不进位；
• “0”与“0”：不进位。

我们很容易就能想到按位与。而且，进的一位，肯定是要左移的：

// 13: 001101// 28: 011100// 13 & 28 = 001100// (13 & 28) << 1 = 011000

接着，我们重复操作：

• 让^出来的结果充当a；
• 让&并左移的结果充当b；
• 继续上述两个操作，直到b为0，也就是进位没有了，此时a就是返回值。

classSolution{public:intgetSum(inta,intb){while(b){intx1=a^b,x2=(a&b)<<1;a=x1,b=x2;}returna;}};

小贴士1

---

笔试场上我们要见机行事，如果允许的话，直接return a + b;得了。(😄)

5 ···> 只出现一次的数字(Ⅱ)

只出现一次的数字(Ⅱ)

这道题的特点是：在一个数组中，除只出现一次的数外，其他数都出现了3次。

我们不妨观察数组中每一个数的任意一个比特位：

对于每一个数，我们可以做一个区分：

• 要么是出现一次的数；
• 要么是出现3次的数；

那么对于一个数组中所有的数，在这个特定位置上的比特位，相加之后，有这四种情况：

• 3n个0 + 0 = 0
  • 解释一下：其中，“0”表示出现一次的数特定二进制位上是0；“3n个0”表示剩余出现三次的数中，每一种数特定二进制位上都是0。所有0相加，结果还是0。
• 3n个0 + 1 = 1
• 3n个1 + 0 = 3n
• 3n个1 + 1 = 3n + 1

我们再将四个结果%3，就可以得到：

• 0 % 3 = 0
• 1 % 3 = 1
• 3n % 3 = 0
• (3n + 1) % 3 = 1

四个结果，不刚好与出现一次数在特定二进制位置上的比特位表示相对应吗？通过这个规律，我们就可以把结果“从ret = 0开始，一个比特位一个比特位地把结果做出来”。

classSolution{public:intsingleNumber(vector<int>&nums){intret=0;for(inti=0;i<32;++i){intbitsum=0;for(auto&n:nums)if(((n>>i)&1)!=0)bitsum++;bitsum%=3;if(bitsum==1)ret|=(bitsum<<i);}returnret;}};

当然，我们可以推广到“除出现一次的数外，其它数都出现n次的情况(n为奇数)”：

classSolution{public:intsingleNumber(vector<int>&nums){intret=0;inttimes=3;//for(inti=0;i<32;++i){intbitsum=0;for(auto&n:nums)if(((n>>i)&1)!=0)bitsum++;bitsum%=times;//if(bitsum==1)ret|=(bitsum<<i);}returnret;}};

6 ···> 消失的两个数字

消失的两个数字

这道题的解法思路，其实是之前我们做过的两道题的思路的集合：

(看到这里，也许你可以自己试试看)

对于 1 ~ N 的整数，我们可以得到两个部分：

这种情形，很像“只出现一次的数字(Ⅲ)”的情况，即有两种数只出现了一次。

我们可以定义变量order，将原数组所有数与 1 ~ N 按位异或在一起。接着提取出order二进制表示的其中一个为“1”的位(可以是最右边的“1”)，根据这个“1”位，将原数组和 1 ~ N 分成两个部分：

• 数a与一批出现两次的数；
• 数b与另一批出现两次的数。

classSolution{public:vector<int>missingTwo(vector<int>&nums){intsz=nums.size();intorder=0;for(inti=1;i<=sz+2;++i)order^=i;for(auto&n:nums)order^=n;intleft=0,right=0;intdiff=(order&(-(unsignedint)order));for(inti=1;i<=sz+2;++i){if((diff&i)!=0)left^=i;elseright^=i;}for(auto&n:nums){if((diff&n)!=0)left^=n;elseright^=n;}return{left,right};}};

这里有两个细节：

1. 位运算一定要按需加括号！(如果你不想背优先级法则的话)
2. 讲题老师使用了while循环找到order的“1”位，而我直接用常数级运算提取出了order最右边的“1”。(我的方法是不是更好？)