高分求一个C语言算法设计方法

Question

设计一个高效算法，计算两个64位二进制表示的正整数A和B有多少位是不同的。

Answer 1

#include <stdio.h>
int main(void)
{
unsigned long long A,B,C;
int cnt=0;
scanf("%ld%ld",&A,&B);
C=A^B;//异或运算,不同位置一
do{
cnt+=(int)(C&1); //末位为1计数
C>>=C;//右移一位
}while(C); //全零结束
printf("number of diff bit:%d\n",cnt );
}

Answer 2

/*输入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;
}

Answer 3

ghostabe算法基本正确，可惜用了long long。
要注意long long是有符号的整形，万一a < b，那么while里a始终小于b。
从而a-b是负数
但注意，有些编译器（比如微软的VC/VS）会把(-3)%2算成-1。
因此(a-b)%2改成(a&b)&1比较好

Answer 4

C语言里头数都是32位的， 那么就应该分两次计算。
每次处理，就是把A的一半和B的一半"异或"(注：不是“与”，一楼写的是错的) 异或的英文xor.
然后把“异或”的结果一位一位统计是否为1, 统计的方法:
1. 可以是把数 R%2 （取模）,就可以取出最低位，然后 R=R/2,重复32次就可以了。

Answer 5

如果要多次进行此运算，建议首先构造一个常量表，记录下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
}
}

Answer 6

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