什么是位运算

位运算在处理整型数值时,可以直接对组成整型数值的个位进行操作.

符号:

&(与) |(或) ^(异或) ~(非/取反)

>>和<<运算符将二进制位进行右移或者左移操作。

>>>运算符将用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;
 } 

运行效果:

什么是位运算

 

上一篇:mysql索引优化实战<二>


下一篇:LeetCode 罗马数字转整数