位运算的总结

回忆知识点

位运算是基于整数二进制表示进行的运算。
下面展示三种位运算的方法

	运算符	规律
与	&	只有两个对应位都为 1时才为 1
或	\|	只要两个对应位中有一个 1时就为 1
异或	^	只有两个对应位不同时才为 1

移位运算

n<<i 表示 n 的二进制表示向左移动 i 位所得的值。经常以 n<<1 来表示除二的操作
n>>i 表示 n 的二进制表示向右移动 i 位所得的值。

左移 i 位相当于乘 2ⁱ，右移 i 位相当于除以2ⁱ。

原码补码反码

因为有一道题用到了这个知识点所以我来复习一下，考研 er

原码：是最简单的机器数表示法。用最高位表示符号位，‘1’表示负号，‘0’表示正号。其他位存放该数的二进制的绝对值

这里举个🌰
‘1010‘ 最高位为 1 表示这个数是个负数，其他三位‘010’转为十进制为 2，所以‘1010’表示-2。
同理‘0010’表示十进制的 2

0010+0011=0011=1+2=3；对于整数加减法是合理的
0000+1000=1000=0；这个也是合理的
0001+1001=1010=1+(-1)=-2；这是错误的
所以引入了反码来解决这个问题

反码：正数的反码还是等于原码，负数的反码就是他的原码除符号位外，按位取反。

举个🌰
对于正数 3，原码为 0011，反码仍为 0011；
对于-3，原码为 1011，符号位不变，其余位按位取反，则反码为 1100
对于-1，原码为 1001，则反码为 1110
此时如果再进行上面的运算
0001+1110=1111=1+(-1)=-7
1110+1101=1011=-1+(-2)=-4
1110+1100=1010=-1+(-3)=-5
可以发现除了第一个以外，结果均与正确值相差 1
所以引入补码的概念来解决这一问题

补码：正数的补码等于他的原码，负数的补码等于反码+1。也等于正数反码+1。

🌰依旧出场
用补码来进行运算
源码 1 : 0001 -1: 1001
补码 1 : 0001 -1: 1110 + 1 = 1111
补码相加 1 + -1 = 0001 + 1111 = 0000 结果为 0，答案正确
你可能想问结果为什么不是五位数，因为机器码的位数在操作系统中是固定位，假设固定为 4 位，那么结果就只有四位码

补充

这里听劝去看了下灵神的知识点。[^1]

集合可以用二进制来表示，二进制从低到高第 i 位表示 i 在集合中，0 表示 i 不在集合中。比如这样一个集合{0,2,3}可以用二进制数 1101 表示；

第 0 位为 1 表示 0 在集合中
第 1 位为 0 表示 1 不在集合中
第 2 位为 1 表示 2 在集合中
第 3 位为 1 表示 3 在集合中

反过来二进制数 1101 就对应集合{1101}。所以，包含非负整数的集合 S 可以通过压缩成一个数字。

例如集合{0,2,3}可以压缩成 2⁰+2²+2³=13, 也就是二进制数 1101.

集合与集合

两个集合的对称差是只属于其中一个集合而不属于另一个集合的元素组成的集合，也就是不在交集中的元素组成的集合。ps: 又遇到了离散数学知识点

	位运算	集合示例	位运算示例
交集	a&b	{0,2,3}{0,1,2}={0,2}	1101&0111=0101
并集	a\|b	{0,2,3}{0,1,2}={0,1,2,3}	1101 \| 0111=1111
对称差		{0,2,3}{0,1,2}={1,3}	1101 0111=1010
差	a&~b	{0,2,3}{1,2}={0,3}	1101&1001=1001
差 (子集)		{0,2,3}{0,2}={3}	1101 0101=1000
包含于	a&b=a a\|b=b	{0,2}{0,2,3}	0101&1101=0101 0101 \| 1101=1101

注：判断子集的两种位运算写法等价，写代码只需要写其中一种。也可以用 (a&~b)==0 判断，也就是 a 和 b 的补集相交为空，如果成立也可以表示 A 是 B 的子集。

集合与元素

通常会用到[[#移位运算]]。

	集合	位运算	集合示例	位运算示例
空集		0
单元素集合	{i}	1<<i	{2}	1<<2
全集	U={0,1,2,3,…, n-1}	(1<<n)-1	{0,1,2,3}	(1<<4)-1
补集	∁_US=U∖S	((1<<n)-1) s	U={0,1,2,3} ∁_U{1,2}={0,3}	1111 0110=1001
属于		(s>>i)&1=1	2 {0,2,3}	(1101>>2)&1=1
不属于		(s>>i)&1=0	1 {0,2,3}	(1101>>1)&1=0
添加元素	S U {i}	s \| (1<<i)	{0,3} U {2}	1001 \| (1<<2)
删除元素	S \ {i}	s&~(1<<i)	{0,2,3} \ {2}	1101&~(1<<2)
删除元素（一定在集合中）	S \ {i},	s (1<<i)	{0,2,3} \ {2}	1101 (1<<2)
删除最小元素		s&(s-1)

这里解释一下位运算的表示。
1.1<<2 表示将 1 的二进制表示向左移动两位 0100，第二位是 1 表示 2 在集合中。
2.1 的二进制左移 4 位后是 00010000，减 1 后 00001111，表示集合{0,1,2,3}
3. 这里 1101 表示集合{0,2,3}，向右移动 2位后为 0011，与 0001 进行按位与操作结果是 0001，所以结果是 1；第 5 个结果为 0 就不解释了。
4. 集合{0,3}用 1001 表示，要添加元素 2 那就可以让第 2 位为 1。1<<2 就是元素 2 的集合，然后用或运算(有一位是1就为1)就可以实现
5. 集合{0,2,3}用 1101 表示，要删除元素 2 可以通过让第 2位为 0 。1<<2 是元素为 2 的集合，按位取反后为 1011，然后和原集合取交集即为无 2 的集合。与操作取交集 (都为 1 时才为 1)
6. 集合{0,2,3}用 1101 表示，要删除元素 2 可以通过让第 2位为 0 。这里可以保证要删除的元素一定在集合中。所以就可以用按位异或的运算 (不同时为 1)，0100 是只有2，和 1101 异或之后变为 1001。所以这里是保证元素一定在集合中才可以用，不然就会向集合中添加不存在的元素
7. 假设我们有一个集合 s 用二进制来表示。要删除最小的元素即为删除最右边的 1。这里假设集合为 101100，那么 s-1 即为 101011 按位与操作后为 101000 这样就把最右侧的 1 去掉了
8. 当 s 是 2 的幂，那么s&(s−1)=0，如何解释呢，二进制的幂的二进制表示(以 2²为例)为 0100 那么去除最右侧 1 之后就为 0000 结果为 0。

c++中提供了一些和二进制有关的函数

	C++
集合大小	__builtin_popcount(s)
二进制长度	__lg(s)+1
集合最大元素	__lg(s)
集合最小元素	__builtin_ctz(s)

当 s=0 时,对于 c++来说 __lg(0) 和 __builtin_ctz(0) 是未定义行为。
特别地，只包含最小元素的子集，即二进制最低 1 及其后面的 0，也叫 lowbit，可以用 s & -s 算出。

s=101100
~s=010011
~s+1=010100
s&~s=000100//lowbit

遍历集合

设元素范围从 0~n-1，枚举范围中的元素 i，判断 i 是否在集合 s 中。

for(int i=0;i<n;i++)
{
	if((s>>i)&1){//i在s中
	//处理i的逻辑
	}
}

也可以直接遍历集合 s 中的元素：不断地计算集合最小元素、去掉最小元素，直到集合为空。

for (int t=s;t;t&=t-1)
{
	int i=__builtin_ctz(t); 
	//处理i的逻辑
}

枚举集合

4.1 枚举所有集合
设元素范围从 0 到 n-1，从空集枚举到全集：

1
2
3

for(int s=0;s<(1<<n);s++){
//处理s的逻辑
}

4.2枚举非空子集
设集合为 s，从大到小枚举 s 的所有非空子集 sub：

1
2
3

for(int sub=s;sub=(sub-1)&s){
//处理sub的逻辑
}

为什么写成 sub=(sub-1)&s?
暴力的做法是从 s 出发不断减一，直到 0. 这样做会遇到很多不是 s 子集的情况。比如 s=10101 时，减一得到 10100 这是 s 的子集，再减一得到 10011 这不是 s 的子集，下一个子集应该是 10001。
这里我们就需要进行处理，把最低位的 1 变成 0，对于最低位 1 右侧的 0 只有在 s 中的 1才变成 1. 所以在减一后&s 就可以。

4.3枚举子集(包含空集)
从大到小枚举 s 的所有子集 sub

int sub=s;
do{
//处理sub的逻辑
sub=(sub-1)&s;
}while(sub!=s)

还可以枚举全集 U 的所有大小恰好为 k 的子集，Gosper’s Hack 算法[^2]

void GospersHack(int k,int n)
{
	int subset=(1<<k)-1;
	int limit=(1<<n);
	while(subset<limit)
	{
		//do something
		//计算lowbit
		int lb=subset&-subset;
		 //左边部分计算
		 //subset+lb达到的效果就是将最右边的01变成10
		int r=subset+lb;
		subset=((r^subset))>>_built_ctz(lb)+2|r;
		//或subset=(((r^subset)>>2)/b)|r;
		//(subset^r)/lb>>2 右边部分公式。也就是将左边部分之后的1全部集中到最右边。右移两位是把左边部分改变的两位影响去除
		 //|r将两个数的1合并起来，不使用+避免影响1的位置
	}
}

如果调用 GospersHack(3,5) 会得到以下二进制数：

4.4枚举超集
如果 T 是 S 的子集，那么称 S 是 T 的超集

枚举超集和枚举子集是类似的，通过或运算保证枚举的集合 S 一定包含集合 T 中的所有元素。

1
2
3

for(int s=t;s<(1<<n);s=(s+1)|t) {
    //处理s的逻辑
}

作用

对于位运算，我感觉应用还是比较广泛的，在牛客周赛上见到学长有用过。

一方面是在状压 DP 中会用到，用来表示集合或者是状态
或者有些题目就是位运算的题（求异或和之类的）
或者可以通过位运算来高效进行一些运算（这个看个人能力吧）

做题吧~💡💡💡

AcWing 801. 二进制中1的个数

这个题的意思非常简单，就是要求出数列中每个数的二进制表示中 1 的个数。

一个 int 类型的变量的长度是 32，所以我们可以通过循环 32 次求出它的每一位是几。也就是我们可以使用上面的右移方法来判断它的每一位是否为 1，通过或运算来验证。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=1,x;i<=n;i++)
    {
        cin>>x;
        int res=0;
        for(int i=0;i<=31;i++)
        {
            if(x>>i&1)res++;
        }
        cout<<res<<" ";
    }
    return 0;
}

我们也可以通过 lowbit (x) 操作，表示 x 的最后一位。每次 lowbit 操作截取一个数字最后一个 1 后面的所有位，每次减去 lowbit 得到的数字，直到数字减到 0，就得到了最终 1 的个数。C++中负数是用补码，补码等于反码+1；所以 x&-x=x&(~x+1)。

#include <bits/stdc++.h>
using namespace std;
int lowbit(int x)
{
    return x&-x;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1,x;i<=n;i++)
    {
        cin>>x;
        int res=0;
        while(x) x-=lowbit(x),res++;
        cout<<res<<" ";
    }
    return 0;
}

AcWing 89. a^b

这个题其实是快速幂(可以快速求出 a^k mod p 的结果)的模板题和 AcWing 857 其实是同一道题

暴力思路其实很好想 (当然会 TLE)

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    ll a,b,p;
    cin>>a>>b>>p;
    ll res=1;
    for(ll i=1;i<=b;i++)
    {
        res=res*a%p;
    }
    cout<<res;
    return 0;
}

这里我们需要先预处理出 a^2⁰, a^2¹, a^2¹,…, a^{2^logk}.这 log k个数
对于一个数字 a^k, 可以用a^2⁰, a^2¹, a^2¹,…, a^{2^logk}.这 log k个数来组合，也就是 k用二进制形式来表示。
这个是处理多组数据的代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll qmi(int a,int k,int p)
{
    ll res=1%p;
    while(k)//对k进行二进制化,从低位到高位
    {
        if(k&1) res=res*a%p;
        k>>=1;
        //更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logk}
        a=(ll)a*a%p;//这里逐步更新a，边计算边处理
    }
    return res; 
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,p,k;
        cin>>a>>k>>p;
        cout<<qmi(a,k,p)<<endl;
    }
    return 0;
}

下面是针对这个题的代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    int a,p,k;
    cin>>a>>k>>p;
    ll res=1%p;
    while(k)
    {
        if(k&1) res=res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    cout<<res<<endl;
    return 0;
}

这里顺便把洛谷 P 1226 快速幂也做了，代码如下

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    int a,p,k;
    cin>>a>>k>>p;
    ll res=1%p;
    cout<<a<<"^"<<k<<" mod "<<p<<"=";
    while(k)
    {
        if(k&1) res=res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    cout<<res<<endl;
    return 0;
}

AcWing 5579. 增加模数

这个题真够折磨人的，我尝试了 16 次，这个题其实就是把上一个快速幂变成了多个快速幂，所以我们只需要每次输入 a, b 然后直接计算就可以。思路上没有什么问题。

#include<bits/stdc++.h>
using namespace std;
// using ll=long long;
const int N = 10;
int qmi(int a,int k,int p)
{
    int res=1;
    a%=p;
    while(k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int result=0;
        int m,h;
        cin>>m>>h;;
        for(int i=0;i<h;i++)
        {
            int a,b;
            cin>>a>>b;
            result=(result+qmi(a,b,m))%m;
        }
        cout<<result<<endl;
    }
    return 0;
}

这个代码最大的注意事项就是不能用 long long，开了就 TLE，具体原因鄙人未知。

AcWing 90. 64位整数乘法

这里如果直接相乘那就会爆 longlong，可以去考虑高精度的做法，但是我现在还没有复习到。
这里我们考虑对 b 进行二进制拆分，当然拆 a 也可以。然后如果某位上为 1 就加上 $Double exponent: use braces to clarify a^2^n mod p$

这里还是举个🌰
3*7； 7 可以用二进制表示为 111，7=2⁰+2¹+2²;
所以就可以根据乘法分配律 3*(2⁰+2¹+2²)=3*2⁰+3*2¹+3*2²=3+6+12=21=3*7;
这里可以看出，每一次都可以通过前一次乘二来推出
再用 3*6 来演示一下，7 可以用二进制表示为 110，6=2¹+2²;
3*(2¹+2²)=6+12
这里起初 a 为 3 但是 6 的二进制第一位为 0，所以不加，a=a*2%p;
a 变为了 6，之后的累加就自然说通了
看到这里应该明白这个意思了叭🍉🍉🍉

代码思路和上方一直，可以结合演示来理解。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    ll a,b,p,res=0;
    cin>>a>>b>>p;
    while(b)
    {
        if(b&1)res=(res+a)%p;
        b>>=1;
        a=a*2%p;
    }
    cout<<res;
    return 0;
}

AcWing 91. 最短Hamilton路径

这个题如果暴力去做是会 TLE 的，这里就用到上面说的优化就是状压 DP。我们可以用二进制数来表示哪些点走过，0 表示没走，1 表示走了。当二进制数全为 1 时就代表走完了。2ⁿ的二进制表示为 1111…11

这里我们分析一下 DP，我们这里需要输出的也是最优解，所以 f_{i, j}表示经过 i 集合的所有点到 j 点的最短 Hamilton 路径，属性就是最小值。那么就不难得到状态转移方程：f[i]][j]=min (f[i][j], f[i^(1<<j)][k]+weight[k][j])。

这里的 weight 数组是权值，表示从 k 点到 j 的距离。
i^(1<<j) 的意思是，i 异或 1 右移 j 位，具体来说就是 i 这个方案集合 xor 10……0, (其中 1 的位置在第 j 位)。其实就是将 i 的第 j 位改为 0，这样就符合了走到点 k的路径就不能经过点 j这个条件。
- 如果 i 的第 j 位上是 1 那么将其改为 0；
- 否则将 i 的第 j 位改为 1；
  可能表述的比较混乱，具体逻辑在代码中体现

#include <bits/stdc++.h>
using namespace std;
const int N=20,M=1<<N;//一共最多有20个1种状态
//解释一下1<<N：因为i是二进制数，表示从0到当前点的状态，所以每个点都有两个状态0和1，所以是2的N次方
int n,i,j,k,f[M][N],w[N][N];
//f[i][j]:所有从0走到j,走过的所有点的情况是i的所有路径
//f记录距离的总和例如f[2][4]表示第两种情况，从0号点到4号点的距离总和。
//w用来存储点与点之间的距离权重
int main()
{
    cin>>n;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cin>>w[i][j];
    memset(f,0x3f,sizeof f);//f的属性是最小值，这里先设为最大值
    f[1][0]=0;////第一个点是不需要任何费用的
    for(i=1;i<1<<n;i++)//i是遍历所有状态，从000000000到1111111111
    {
        for(j=0;j<n;j++)//j遍历每个点。
        {
            if(i>>j&1)//如果i集合中第j位是1，也就是到达过这个点
            //k表示走到j这个点之前，以k为终点的最短距离
            for(k=0;k<n;k++)
            {
                if((i^(1<<j))>>k&1)//i除去j这个点后包含k这个点
            //如果从当前状态经过点集i中，去掉点j后，i仍然包含点k，那么才能从点k转移到点j。
            //当然这个if也可以不加，因为如果i去掉第j个点后，i不包含点k了，
            //那么f[i^1<<j][k]必然为正无穷，也就必然不会更新f[i][j]，所以去掉也可以AC。
                {
                    f[i][j]=min(f[i][j],f[i^(1<<j)][k]+w[k][j]);
                }
            }
        }
        
    }
    cout<<f[(1<<n)-1][n-1];
    //(1<<n)-1表示：有n个1，也就是所有的点都走完了
    //n-1表示：终点
    return 0;
}

AcWing 998. 起床困难综合症

这个题一共有 3 种操作，要得到经过 n 次操作后的最大值，这几个运算只有关该位上的数，不影响其他位上的数。所以我们可以从高到低来确定数的每一位。如果这一位上可以填 u 并且填 u 之后答案的该位是 1，那么在该位填 u 否则填!u;

问题来了，如何确定该位可以填几？

如果该位填 1 后，所得的数大于 m，那么该位填 0
否则如果该位填 1 后所得的数对 n 个数都运算之后结果小于等于该位填 0 之后得到的结果，那么为了让剩下的能填的数更大，该位填0；
否则该位填 1；
确定好每一位之后就可以得到 ans 的值

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int ans;
int t[N];
short op[N];// op 存 n 个数对应的操作，1表示按位或，2表示按位异或，3表示与
string s;
bool calc(bool x,int j)// calc 用于计算 x 经过所有数的第 j 位操作后所得到的结果
{
    for(int i=0;i<n;i++)
    {
        if(op[i]==1) x|=t[i]>>j&1;
        else if(op[i]==2) x^=t[i]>>j&1;
        else x&=t[i] >> j & 1;
    }
    return x;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s>>t[i];
        if(s=="OR")op[i]=1;
        else if(s=="XOR")op[i]=2;
        else op[i]=3;
    }
    //本题中m最大是10^9，log2(10^9)=3log2(10^3)<3*10=30，所以每次i从29往后枚举就可以了
    for(int i=29;i>=0;i--)
    {
         if(1<<i<=m)//如果填1后小于等于m，要看填完后对答案的影响来填
         {
            bool x=calc(0,i),y=calc(1,i);
            if(x>=y) ans|=x<<i;//如果该位填1并不比该位填0更优，那么为了让剩下能填的数更大，在该位填0
            else ans|=y<<i,m-=1<<i;
            //否则在该位填1，填完后让m减去该位填1的结果，这样在后面填数的时候只用考虑是否大于m就可以了
         }else ans|=calc(0,i)<<i;// 否则该位只能填 0
    }
    cout<<ans;
    return 0;
}

0x3f 位运算题单第一章🦄🦄

🍇这里简单加练一下也熟悉一下力扣怎么刷题

Leetcode 3370. 仅含置位位的最小整数

这个题是要求大于等于 n 的第一个二进制位全为 1 的数，所以我们求出 n 的二进制位数 m，返回长为 m 的全为 1 的二进制数即可

class Solution {
public:
    int smallestNumber(int n) {
        int ans=0;
        while(n){
            ans=ans<<1|1;
            //这个操作是将ans不断左移，然后通过按位或的操作将1加到最低位上
            n>>=1;
            //这里把n右移减小位数
        }
        return ans;
    }
};

这里呢灵茶的代码是这样的

class Solution {
public:
    int smallestNumber(int n) {
        return (1 << bit_width((uint32_t) n)) - 1;
        //这里用bit_width计算无符号32位整数的二进制表示的位宽，然后左移bit_width((uint32_t) n)位，使其最高位为1，减一操作得到一个全为1的二进制数
    }
};

Leetcode 3226. 使两个整数相等的位更改次数

这里我们运用集合与集合的思想，n ,k为两个不同的集合，如果可以使 n 修改为 k，我们是从 n 中去掉元素使其等于 k，那么 k 应该为 n 的子集。否则返回-1，满足这一条件后，我们可以通过对称差 (按位异或) 操作来得到需要去除的元素。这里因为 k 是子集所以得到的元素都是 n 独有的。通过 __builtin_popcount(n^k) 操作可以得到二进制中 1 的位数。
验证是否为子集还可以通过求 n 和 k 的并集(按位或运算)验证是否为 n

class Solution {
public:
    int minChanges(int n, int k) {
        return (n&k)!=k ? -1:__builtin_popcount(n^k);
        //return  (n|k)!= n ? -1:__builtin_popcount(n^k);
    }
};

Leetcode 1356. 根据数字二进制下 1 的数目排序

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(),arr.end(),[&](int x, int y){
            int x1=__builtin_popcount(x);
            int y1=__builtin_popcount(y);
            if(x1<y1) return true;
            if(x1>y1) return false;
            return x<y;
        });
        return arr;
    }
};

Leetcode 461. 汉明距离

这个题其实就是问两个集合中不同的元素有多少，那我们就可以继续沿用对称差方法，求出集合再用 __builtin_popcount() 来求出集合中的元素数目

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x^y);
    }
};

虽然直接用公式做题比较爽但是也学习一下用代码写这个操作

class Solution {
public:
    int hammingDistance(int x, int y) {
        int s=x^y,cnt=0;
        while(s){
            cnt+=s&1;
            s>>=1;
        }
        return cnt;
    }
};

Leetcode 2220. 转换数字的最少位翻转次数

这个题目和之前的类似，只是多了一个可以增加元素的操作，所以仍然是按位异或得到集合 s，这个集合包含 state 中独有的 (需要删除的元素) 和 goal 中独有的 (需要添加的元素)

class Solution {
public:
    int minBitFlips(int start, int goal) {
        int s=start^goal;
        return __builtin_popcount(s);
    }
};

Leetcode 1342. 将数字变成 0 的操作次数

这个题一般模拟就可以过, 就不写位运算了

class Solution {
public:
    int numberOfSteps(int num) {
        int ans=0;
        while(num)
        {
            if(num%2){
                num--;
            }else num/=2;
            ans++;
        }
        return ans;
    }
};

Leetcode 476. 数字的补数

我们从左边到右边找到该二进制的第一个 1，t - 1，则该位后面的数都是 1111 这样形式，数字取反后和 t 与操作表明取取反结果后面的二进制

class Solution {
public:
    int findComplement(int num) {
        if(!num) return 1;
        int t=0;
        for(int i=30;i>=0;i--)
        {
            if(num>>i&1){
                t=1<<i;
                break;
            }
        }
        t--;
        return ~num&t;
    }
};

Leetcode 1009. 十进制整数的反码

这个题用上面的代码就可以过了

class Solution {
public:
    int findComplement(int num) {
        if(!num) return 1;
        int t=0;
        for(int i=30;i>=0;i--)
        {
            if(num>>i&1){
                t=1<<i;
                break;
            }
        }
        t--;
        return ~num&t;
    }
};

也看到了用掩码做题的；那就来学习一下吧

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n==0) return 1; // 特殊情况处理
        int ans=1;          // 初始化掩码为 1
        while(ans<=n){    // 循环直到掩码大于 n
            ans<<=1;        // 将掩码左移一位
        }
        return ans-1-n;   // 计算补数
    }
};

Leetcode 868. 二进制间距

这个题要求相邻 1 的最远距离，我们可以每次取 n 最后一位判断是否为 1，如果上一位为 1 则更新距离

class Solution {
public:
    int binaryGap(int n) {
        int l=-1,ans=0;
        for(int i=0;n;i++)
        {
            if(n&1)
            {
                if(l!=-1)
                {
                    ans=max(ans,i-l);
                }
                l=i;
            }
            n>>=1;
        }
        return ans;
    }
};

Leetcode 2917. 找出数组中的 K-or 值

这里我们枚举每个元素的 0~30 比特位，统计该位为 1 的个数再对 ans 进行操作

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int ans=0;
        for(int i=0;i<31;i++)
        {
            int cnt1=0;
            for(int x:nums){
                cnt1+=x>>i&1;
            }
            if(cnt1>=k){
                ans|=1<<i;
            }
        }
    }
    return ans;
};

Leetcode 693. 交替位二进制数

我的想法就是逐步遍历每一个二进制位

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int l=0;
        while(n){
            if(n&1)
            {
                if(l==1){
                    return false;
                }
                l=1;
                n>>=1;
            }else {
                if(l==-1){
                    return false;
                }
                l=-1;
                n>>=1;
            }

        }
        return true;
    }
};

这样看起来就很复杂所以可以优化一下

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int l=-1;
        for(;n;n>>=1)
        {
            if(l==(n&1)) return false;
            l=n&1;
        }
        return true;
    }
};

Leetcode 2657. 找到两个数组的前缀公共数组

这里是要取两个集合的交集，我们可以用 set 来去重，把两个数组中的元素均存入 set 中，然后减去 set 的大小即为重复元素的数量。

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n=A.size();
        vector<int> c;
        unordered_set<int> cnt;
        for(int i=0;i<n;i++)
        {
            cnt.insert(A[i]);
            cnt.insert(B[i]);
            c.push_back(2*(i+1)-cnt.size());
        }
        return c;
    }
};

看看灵神的优雅代码把

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        uint64_t p=0,q=0;//初始化两个 64 位无符号整数 p 和 q，用于存储两个数组中元素的位掩码。
        for(int i=0;i<A.size();i++)
        {
            p|=1ULL<<A[i];
    //将a[i]的位置在p中标记为1。1ULL<<a[i]生成一个只有第a[i]位为1的二进制数，然后与p进行按位或操作，将该位置标记为1。
            q|=1ULL<<B[i];
            A[i]=popcount(p&q);
            //计算 p 和 q 的按位与结果中 1 的个数，即两个数组中相同元素的个数。
        }
        return A;
    }
};

Leetcode 231. 2 的幂

这个问的是 2 的幂次，而不是偶数，如果 n 小于等于 0 那结果一定为 false。否则如果 n 是 2 的幂其二进制表示应该从第一位开始数第一个 1 即为最高位，也就是只有一个 1 。这个呢就是进行一次 lowbit 运算。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&((n&-n)==n);
    }
};

这里的判断方法还可以是我们对 n 减 1 再和 n 进行与运算

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&(n&(n-1))==0;
    }
};

Leetcode 342. 4 的幂

可以确定一个数如果是 4 的幂一定是 2 的幂，那么就可以开平方后再验证是否为 2 的幂

class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<=0)return false;
        int t=sqrt(n);
        return t*t==n&&(t&(t-1))==0;
    }
};

Leetcode 191. 位 1 的个数

这个题一般思想就是直接遍历

class Solution {
public:
    int hammingWeight(int n) {
        int ans=0;
        for(int i=0;i<32;i++)
        {
            if(n&(1<<i)) ans++;
        }
        return ans;
    }
};

当然也可以找找捷径直接用函数

class Solution {
public:
    int hammingWeight(int n) {
        return __builtin_popcount(n);
    }
};

Leetcode 338. 比特位计数

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> a(n+1);
        for(int i=0;i<=n;i++)
        {
            a[i]=__builtin_popcount(i);
        }
        return a;
    }
};

Leetcode 2595. 奇偶位数

class Solution {
public:
    vector<int> evenOddBit(int n) {
        vector<int> ans(2);
        for(int i=0;i<32;i++)
        {
            if(n&(1<<i)){
                if(i%2) ans[1]++;
                else ans[0]++;
            }
        }
        return ans;
    }
};

Leetcode 2154. 将找到的值乘以 2

这个题我们可以用哈希表记录数组元素，再用函数判断元素是否在数组中。

class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        unordered_set<int> s(nums.begin(),nums.end());
        while(s.count(original))original*=2;
        return original;
    }
};

也可以排序一下直接找

class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        sort(nums.begin(),nums.end());
        for(auto x:nums)
        {
            if(x==original) original*=2;
        }
        return original;
    }
};

Leetcode 3211. 生成不含相邻零的二进制字符串

//偷个懒先空着吧

灵神位运算题单
这里学了知乎 pecco 大神的算法学习笔记 (75)