蓝桥杯算法竞赛系列第一章——位运算的奇巧淫技及其实战
遇见蓝桥遇见你，不负代码不负卿！
第二章”递归“已将更新咯，欢迎铁汁们点评！蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（上）_安然无虞的博客-CSDN博客
目录
【前言】：笔者是根据蓝桥杯官方发布的视频整理出的笔记，博文是由笔记二次整理而来，具有较强的针对性，打算参赛的小伙伴跟着笔者一起行动起来吧！为了方便更多的铁汁们，代码示例中笔者采用的是C语言编写。
【友情提示】：在接下来的两个半月中，博主将会持续推出两个系列的博文，一是零基础搞定C语言，二是蓝桥杯算法竞赛，包括一些刷题感悟与总结哦，当然后面还会有往年的蓝桥杯真题总结，喜欢的铁汁们可以关注笔者哦。
一、位运算符总结概述
1、按位与 &
如果两个二进制位都为1，则结果是1，否则是0
2、按位或 |
如果两个二进制位都为0，则结果是0，否则是1
3、按位取反 ~
该位为0，则变为1，否则变为0
4、按位异或 ^
如果两个数字的二进制位相同，则结果为0，相异则结果为1
5、补充了解移位运算
实际运用当中可以根据情况用左移/右移做快速的乘除法，这样效率会高很多。
1.左移<<
最左侧不要了，最右侧直接补0；（左移相当于乘法，如左移1位，相当于乘以2的1次方）
2.右移>>
右移相当于除法...
因为C语言中没有特别引入无符号右移，所以C语言中的右移分成算术右移和逻辑右移两种。
算术右移就是最右侧位不要了，最左侧直接补符号位（大多数机器上采用的是算术右移）
所以应用C语言中的右移需要格外注意负数的情况。
逻辑右移就是最右侧不要了，最左侧直接补0
注意：对于int 类型的数据，移位超出32位时，需要模上32，比如1 << 35 == 1 << 3；
那么对于long类型来说，超出时需要模上64（模-->求余）
3.无符号右移>>>
引入Java中的无符号右移，它和左移的用法一直，也就是逻辑右移，最右侧不要了，最左侧补0
6、补充了解原码反码补码
1.原码
直接将这个数字按照正负数的形式翻译成二进制即可
2.反码
原码的符号位不变，其他位按位取反即可
3.补码
反码+1即可得到补码
注意：正数和无符号数的原码、反码、补码都相同，只有求负数的反码、补码才采用上面的计算
-
int a = 20; //整型a是4个字节，32位
-
-
// 00000000 00000000 00000000 00010100 - 原码
-
// 00000000 00000000 00000000 00010100 - 反码
-
// 00000000 00000000 00000000 00010100 - 补码
-
-
int b = -10;
-
-
// 10000000 00000000 00000000 00001010 - 原码
-
// 11111111 11111111 11111111 11110101 - 反码
-
// 11111111 11111111 11111111 11110110 - 补码
声明：对于数据的存储只简单介绍到这里，详细介绍将放在后面零基础搞定C语言系列
二、蓝桥云课：位运算的奇巧淫技
1、判断奇偶数
解题思路：
拿int型举例，int占4个字节，也就是32位，对于整型来说，数据存放在内存当中存放的是其补码形式，由于第一位(注意上面图片中第1位的位置)前面的数都是2的1及以上次方，只有当第一位是1时为奇数，是0时为偶数，大家先理解一下上面这句话，明白了以后，如果我们想要判断一个整数的奇偶性，只需要和1进行按位&运算即可，由于1中除第1位以外每一位都是0，又因为任何数中的每一位与1中的0位做&运算，与0位做&运算的位结果都是0，所以偶数和1进行&运算是0，奇数和1进行&运算是1
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
printf("判断奇偶数：\n");
-
int num = 12;
-
if ((num & 1) == 0)
-
{
-
printf("%d是偶数\n",num);
-
}
-
else
-
{
-
printf("%d是奇数\n", num);
-
}
-
return 0;
-
}
2、判断二进制位是1还是0（两种方法）
例：int x = 86; // 定义一个整型变量x, 并将其初始化为86
现需要判断第5位是1还是0， 该如何操作？
方法一解题思路
老样子，还是用整数1执行操作，由于是判断x的第五位是1还是0，所以取整数1，让1左移（5 - 1）位，也就是左移4位，然后直接和x进行按位&操作，最后再右移4位至该数二进制第一位，若第1位是0，则第5位上的二进制数是0，否则是1
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int x = 86;
-
printf("判断整数86的二进制第5位是1还是0:\n");
-
//运算符的使用有优先级，我们不必特意去记这个，可能存在歧义的时候，就加上括号，这样既保险又省心
-
if ((((1 << 4) & x) >> 4) == 0)
-
{
-
putchar('0');
-
}
-
else
-
{
-
putchar('1');
-
}
-
return 0;
-
}
方法二解题思路
该方法较方法一就简单多了，它利用了“判断奇偶数”的解题思想，首先，让x右移（5 - 1）位，即右移4位，然后再和1相&，如果结果是0，则第5位上的二进制数是0，否则是1。
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int x = 86;
-
printf("判断整数86的二进制第5位是1还是0:\n");
-
if (((x >> 4) & 1) == 0)
-
{
-
putchar('0');
-
}
-
else
-
{
-
putchar('1');
-
}
-
return 0;
-
}
3、交换两个整型变量的值（异或法）
解题思路
补充：异或，可理解为不进位加法，如1+1 = 0, 0 + 0 = 0, 1 + 0 = 1
异或：如果两个数字的二进制位相同，则结果为0，相异则结果为1.
异或的性质：
1.交换律：可任意交换运算因子的位置，结果不变；
如：a ^ b ^ c = b ^ a ^ c;
2.结合律：即(a ^ b) ^ c == a ^ ( b ^ c) ;
3.对于任何数x, 都有x ^ x = 0, x ^ 0 = x,同自己求异或为0，同0求异或为自己
4.自反性：A ^ B ^ B = A ^ 0 = A, 连续和同一个因子做异或运算，最终结果为自己
说了这么多，那么位运算中的异或到底跟“交换两个整型变量的值”这个题目有什么联系呢，请听笔者向铁汁们慢慢道来...
例题：int A = 10, int B = 20, 在不引入第3个变量的情况下，交换两个变量的值（除了采用异或法，用加减法也可以，这个将在后面的零基础搞定C语言中详细介绍）
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int A = 10;
-
int B = 20;
-
printf("交换前A = %d B = %d\n", A, B);
-
A = A ^ B;
-
B = A ^ B;
-
A = A ^ B;
-
printf("交换后A = %d B = %d\n", A, B);
-
return 0;
-
}
4、不用判断语句，求整数的绝对值
解题思路
如果上面的表述看不懂也没有关系，表达式已经给出来了，你只需要知道当遇到不用判断语句求整数的绝对值用它即可。
代码执行
本题采用Java语言编写
-
public class Test10_16 {
-
public static void main(String[] args) {
-
-
System.out.println("不用判断语句，求整数的绝对值");
-
int num5 = -100;
-
System.out.println("num5的绝对值是：" + ((num5 ^ (num5 >> 31)) + (num5 >>> 31)));
-
}
-
}
三、实战例题
例1、如何找数组中唯一成对的那个数
1-10这10个数放在含有11个元素的数组中，只有唯一一个元素重复，其他均只出现一次，要求每个数组元素只能够被访问一次，请设计一个算法，将它找出来，不用辅助存储空间，能否设计一个算法实现？
解题思路
想要计算出本题，需要我们掌握异或的性质，思路：定义一个数x，并将它初始化成0，将它和数组中的11个数异或，再和1-10这10个自然数异或，最终的结果就是那个数。
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int arr[] = { 1,2,3,2,6,4,7,5,8,9,10 };
-
int sz = sizeof(arr) / sizeof(arr[0]);
-
int x = 0;//之所以将x初始化为0，因为0与任何数异或都是它自己
-
for (int i = 0; i < sz; i++)
-
{
-
x = x ^ arr[i];
-
}
-
for (int i = 1; i <= sz - 1; i++)
-
{
-
x = x ^ i;
-
}
-
printf("%d\n", x);
-
return 0;
-
}
例2、找出落单的那个数
一个数组中除了某一个元素中之外，其他的元素都出现了两次，请写程序找出这份只出现一次的数字
解题思路
这道题比第一道题还要简单，直接异或即可
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int arr[] = { 1,1,2,3,3,4,4,5,5 };
-
int sz = sizeof(arr) / sizeof(arr[0]);
-
int x = 0;
-
for (int i = 0; i < sz; i++)
-
{
-
x = x ^ arr[i];
-
}
-
printf("%d\n", x);
-
return 0;
-
}
例3、二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数
如9的二进制表示为00000000 00000000 00000000 00001001，有两个1
方法1解题思路
笨方法，把1给数出来-->让1动，那个整数一直不动，利用32次循环，每一次都是将相应位上的数字进行按位&操作
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int num = 9;
-
int count = 0;//用于计数
-
for (int i = 0; i < 32; i++)
-
{
-
//一定要注意写法，虽然简单，但是容易出错
-
if ((num & (1 << i)) == (1 << i))-----注意写成if((num & (1 << i) == 1)就错了
-
{
-
count++;
-
}
-
}
-
printf("%d\n", count);
-
return 0;
-
}
方法2解题思路
其实就是方法1的一个变形，保持1的位置不动，让那个整数不断右移
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int num = 9;
-
int count = 0;
-
for (int i = 0; i < 32; i++)
-
{
-
if (((num >> i) & 1) == 1)
-
{
-
count++;
-
}
-
}
-
printf("%d\n", count);
-
return 0;
-
}
方法3解题思路
技多不压身，铁汁们最好将这三种方法全部掌握，保不准在之后的题目中会用到。
利用循环，当这个整数变为0时循环结束，循环体中执行num = (num - 1) & num 这个操作
可能大家一开始的时候想不到这个解法，笔者也是，我一开始看的时候也很蒙，但是当你看完了之后会有种醍醐灌顶的感觉，说明你理解了原来还可以这样。虽然之前我们可能想不到，但是既然现在遇到了，那就要记住它，以后再出现的时候就要会运用了，一起加油吧铁汁们。
代码执行
-
#include<stdio.h>
-
int main()
-
{
-
int num = 9;
-
int count = 0;
-
while (num != 0)
-
{
-
num = (num - 1) & num;
-
count++;
-
}
-
printf("%d\n", count);
-
return 0;
-
}
例4、是不是2的整数次方
同一条语句判断一个整数是不是2的整数次方
解题思路
判断一个整数是不是2的整数次方，也就是这个整数的二进制中只有一个1
代码执行
看，这里就用到了上一题的方法3，所以我们该不该记住呢...
-
#include<stdio.h>
-
int main()
-
{
-
int num = 9;
-
if (((num - 1) & num) == 0)
-
{
-
printf("YES\n");
-
}
-
else
-
{
-
printf("NO\n");
-
}
-
return 0;
-
}
当你刷题的时候刷到了这题请注意要添加一个条件哦，就是这个num一定是大于0的，因为它是2的幂。
例5、将整数的奇偶位互换
注意：用1做&运算其实就是保留，用0做&运算其实就是消除
解题思路
-
#include<stdio.h>
-
int main()
-
{
-
int num = 9; //0000....00001001
-
int a = 0xaaaaaaaa; //1010....10101010
-
int b = 0x55555555; //0101....01010101
-
int c = num & a; //目的是保留num的偶数位
-
int d = num & b; //目的是保留num的奇数位
-
-
printf("%d\n", ((c >> 1) ^ (d << 1)));
-
-
return 0;
-
}
思考题：出现K次与出现一次
题目描述：数组中只有一个数出现了1次，其他数都出现了K次，请输出这出现一次的数，需要用位运算，不可以采用暴力求解法。
注意：以后笔者的博文中可能每篇都会有下一道思考题留给铁汁们做，等到笔者下次发表该系列博文的时候会公布解题思路权当复习了。
四、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！
大学可以说是人生中最美好的阶段，我们虽然有压力，但是相比以后工作、生活而言就算不上什么了，对于身处IT浪潮中的我们而言，愿大家不负韶华，珍惜机会，丰富经历，学有所成。
五、笔者请求
铁汁们，笔者的博文都是由纸质和电子笔记的二次加工而来的，花费了比较多的心力，感觉写的还可以的话，给俺来个点赞，收藏加关注呗，你们的支持就是笔者最大的动力
第二章“递归”已经更新咯，欢迎铁汁们指点。蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（上）_安然无虞的博客-CSDN博客
准备算法竞赛，或者是想提升基础算法能力的铁汁们都可以订阅哦，免费的啦，周周都有更新。
https://blog.csdn.net/weixin_57544072/category_11418082.html?spm=1001.2014.3001.5482
文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。
原文链接：bit-runout.blog.csdn.net/article/details/120798996
- 点赞
- 收藏
- 关注作者
评论（0）