复习二进制位的一些操作

  最近在学习数据结构感觉利用二进制位来标记一个数是否存在是特别节省空间的，比如位图和布隆过滤器是效率比较高的。所以感觉有必要复习一下二进制位的一些常用的操作。

  通过几个例子来复习一下：

（一）写一个函数返回参数二进制中 1 的个数（与运算）

int count_one_bits(size_t value)
{
	size_t i = 1;
	int count = 0;
	while(1)
	{
		if((value&i)==i)//1&1==1，1&0=0；
			printf("1",count++);
		else 
			printf("0");
		i <<= 1;
		if(i>value)
			break;
	}
	printf("\n");
	return count;
}

int count_one_bits(size_t value)
{
	int count = 0;
	while (value)
	{
		count++;
		value = value&(value - 1);
	}
	printf("\n");
	return count;
}

  1&1=1；1&0=0；    num<<1等价于num*2;num>>1等价于num/2;

  这一题主要运用或（&）的性质和<<，可以计算出一个数二进制位中1的个数。

（二）交换两个一样大的数组的内容（异或运算）

int i,A[10]={1,2,3,4,5,6,7,8,9,10};
int B[10]={11,12,13,14,15,16,17,18,19,20};
for(i=0;i<sizeof(A)/sizeof(A[0]);i++)
{	
    A[i]=A[i]^B[i];
    B[i]=A[i]^B[i];
    A[i]=A[i]^B[i];
}

  异或的是有那么一个公式的，a=a^b;b=a^b;a=a^b;即可交换a和b的值。

（三）求两个数的最大公约数（取模）

#include<stdio.h>

int main()
{
int m,n,p;
printf("Input two numbers:");
scanf("%d%d",&m,&n);
while(m%n != 0)
{
  p = m%n;
  m = n;
  n = p;
}
printf("最大公约数是%d\n",n);
}

（四）判断一个数是否是素数（常用素数，要理解素数怎么来的）

int is_prime(int n)
{
	int i;
	for(i=2;i<(double)sqrt((double)n);i++)
		if(n%i==0)
			return 0;
	return 1;
}

  判断一个数是否是素数，只要这个数除以 2到这个数的开方任意一个数 都不能整除就是一个素数，否则不是素数。

 当然今天这篇博客很基础，但是是非常有用的，熟练掌握以后很有用。