目录
- 为什么要使用位运算？
- 位运算的运算符
- 位运算核心操作
- 置位
- 单位置位
- 多位置位
- 清零
- 单位清零
- 多位清零
- 取位
- 单位取位
- 多位取位
- 翻转
- 置位
- 题目实战
- 例1：打印32位二进制
- 例2：打印并反转32位二进制
- 例3：十进制转十六进制
- 例4：找出仅出现一次的数字
- 题目中的注意事项
- 1.无符号整数的占位符
- 2.
1 << 31属于未定义行为
为什么要使用位运算？
- 运算优化
- 访问硬件寄存器
- 优化内存占用
位运算的运算符
&：按位与|：按位或^：按位异或~：按位取反>>：按位右移<<：按位左移
位运算核心操作
置位、清零、取位、翻转
注：我们下面都规定二进制的最低位为第0位
置位
单位置位
置位就是置特定位置为1
5的二进制
0000 0101如果我们想要把第3位置1，那么我们可以找一个数字
0000 1000把这个数字与原数字按位或，得到
0000 1101这就成功把第3位置1
而这个
0000 1000本质上就是
1<<3所以把0000 0101的第三位置1，需要的操作就是
5|(1<<3)这里，这个0000 1000，有一个专业名词，叫掩码
进而推广，把x的第n位置1，那么需要的操作就是
x=x|(1<<n)多位置位
假如我们要把
0000 0101的3,4,5三位置位，那么我们需要的操作就是
x=5|(1<<3)|(1<<4)|(1<<5);清零
单位清零
清零就是特定位置置为0,
123的二进制
0111 1011如果我们想把第4位清零
可以构造一个下面的数字
0001 0000然后按位取反
1110 1111然后与原数字按位与，得到
0110 1011这就成功把第4位清零
整理成公式就是
x=x&~(1<<n)多位清零
假如我们要把
0111 1011的3,4,5清零
那么我们就要先生成
1100 0111然后再与原数字按位与
那么实际需要的操作就是
x=123&~((1<<3)|(1<<4)|(1<<5));取位
单位取位
数字66的二进制为
0100 0010想要取它的第1位
先把这个数字右移一位
66>>1得到
0010 0001然后再与
0000 0001按位与
得到
1所以第1位上的数字就是1
取数字x第n位上的数字存入变量tmp，写成C语言代码就是
inttmp=(x>>n)&1;多位取位
数字67
0100 0011假如我们要取这个数字的第1位到第6位
那么我们就需要构造一个掩码
0111 1110然后把这个数字与原数字按位与，得到
0100 0010然后再右移一位， 得到
0010 0001这就成功取出了67的二进制的第1位到第6位
用C语言代码写出来就是
inttmp=(67&(1<<1|1<<2|1<<3|1<<4|1<<5|1<<6))>>1;翻转
异或的运算性质：相同为0，不同为1
所以，我们的掩码可以这样设计：
不需要翻转的位都是0，异或之后，0变为0，1变为1，这样不会改变原有的数字
然后需要翻转的位都是1，异或之后，0变为1,1变为0.这样就实现了翻转。
假如一个数字98，其二进制为
0110 0010如果我们想要把第1位翻转
那么我们的掩码就是
0000 0010再与98异或，得到
0110 0000这就成功翻转了第一位
再比如，如果我们想要把第1,2位翻转，那么我们需要的掩码就是
0000 0110然后再与98异或，得到
0110 0100这也就成功翻转了第1,2位
也就是说，假如有数字x，我们想要翻转第n位数字，C语言代码就是
x=x^(1<<n)题目实战
例1
题目描述
输入一个十进制整数，打印其32位二进制
代码实现
#include<stdio.h>voidprint(unsignedintx){unsignedintmask=1U<<31;charflag=0;while(mask>0){printf("%d",(mask&x)?1:0);flag++;if(flag%4==0){printf(" ");}mask=mask>>1;}return;}intmain(){unsignedintx;scanf("%u",&x);print(x);return0;}例2
题目描述
输入一个十进制整数，打印其32位二进制数，并反转这个数字打印出来
代码实现
#include<stdio.h>voidprint(unsignedintx){unsignedintmask=1U<<31;charflag=0;while(mask>0){printf("%d",(mask&x)?1:0);flag++;if(flag%4==0){printf(" ");}mask=mask>>1;}return;}voidreverse(unsignedintnum){unsignedintans=0;print(num);printf("\n");for(inti=0;i<32;i++){ans=(ans<<1)|(num&1);num=num>>1;}for(inti=31;i>=0;i--){printf("%d",(ans>>i)&1);if(i%4==0&&i>0){printf(" ");}}return;}intmain(){unsignedintnum;scanf("%u",&num);reverse(num);}例3
题目描述
输入一个十进制整数，转换为16进制输出
代码实现
#include<stdio.h>voidturnToHEX(unsignedintnum){printf("0x");for(inti=31;i>0;i-=4){unsignedintmask=0;mask=mask|(1U<<i)|(1U<<(i-1))|(1U<<(i-2))|(1U<<(i-3));unsignedinttmp=num&mask;tmp=tmp>>(i-3);if(tmp<10){printf("%d",tmp);}else{printf("%c",tmp-10+'A');}}}intmain(){unsignedintnum;scanf("%d",&num);turnToHEX(num);return0;}例4
题目描述
给定int数组numns，除1个元素仅出现1次，其余都出现3次，用位运算在O ( 1 ) O(1)O(1)的空间找出这个仅出现一次的数
题目解析
假如我们的数组为{5,5,5,6}
这四个数字对应的二进制如下
0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0我们可以这样想，假如一个数字重复出现三次，那么这个数字的二进制表示上任意一位上的1的个数要么是0，要么是3的倍数，也就是说对3取余的结果为0
也就是说，除了那一个数字之外，所有的数字对任意一位上的贡献都可以通过对3取余摸除掉，而这一个数字仅出现一次。那么思路显而易见
我把这四个二进制数字对应位都相加，得到
0 4 1 3然后每一位分别对3取余
0 1 1 0这恰好就是那个只有一个的数字6！
所以，我们可以开一个数组，用来记录每一位上的1的总个数，把数组{5,5,5,6}中的每一个数字的对应位都累加到这个数组上
最后把这个数组每一个数字都对3取余，得到的二进制数字再转换成十进制，就是最终答案！
虽然使用长度为 32 的数组仍然属于O ( 1 ) O(1)O(1)空间，但我们还可以进一步利用位运算，把这 32 个计数器压缩到ones和twos两个整数中。
这时候，我们可以尝试模拟一个计数器，定义两个整型变量ones与twos并都初始化为0，其中ones代表计数器的第一位，twos代表计数器的第二位。ones与twos的二进制的第n位组合起来，共同用来记录所有数字的二进制的第n位上1的总个数对3取余后的结果
intones=0;inttwos=0;但是你不要把这两个数字都当做0来看，更应该这样看这两个数字：
ones: 00000000 00000000 00000000 00000000 twos: 00000000 00000000 00000000 00000000每一位都对应一个计数器
我们先看ones与twos的第一位
ones: 00000000 00000000 00000000 00000000 ↑ ones的第一位 twos: 00000000 00000000 00000000 00000000 ↑ twos的第一位此时对应二进制数字，暂且称这个数字为cnt
00这里左边的0就是第二位上的数字，对应twos的第一位。右边的0就是第一位上的数字，对应ones的第一位
假如说我们在遍历数字的时候，第一次在某一个数字的二进制的第一位遇到1，那么就要把这个cnt变为
01也就对应十进制数字1，相当于记录第一位目前已经出现了1个1
再次在第一位遇到1时，cnt就要变成
10对应十进制数字2，相当于记录第一位目前已经出现了2个1
再次遇到1时，cnt就要变成
11对应十进制数字3，相当于记录第一位目前已经出现了3个1
但是，实际状态不能进入11，同时我们也要对3取余，因为贡献累计三次就要抹除
所以这时候就要立马把cnt清零
00实际的状态转移应该是：
00 -> 01 -> 10 -> 00所以，遍历完整个数组之后，所有的出现三次的数字对第一位的贡献全部被抹除，仅仅剩下仅出现一次的数字对第一位的贡献，同时遍历完整个数组之后twos的第一位一定是0
同理，nums数组内的数字的第二位、第三位…的总贡献也是如此，遍历完整个数组之后twos的每一位都是0
所以，按照这个逻辑跑一遍之后，ones的值恰好就是我们的答案！那个唯一出现的数字！
那么我们的核心就变为了如何去实现这个计数器
对于ones，如果遇到了数字x，针对数字x的某一位，假如遇到了1，就要把ones的这一位翻转，假如遇到了0，就不改变ones这一位上的值
那么就是：
ones=ones^x但是这有一个问题，如果此时twos的这一位为1，ones的这一位为0，那么翻转完ones的这一位之后就是11，这不符合我们的要求，我们要求一旦遇到3就清零。只有当twos的这一位为0的时候才正常翻转ones的这一位
所以，这里我们需要有这样的设定：
当twos的这一位为1时，要把ones清零 当twos的这一位为0时，正常翻转ones那么，我们可以这样做：
ones=(ones^x)&~twos如果twos的这一位为0，那么~twos的这一位为1，再与原结果与， 不影响原结果
如果twos的这一位为1，那么~twos的这一位为0，再与原结果与，得到0，实现了ones的这一位的清零
对于twos，如果遇到了数字x，针对数字x的某一位
- 如果遇到了1
- 更新后
ones的这一位为0时，要保证twos的这一位为0时被翻转，twos的这一位为1时清零（也就是翻转），即：更新后的ones的这一位为0时直接翻转twos的这一位 - 更新后
ones的这一位为1时，就要保证twos的这一位一定为0
- 更新后
- 如果遇到了0，那么就不做任何变化
那么，我们就可以这样做
twos=twos^x这样实现的是，当x的这一位为0时不做任何变化，当x的这一位为1时翻转了twos的这一位
但是，x的这一位为1时如果更新后的ones的这一位为1，那么要保证twos的这一位为0
那么就可以这样做：
twos=(twos^x)&~ones这就成功得到了两个核心关系式：
ones=(ones^x)&~twos twos=(twos^x)&~ones这就是这个题目最核心的部分。
代码实现
#include<stdio.h>intnums[]={5,5,6,5};intsolve(int*nums,intlen){intones=0;inttwos=0;for(inti=0;i<len;i++){ones=(ones^nums[i])&~twos;twos=(twos^nums[i])&~ones;}returnones;}intmain(){intans=solve(nums,4);printf("%d\n",ans);return0;}题目中的注意事项
1.无符号整数的占位符
无符号整数在格式化输入输出中的占位符为%u，不是%d
2.1 << 31属于未定义行为
直接写一个1，它的类型是有符号的int，1<<31的大小为2 31 2^{31}231会超过int的最大范围[ − 2 31 , 2 31 − 1 ] [-2^{31},2^{31}-1][−231,231−1]导致整型溢出，是未定义行为
应该写1U，加U后缀告诉编译器这是一个unsigned int，而unsigned int的范围为[ 0 , 2 32 − 1 ] [0,2^{32}-1][0,232−1]，这样1<<31就不会发生整型溢出的未定义行为。
或者说，不写1U，也可以这样做
unsignedintmask=1;unsignedinttmp=mask<<31;也是一样的效果。
