遇见蓝桥遇见你，不负代码不负卿！

第二章”递归“已将更新咯，欢迎铁汁们点评！蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（上）_安然无虞的博客-CSDN博客

目录

一、位运算符总结概述

1、按位与 &

2、按位或 |

3、按位取反 ~

4、按位异或 ^

5、补充了解移位运算

1.左移<<

2.右移>>

3.无符号右移>>>

6、补充了解原码反码补码

1.原码

2.反码

3.补码

二、蓝桥云课：位运算的奇巧淫技

1、判断奇偶数

​

解题思路：

代码执行

2、判断二进制位是1还是0（两种方法）

方法一解题思路

 代码执行

方法二解题思路

代码执行

3、交换两个整型变量的值（异或法）

解题思路

 代码执行

4、不用判断语句，求整数的绝对值

解题思路

代码执行

三、实战例题

例1、如何找数组中唯一成对的那个数

解题思路

代码执行

例2、找出落单的那个数

解题思路

代码执行

例3、二进制中1的个数

方法1解题思路

代码执行

方法2解题思路

代码执行

方法3解题思路

代码执行

例4、是不是2的整数次方

解题思路

代码执行

例5、将整数的奇偶位互换

解题思路

思考题：出现K次与出现一次

四、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！

五、笔者请求

---

推荐给老铁们两个学习网站：

面试利器&算法学习：牛客网

风趣幽默的学人工智能：人工智能学习​​​​​​​

【前言】：笔者是根据蓝桥杯官方发布的视频整理出的笔记，博文是由笔记二次整理而来，具有较强的针对性，打算参赛的小伙伴跟着笔者一起行动起来吧！为了方便更多的铁汁们，代码示例中笔者采用的是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