目录为什么要使用位运算位运算的运算符位运算核心操作置位单位置位多位置位清零单位清零多位清零取位单位取位多位取位翻转题目实战例1打印32位二进制例2打印并反转32位二进制例3十进制转十六进制例4找出仅出现一次的数字题目中的注意事项1.无符号整数的占位符2.1 31属于未定义行为为什么要使用位运算运算优化访问硬件寄存器优化内存占用位运算的运算符按位与|按位或^按位异或~按位取反按位右移按位左移位运算核心操作置位、清零、取位、翻转注我们下面都规定二进制的最低位为第0位置位单位置位置位就是置特定位置为15的二进制0000 0101如果我们想要把第3位置1那么我们可以找一个数字0000 1000把这个数字与原数字按位或得到0000 1101这就成功把第3位置1而这个0000 1000本质上就是13所以把0000 0101的第三位置1需要的操作就是5|(13)这里这个0000 1000有一个专业名词叫掩码进而推广把x的第n位置1那么需要的操作就是xx|(1n)多位置位假如我们要把0000 0101的3,4,5三位置位那么我们需要的操作就是x5|(13)|(14)|(15);清零单位清零清零就是特定位置置为0,123的二进制0111 1011如果我们想把第4位清零可以构造一个下面的数字0001 0000然后按位取反1110 1111然后与原数字按位与得到0110 1011这就成功把第4位清零整理成公式就是xx~(1n)多位清零假如我们要把0111 1011的3,4,5清零那么我们就要先生成1100 0111然后再与原数字按位与那么实际需要的操作就是x123~((13)|(14)|(15));取位单位取位数字66的二进制为0100 0010想要取它的第1位先把这个数字右移一位661得到0010 0001然后再与0000 0001按位与得到1所以第1位上的数字就是1取数字x第n位上的数字存入变量tmp写成C语言代码就是inttmp(xn)1;多位取位数字670100 0011假如我们要取这个数字的第1位到第6位那么我们就需要构造一个掩码0111 1110然后把这个数字与原数字按位与得到0100 0010然后再右移一位 得到0010 0001这就成功取出了67的二进制的第1位到第6位用C语言代码写出来就是inttmp(67(11|12|13|14|15|16))1;翻转异或的运算性质相同为0不同为1所以我们的掩码可以这样设计不需要翻转的位都是0异或之后0变为01变为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语言代码就是xx^(1n)题目实战例1题目描述输入一个十进制整数打印其32位二进制代码实现#includestdio.hvoidprint(unsignedintx){unsignedintmask1U31;charflag0;while(mask0){printf(%d,(maskx)?1:0);flag;if(flag%40){printf( );}maskmask1;}return;}intmain(){unsignedintx;scanf(%u,x);print(x);return0;}例2题目描述输入一个十进制整数打印其32位二进制数并反转这个数字打印出来代码实现#includestdio.hvoidprint(unsignedintx){unsignedintmask1U31;charflag0;while(mask0){printf(%d,(maskx)?1:0);flag;if(flag%40){printf( );}maskmask1;}return;}voidreverse(unsignedintnum){unsignedintans0;print(num);printf(\n);for(inti0;i32;i){ans(ans1)|(num1);numnum1;}for(inti31;i0;i--){printf(%d,(ansi)1);if(i%40i0){printf( );}}return;}intmain(){unsignedintnum;scanf(%u,num);reverse(num);}例3题目描述输入一个十进制整数转换为16进制输出代码实现#includestdio.hvoidturnToHEX(unsignedintnum){printf(0x);for(inti31;i0;i-4){unsignedintmask0;maskmask|(1Ui)|(1U(i-1))|(1U(i-2))|(1U(i-3));unsignedinttmpnummask;tmptmp(i-3);if(tmp10){printf(%d,tmp);}else{printf(%c,tmp-10A);}}}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取余后的结果intones0;inttwos0;但是你不要把这两个数字都当做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的第一位此时对应二进制数字暂且称这个数字为cnt00这里左边的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这一位上的值那么就是onesones^x但是这有一个问题如果此时twos的这一位为1ones的这一位为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那么就不做任何变化那么我们就可以这样做twostwos^x这样实现的是当x的这一位为0时不做任何变化当x的这一位为1时翻转了twos的这一位但是x的这一位为1时如果更新后的ones的这一位为1那么要保证twos的这一位为0那么就可以这样做twos(twos^x)~ones这就成功得到了两个核心关系式ones(ones^x)~twos twos(twos^x)~ones这就是这个题目最核心的部分。代码实现#includestdio.hintnums[]{5,5,6,5};intsolve(int*nums,intlen){intones0;inttwos0;for(inti0;ilen;i){ones(ones^nums[i])~twos;twos(twos^nums[i])~ones;}returnones;}intmain(){intanssolve(nums,4);printf(%d\n,ans);return0;}题目中的注意事项1.无符号整数的占位符无符号整数在格式化输入输出中的占位符为%u不是%d2.1 31属于未定义行为直接写一个1它的类型是有符号的int131的大小为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]这样131就不会发生整型溢出的未定义行为。或者说不写1U也可以这样做unsignedintmask1;unsignedinttmpmask31;也是一样的效果。