復(fù)習(xí)二進(jìn)制位的一些操作

  最近在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)感覺(jué)利用二進(jìn)制位來(lái)標(biāo)記一個(gè)數(shù)是否存在是特別節(jié)省空間的，比如位圖和布隆過(guò)濾器是效率比較高的。所以感覺(jué)有必要復(fù)習(xí)一下二進(jìn)制位的一些常用的操作。

  通過(guò)幾個(gè)例子來(lái)復(fù)習(xí)一下：

（一）寫(xiě)一個(gè)函數(shù)返回參數(shù)二進(jìn)制中 1 的個(gè)數(shù)（與運(yùn)算）

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等價(jià)于num*2;num>>1等價(jià)于num/2;

  這一題主要運(yùn)用或（&）的性質(zhì)和<<，可以計(jì)算出一個(gè)數(shù)二進(jìn)制位中1的個(gè)數(shù)。

（二）交換兩個(gè)一樣大的數(shù)組的內(nèi)容（異或運(yùn)算）

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];
}

  異或的是有那么一個(gè)公式的，a=a^b;b=a^b;a=a^b;即可交換a和b的值。

（三）求兩個(gè)數(shù)的最大公約數(shù)（取模）

#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("最大公約數(shù)是%d\n",n);
}

（四）判斷一個(gè)數(shù)是否是素?cái)?shù)（常用素?cái)?shù)，要理解素?cái)?shù)怎么來(lái)的）

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

  判斷一個(gè)數(shù)是否是素?cái)?shù)，只要這個(gè)數(shù)除以 2到這個(gè)數(shù)的開(kāi)方任意一個(gè)數(shù) 都不能整除就是一個(gè)素?cái)?shù)，否則不是素?cái)?shù)。

 當(dāng)然今天這篇博客很基礎(chǔ)，但是是非常有用的，熟練掌握以后很有用。