第1个回答 2010-03-23
/*输入2个64位数pa1,pa2,返回值是不同位的个数*/
int check64(unsigned long pa1,unsigned long pa2)
{
unsigned long tag;
unsigned long mod = 1;
int counter = 0;
tag = pa1^pa2;/*异或结果中有几个‘1’就有几位不同,再利用mod变量统计‘1’的个数*/
while(mod)
{
if((mod&tag)>0)
{counter++;}
mod <<= 1;/*mod左移1位*/
}
return counter;
}
第2个回答 2010-03-23
ghostabe算法基本正确,可惜用了long long。
要注意long long是有符号的整形,万一a < b,那么while里a始终小于b。
从而a-b是负数
但注意,有些编译器(比如微软的VC/VS)会把(-3)%2算成-1。
因此(a-b)%2改成(a&b)&1比较好
第3个回答 2010-03-23
C语言里头数都是32位的, 那么就应该分两次计算。
每次处理,就是把A的一半和B的一半"异或"(注:不是“与”,一楼写的是错的) 异或的英文xor.
然后把“异或”的结果一位一位统计是否为1, 统计的方法:
1. 可以是把数 R%2 (取模),就可以取出最低位,然后 R=R/2,重复32次就可以了。
第4个回答 2010-03-24
如果要多次进行此运算,建议首先构造一个常量表,记录下8位二进制的数各有多少个1.
#define N 8
int one[1 << N];
void make()
{
int i,j;
for (i = 0; i < 1 << N; ++i)
{
j = i;
while (j)
{
++one[i];
j >>= 1;
}
}
}
int check64(unsigned long a,unsigned long b)
{
unsigned long c;
int counter, d;;
counter = 0;
d = (1 << N) - 1;
c = a^b;
while(c)
{
counter += one[c & d];
c >>= N;
} //这样,这个循环最多执行64 / N次
return counter;
}
当check64调用次数很高时,此方法的对效率的改进很明显
设check64需要调用M次,则总复杂度为O(2^N*N+M * (64 / N)) 可根据M大小,适当选择N
另外,求一个二进制数1的个数,还有一种算法的复杂度正比于答案的:
int one(int x)
{
int cnt = 0;
while(x)
{
++cnt;
x &= x - 1; //这句话的意思是,每次去掉x的最低位的1
}
}
第5个回答 2010-03-23
#include <cstdio>
long long a,b;
int main(void){
scanf("%ld%ld",&a,&b);
int ct=0;
while (a!=0||b!=0){
ct+=(a-b)%2;
a/=2;b/=2;
}
printf("%d\n",ct);
scanf("\n");
return 0;
}