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

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

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

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

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

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

int check64(unsigned long pa1,unsigned long pa2) { unsigned long tag; unsigned long mod = 1; int counter = 0; tag = pa1^pa2; while(mod) { if((mod&tag)>0) {counter++;} mod <<= 1; } return counter; }

#include<stdio.h> void main() { int i,n; i=0; scanf("%d",&n); while(n){ printf("%d",n%10); n/=10; i++; } printf("\n%d位数\n",i); }