[数据结构与算法]算法基础--位运算

1、位运算符（C语言中的六个位运算符）

2?例题

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

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法将它找出来。

2.1 解题思路

方法一：利用位运算符中的异或运算

????????????????????????A^A =0;? A^0=A (相同为0 不同为1)

具体应用：(1^2^3...^1000)^(1^2^3...^1000^r)=r

2.2 代码展示

# include <stdio.h>
# include <time.h>
# include <stdlib.h>

int main(void)
{
	srand((unsigned)time(NULL));//产生随机数的种子 
	
	int a[1001];
	int i;
	int result = 0;//最终用来存储重复的数  
	
	for ( i=0; i<1001; i++ )//给数组赋1-1000的值 
	{
		a[i] = i + 1;
	}
	a[1000] = rand() % 1000+1;//生成[1,1000]范围内的随机数 
	/* rand()%(b-a+1)+a 范围[a,b] */
	
	for ( i=1; i<1001; i++ )//1^2^3...^1000
	{
		result ^= i;	
	} 
	for ( i=0; i<1001; i++ )//在把上面的结果与1^2^3...^1000^a[1000] 
	{ 
		result ^= a[i];	
	} 
	
	printf("%d", result);
	
	return 0;
}

方法二：开辟辅助空间

# include <stdio.h>
# include <time.h>
# include <stdlib.h>

int main(void)
{
	srand((unsigned)time(NULL));//产生随机数的种子 
	
	int a[1001];
	int b[1001]={0};//辅助空间 记录的是对应下表的数字出现的次数 
	int i;  
	
	for ( i=0; i<1001; i++ )//给数组赋1-1000的值 
	{
		a[i] = i + 1;
	}
	a[1000] = rand() % 1000+1;//生成[1,1000]范围内的随机数 
	/* rand()%(b-a+1)+a 范围[a,b] */
	
	for ( i=0; i<1001; i++ )
	{
		b[a[i]]++;//原数组中没出现一个值 就对该值为下标的辅助数组值加一  
	} 
	for ( i=0; i<1001; i++ )
	{
		if ( b[i] == 2 )
		{
			printf("%d", a[i]);
			return 0;
		}
	}
	
	return 0;
}

2 找出落单的那个数

一个数组中除了某一个数字外，其它的数字都出现两次。请写程序找出这个只出现一次的数字。

2.1 解题思路

这题比第一题要简单一些 与第一题中用到的知识点是一样的?

? ? ?A^A^B^B^C = C (因为有异或交换律 所以顺序无所谓)

2.2 代码展示

# include <stdio.h>
# include <time.h>
# include <stdlib.h>

int main(void)
{
	srand((unsigned)time(NULL));//产生随机数的种子 
	
	int N = 1001;
	int a[N];
	int i;
	int result;//异或后的结果  
	
	for ( i=0; i<=(N-2)/2; i++ )//给数组赋[1,500]的值 
	{
		a[i] = a[N-2-i] = i+1;//a[i] 和 a[N-2-i] 的值相等  
	}
	a[N-1] = rand() % 500+501;//生成[501,1000]范围内的随机数 
	/* rand()%(b-a+1)+a 范围[a,b] */
		
	for ( i=0; i<N; i++ )//连续异或 重复的数会被消掉 只出现一次的数会被保留下来  
	{
		result ^= a[i];
	}
	
	printf("%d", result);
		
	return 0;
} 

3、二进制中1的个数

请输入一个函数，输入一个整数，输出该二进制表示中1的个数。

例如：9的二进制表示为1001，有2位是1

3.1 解题思路?

可以利用&(或运算)和>>(右移)

其中& 全为1是结果才是1 就正好可以很完美的解决题目的要求

3.2 代码展示

# include <stdio.h>

int main(void)
{
	int n;
	int flag = 0;//记录个数  
	
	scanf("%d", &n);
	
	while( n )
	{
		if ( n & 1 )//最低位为1时 flag加一 
			flag++;
		n = n >> 1;	//每一次循环都右移一次 
	}
	
	printf("二进制表示中有%d个1", flag);
	
	return 0;	
} 

4 是不是2的整数次方

用一条语句判断一个数是不是2的整数次方

4.1 解题思路

这里直接说一下 我也是看了很多文章才知道 原来2的整数次方有一个特点 2的整数次方的二进制中只有1个1，其它全为0??

4.2 代码展示

if ( n&(n-1) == 0 )
    printf("YES");
else
    printf("NO");