位运算在处理整型数值时,可以直接对组成整型数值的个位进行操作.
符号:
&(与) |(或) ^(异或) ~(非/取反)
>>和<<运算符将二进制位进行右移或者左移操作。
>>>运算符将用0填充高位;>>运算符用符号位填充高位;没有<<<运算符;
a | b | ~a | a&b | a|b | a^b |
1 | 1 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 0 | 0 |
相关的性质:
1.交换律 可任意交换运算因子的位置,结果不变
2.结合率 (即(a^b)^c==a^(b^c))
3.对于任何数字x,都有x^x=0,x^0=x,同自己求异或为0,同0求异或为自己。
4.自反性A^B^B=A^0=A,连续和同一因子做异或运算,最终结果为自己。
现在我们来解决一个问题:
题目:找出唯一成对的数
1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素值重复,其他的均只出现一次。每个数组元素只访问一次,设计一个算法,将它找出来;不用辅助储存空间,能否设计一个算法实现?
解题分析:
对于这个题,首先我们需要将1-1000个数放在这个数组当中,然后再调用rand()函数生成一个范围在1-1000中的数字,添加到数组中,这样数组就添加完毕,然后我们再分析题意,其中题目中指名每一个数组元素只能访问一次,所以这里如果用两个for()循环语句来依次判断每一个数在数组中出现的次数这种方案就不行,这是我们就要用到位运算来解决这个问题。
解决这个题目我们采用异或运算符,根据前面提到的第三条性质:对于任何数字x,都有x^x=0,x^0=x,同自己求异或为0,同0求异或为自己。
代码如下:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a[1001],i,j,k=0;
for(i=0;i<=999;i++)
a[i]=i+1;
a[1000]=rand()%(1000)+1;
for(i=0;i<=1000;i++)
printf("%d ",a[i]);
int x1=0;
for(i=1;i<=1000;i++)
x1=x1^i;
for(i=0;i<=1000;i++)
x1=x1^a[i];
printf("%d",x1);
getch();
return 0;
}
运行效果: