復習二進制位的一些操作

  最近在學習數據結構感覺利用二進制位來標記一個數是否存在是特別節省空間的，比如位圖和布隆過濾器是效率比較高的。所以感覺有必要復習一下二進制位的一些常用的操作。

  通過幾個例子來復習一下：

（一）寫一個函數返回參數二進制中 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到這個數的開方任意一個數 都不能整除就是一個素數，否則不是素數。

 當然今天這篇博客很基礎，但是是非常有用的，熟練掌握以后很有用。