算法之位运算

前言

位运算在我们的学习中占有很重要的地位，从二进制中数的存储等都需要我们进行位运算

一、位运算复习

1.位运算复习

按位与(&)：如果两个相应的二进制位都为1，则该位的结果值才为1，否则为0
按位或( | )：如果两个相应的二进制位中有一个为1，则该位的结果值为1，否则为0
按位异或( ^ )：如果两个相应的二进制位值相同，则该位的结果值为0，否则为1
按位取反( ~ )：对二进制数按位取反，即0变为1，1变为0

其中我们使用最多的为异或操作， 异或操作又可以称为无进位相加。

2.常见的位操作

1.异或的运算规则

1. 两个相同的数异或结果为0
2. 异或满足交换律
3. 任何数异或0都为那个数本身

2.获得一个数的相反数

这个数取反加1为这个数的相反数，即（ -num = (~num + 1) ）

3.获得一个数中二进制位最右侧的1

这个数和它的相反数按位与，即（ num &= -num）

其他的操作我们在下面补充

二、位运算练习

1.不创建第三变量进行交换两个数的值

void Swap()
{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);
}

此时用的是相同的数异或为0，0异或任何数都为那个数
注意，异或操作值可以相同，但不可以对同一块空间的值进行异或，否则会变为0，比如同时对a进行异或。
测试结果：

相关练习

2.不使用比较操作返回较大的数

void Compare()
{int a = 10;int b = 20;int c = a - b;int sya = ((a >> 31) & 1);//获得a的符号位int syb = ((b >> 31) & 1);//获得b的符号位int syc = ((c >> 31) & 1);//获得c的符号位int dif = sya ^ syb;//判断a和b的符号位是否相同//符号位相同则不会产生溢出if (dif == 0){if (syc == 1){printf("最大值为：%d\n", b);}else{printf("最大值为：%d\n", a);}}//可能会产生溢出else{if (sya == 1 && syb == 0){printf("最大值为：%d\n", b);}else{printf("最大值为：%d\n", a);}}
}

测试结果：

注意，两个数相加或者相减都可能产生溢出的情况，下面以char为例：

又比如：

所以这个需要我们进行判断是否会进行溢出，这个直接返回两个数相减的结果是否大于0在溢出情况下并不适用。
练习操作

3.不使用加减乘除等符号进行相应的操作

1.加法

//加法
int Add(int a, int b)
{int sum = a;while (b != 0){sum = a ^ b;//获得要进行进位的位置b = (a & b) << 1;a = sum;}
}

测试结果：

我们异或是不进位相加，所以下面两个数进行与是找到这两数都为1的位置，进行右移在异或相当于向前进1。

2.减法

//减法
int Sub(int a, int b)
{//获得b的相反数int sum = Add(~b, 1);//a和b的相反数进行相加sum = Add(a, sum);return sum;
}

测试结果：

在这里我们可以同通过我们的add函数来得到我们的所要的相反数，原理就是我们的按位取反加1得到

3.乘法

//乘法
int Mul(int a, int b)
{int sum = 0;while (b != 0){if ((b & 1) != 0)//b当前最右侧的是否为1{sum = Add(sum, a);}//模拟相乘的过程a <<= 1;//a进行右移b >>= 1;//b进行左移}return sum;
}

测试结果：

原理：二进制的乘法和十进制的乘法相同，在这里我们把十进制相乘转换为二进制相乘，我们可以通过移位来获得每个相加的数

4.除法

//除法
int div(int a, int b)
{int x = a < 0 ? Add(~a, 1) : a;int y = b < 0 ? Add(~b, 1) : b;int sum = 0;int i = 0;//从第31位开始进行判断for (i = 31; i > -1; i = Sub(i, 1)){if ((x >> i) >= y){sum |= (1 << i);x = Sub(x, y << i);}}return ((a < 0) ^ (b < 0)) ? Add(~sum, 1) : sum;
}
int Div(int a, int b)
{if (b == 0){//0为除数，结束程序exit(-1);}if (a == INT_MIN && b == INT_MIN){return 1;}else if (b == INT_MIN){return 0;}else if (a == INT_MIN){int sum = div(Add(a, 1), b);sum = Add(sum, div(Sub(a, Mul(sum, b)), b));return sum;}else{return div(a, b);}
}

测试结果：

原理：

注意：移动时要注意溢出情况，和除数是否为0。

4.整数二进制中1的个数

void Sum1()
{int a = 20;int sum = 0;while (a != 0){a &= (a - 1);sum++;}printf("1的个数为%d个\n", sum);
}

从上面可以看出我们的（ a &= (a - 1) ）操作是为了消除1
测试结果：

题目练习

5.在其他数都出现两次的数组中找出现一次的一个数

void Single_num()
{int arr[] = { 1,1,2,2,3,4,4,5,5,6,6 };int sum = 0;int i = 0;for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){sum ^= arr[i];}printf("出现一次的数%d\n", sum);
}

这个就是我们使用的交换律，和两个相同的数异或结果为0
测试结果：

练习题目

6.在其他数都出现两次的数组中找出现一次的两个数

void two_Single_num()
{int arr[] = { 1,1,2,2,3,4,5,5,6,6 };int sum = 0;int i = 0;for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){//找到这两个出现一次的数sum ^= arr[i];}//获得这两数异或结果最右侧的1，这个1也是这两个数不相同的位置int sum1 = sum & (~sum + 1);int sum2 = 0;for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){//&的优先级低于 ==//把和这个不相同的一位的值进行按位与，如果结果为0；则可以分为1组if ((sum1 & arr[i]) == 0){//得到的为其中的一位sum2 ^= arr[i];}}printf("出现一次的数%d %d\n", sum^sum2,sum2);
}

测试结果：


题目练习

7.在其他数都出现K次的数组中找出现一次的数

void k_Single_num()
{int arr[] = { 5, 4, 1, 1, 5, 1, 5 };int k = 3; int x = 0;int a[32] = { 0 };for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){//把数组中的数的每个进制位都进行相加x = arr[i];for (int j = 31; j >= 0; j--) {if (x & 1)a[j]++;x >>= 1;}}x = 0;for (int i = 0; i < 32; i++) {//对我们相加的值的每一个进制位进行相应的取模运算就是我们所要的值了x <<= 1;x += a[i] % k;}printf("%d\n", x);
}

测试结果：

原理：

我们可以看到在我们第i位置的值为（(a[i] + b[i]) % 5），同理，在K进制中的两个数在i位上的无进位相加结果位（(a[i] + b[i]) % K），所以k个相同的K进制位相加，那么相加后的结果每一位都为0。所以我们把出现的次数设置成相应的K进制位，最后把相加的结果转化为10进制就是我们所需要的值。

题目练习

总结

位运算还有许多的题目，大家可以在下面找着练习一下。