二进制位运算题
本期介绍🍖
主要介绍：1. 在不创建临时变量的情况下交换两个变量，2. 计算变量在内存中存放2进制位“1”的个数，3. 求两个数的二进制中不同位的个数，4. 分别打印整数的二进制中奇数位和偶数位，5. 判断一个整数是不是2的n次方，6. 在成对元素的数组中找单身狗。
文章目录
- 1. 交换两个变量(不创建临时变量)
- 1.1 加减法
- 1.2 异或法
- 2. 计算变量在内存中存放2进制位“1”的个数
- 2.1 除二取余法
- 2.2 移位与1法
- 2.3 消1计数法
- 3. 求两个数二进制中不同位的个数
- 4. 打印整数二进制的奇数位和偶数位
- 5. 判断一个整数是不是2的n次方
- 6. 在成对元素的数组中找单身狗
- 6.1 题目1
- 6.2 题目2
1. 交换两个变量(不创建临时变量)
题目： 交换两个整数的内容，在交换的过程中不允许创建第三个临时变量。
一般想要交换两个变量，会通过创建第三个临时变量来完成，就如同想要将两瓶饮料进行交换，需要第三个空瓶一样。代码实现如下所示：
#include<stdio.h>
int main()
{
int a = 10;
int b = 20;
int tmp = 0;
printf("交换前：a=%d, b=%d\n", a, b);
//交换变量a和变量b
tmp = a;
a = b;
b = tmp;
printf("交换后：a=%d, b=%d\n", a, b);
return 0;
}
1.1 加减法
解题思路： 求出两个变量的和，通过和与变量的差，在不创建第三个临时变量的情况下交换两个变量。代码如下所示：
#include<stdio.h>
int main()
{
int a = 10;
int b = 20;
printf("交换前：a=%d, b=%d\n", a, b);
//交换变量a和变量b
a = a + b;
b = a - b;
a = a - b;
printf("交换后：a=%d, b=%d\n", a, b);
return 0;
}
其实不难看出加减法是存在缺陷的，当a和b的值都很大的时候（即都非常接近int类型所能表示范围中的最大值），那么a+b的值必然会超过int型所能存放的极限，导致一些二进制位的丢失，最后交换的结果必然会是错误的。
1.2 异或法
所谓的异或法就是通过异或操作符符 “ ^ ” 来实现交换两变量中的值。在这里不得不说一下异或运算符的一些性质：
性质1： 计算
3 ^ 3表达式，3的二进制位为011，那两个同为011的二进制位进行异或操作，结果必然会是000；同理5 ^ 5的结果也是000，所以不难看出异或的第一条性质为：x^x = 0。
性质2： 计算
3 ^ 0表达式，3的二进制位为011，0的二进制位为000，进行异或操作结果为011，也为3。由此发现不管什么数与0进行异或结果必然会是该数本身，所以异或的第二条性质为：x^0=a。
性质3： 表达式
(3 ^ 3 ^ 5)的计算结果为5，表达式(3 ^ 5 ^ 3)的结果也为5。所以不难看出异或的第三条性质（交换律）：(x ^ x ^ y) = (x ^ y ^ x)。
代码实现如下所示：
#include<stdio.h>
int main()
{
int a = 10;
int b = 20;
printf("交换前：a=%d, b=%d\n", a, b);
//交换变量a和变量b
a = a ^ b;//a里面存放a^b
b = a ^ b;//此时的a^b其实是(a^b)^b,结果为a
a = a ^ b;//此时的a为a^b,b为a,故a^b其实是(a^b)^a,结果为b
printf("交换后：a=%d, b=%d\n", a, b);
return 0;
}
其实可以将a^b得到的结果看作是一个秘盒，a与b通过异或与秘盒结合都可以得到另个数。异或法就没有加减法的缺陷，不会因数据过大使得存储不下。
2. 计算变量在内存中存放2进制位“1”的个数
题目：输入一个整数 n ，计算n在内存中存放的二进制位中1的个数（其中负数用补码表示）。下面会用3种不同的方法来解决这道笔试题。
2.1 除二取余法
在数学中要将十进制数转换成二进制数老师肯定教过一种方法“ 除2取余法 ”。举例如下图所示，计算十进制89化为二进制数。除完所有数，把所有余数从下往上排序后，得到的结果就是89的二进制表示形式为：1011001。
引用此法，每次除2后统计余数为1的情况，这样就可以做到计算变量在内存中存放2进制位为“1”的个数啦。代码如下：
#include<stdio.h>
int sta_bit_num(int n)
{
int count = 0;
while (n)
{
if (n % 2 == 1)
{
count++;
}
n /= 2;
}
return count;
}
int main()
{
int n = 0;
int count = 0;
printf("请输入要计算的数：");
scanf("%d", &n);
count = sta_bit_num(n);
printf("二进制中1的个数：%d\n", count);
}
乍一看似乎没什么问题，但当输入负数时就会发生错误。就譬如输入-1。如下图所示，得出的结果为0，如下图所示：
由于在编写代码时，压根就没有思考过负数的情况。而负数再内中存放的补码的形式与正数是不同的，所以如果还按照原先计算正数的除2取余法来计算负数必然错误。解决方法：将输入的有符号数强制类型转换为无符号数，用除2取余法再对该无符号数进行统计就间接达到效果了。代码如下：
#include<stdio.h>
int sta_bit_num(unsigned int n)
{
int count = 0;
while (n)
{
if (n % 2 == 1)
{
count++;
}
n /= 2;
}
return count;
}
int main()
{
int n = 0;
int count = 0;
printf("请输入要计算的数：");
scanf("%d", &n);
count = sta_bit_num(n);
printf("二进制中1的个数：%d\n", count);
}
2.2 移位与1法
解题思路：一个数只要" &1 "就可以求得该数在内存中存放的二进制位的最低位，再通右移操作符“ >> ”就可以统计32位上所有1的个数了。如下图所示：
代码如下：
#include<stdio.h>
int sta_bit_num(int n)
{
int count = 0;
int i = 0;
for (i = 0; i < 32; i++)
{
if ((n >> i) & 1 == 1)
{
count++;
}
}
return count;
}
int main()
{
int n = 0;
int count = 0;
printf("请输入要计算的数：");
scanf("%d", &n);
count = sta_bit_num(n);
printf("二进制中1的个数：%d\n", count);
}
值得注意，移位与1法会做多余的判断，不管被求的那个数在内存中的二进制位有几个1，始终都是要循环判断32次的。
2.3 消1计数法
根据题意可知，所需统计的仅仅只是二进制位中1的个数，但上面两种方法在判断统计二进制位1的同时还会多余的判断二进制位0。
现在讲解一种非常牛逼的算法“ 消1计数法 ”。该方法是将被求的数" & "比被求数小1的数，即：n & (n-1) 。计算结果会让二进制序列中最低位的那个1变为0。如果再多来几次这样的操作，被求的那个数最终会变成0，这样做就效率不就上来了嘛。如下图所示：
代码为：
#include<stdio.h>
int sta_bit_num(int n)
{
int count = 0;
while (n)
{
n = n & (n - 1);
count++;
}
return count;
}
int main()
{
int n = 0;
int count = 0;
printf("请输入要计算的数：");
scanf("%d", &n);
count = sta_bit_num(n);
printf("二进制中1的个数：%d\n", count);
}
3. 求两个数二进制中不同位的个数
题目： 求两个整数m和n的二进制序列中，有多少位不相同的？输入例子:1999 ， 2299；输出例子:7。
大家在没看过上面的算法思路时，来求解这道题目的思路一定是逐位进行比较的是否相等，效率太低。现在再思考一下这道题的解法，只需要两步：
第1步：按位异或
^计算两个数的相异处。
第2步：用“ 消1计数法 ”统计二进制位中1的个数，即：二进制位相异处的个数。
代码如下：
#include<stdio.h>
int sta_bit_num(int x, int y)
{
int count = 0;
int n = x ^ y;
while (n)
{
n = n & (n - 1);
count++;
}
return count;
}
int main()
{
int a = 0;
int b = 0;
int count = 0;
printf("请输入要计算的两个数：");
scanf("%d%d", &a, &b);
count = sta_bit_num(a, b);
printf("两个数二进制数中不同位的个数：%d\n", count);
}
4. 打印整数二进制的奇数位和偶数位
题目： 获取一个整数二进制序列中所有的偶数位和奇数位，分别打印出二进制序列。
该题先假设二进制序列中最低位为奇数位1，然后我们想办法从高位向低位打印奇数位、偶数位。这样就需要两个循环分别打印奇数位和偶数位了。
#include<stdio.h>
void print_odd(unsigned int n)
{
int i = 0;
printf("打印奇数位：\n");
for (i = 30; i >= 0; i -= 2)
{
printf("%d ", (n >> i) & 1);
}
printf("\n");
}
void print_even(int n)
{
int i = 0;
printf("打印偶数位：\n");
for (i = 31; i >= 1; i -= 2)
{
printf("%d ", (n >> i) & 1);
}
printf("\n");
}
int main()
{
int n = 0;
printf("请输入一个数：");
scanf("%d", &n);
print_odd(n);
print_even(n);
return 0;
}
5. 判断一个整数是不是2的n次方
解题思路：由于整数 2n 的二进制序列只可能存在一个1。所以在求一个数是否为2 ^ n的整数时，只需要判断该数的二进制序列中只存在一个1就可以了。那这里不想也知道用消1计数法最为高效。代码如下：
#include<stdio.h>
int is_pow(int n)
{
int count = 0;
while (n)
{
n = n & (n - 1);
count++;
}
return count;
}
int main()
{
int n = 0;
printf("请输入一个数：");
scanf("%d", &n);
if (is_pow(n) == 1)
{
printf("整数%d是2的n次方\n", n);
}
else
{
printf("整数%d不是2的n次方\n", n);
}
return 0;
}
6. 在成对元素的数组中找单身狗
6.1 题目1
题目： 在{1,2,3,4,5,4,3,2,1}的一组整型数组中，只有一个数出现一次，其他数都是成对出现的，请找出那个只出现过一次的数字。
解题思路：异或操作符有两个个性质x^x = 0、x^0 = x，由于这一组数中只有一个数出现一次，其余数都是成对出现的，将所有数都异或在一起，就可以得到那个单身狗了。实现代码如下：
#include<stdio.h>
int find_once(int arr[], int sz)
{
int i = 0;
int tmp = 0;
for (i = 0; i < sz; i++)
{
tmp = tmp ^ arr[i];
}
return tmp;
}
int main()
{
int arr[] = { 1,2,3,4,5,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
int result = find_once(arr, sz);
printf("那个单身狗是：%d\n", result);
return 0;
}
6.2 题目2
题目： 在{1,2,3,4,5,4,3,2,1,6}的一组整型数组中，有两个数出现一次，其他数都是成对出现的，请找出那两个只出现过一次的数字。
解题思路：异或操作符有两个个性质x^x = 0、x^0 = x，由于这一组数中有两个数只出现一次，其余数都是成对出现的。可以找这两个数的区别，然后将这一组数分成两组，各占一个单身狗。最后分别将两组数异或在一起，就可以得到那两个单身狗了。实现代码如下：
#include<stdio.h>
void find_once(int arr[], int sz, int* pa, int* pb)
{
//1.找两个单身狗的差异
int diff = 0;
int i = 0;
for (i = 0; i < sz; i++)
{
diff = diff ^ arr[i];
}
//2.确定差异的二进制位
int pos = 0;
for (i = 0; i < 32; i++)
{
if ((diff & 1) == 1)
{
pos = i;
break;
}
diff = diff >> 1;
}
//3.按差异分组并将异或后的结果返回
for (i = 0; i < sz; i++)
{
if ((arr[i] >> pos) & 1 == 1)
*pa ^= arr[i];
else
*pb ^= arr[i];
}
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
int a = 0;
int b = 0;
find_once(arr, sz, &a, &b);
printf("找到了单身狗：%d,%d\n", a, b);
return 0;
}
这份博客👍如果对你有帮助，给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️，谢谢！！！
如果有什么疑问或不同的见解，欢迎评论区留言欧👀。