#include <stdio.h>#include <stdlib.h>#include <time.h>int BitCount2(unsigned int n) { unsigned int c =0 ; while(n!=0) { n &= (n -1) ; // 清除最低位的1 c++; } return c ; } int BitCount4(unsigned int n) { n = (n &0x55555555) + ((n >>1) &0x55555555) ; // n相邻位相加 n = (n &0x33333333) + ((n >>2) &0x33333333) ; // n(以2为单位)相邻位相加 n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ; // n(以4为单位)相邻位相加 n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ; // n(以8为单位)相邻位相加 n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ; // n(以16为单位)相邻位相加 return n ; } int main( ){long i=100000000;unsigned int n;clock_t start, finish; double Total_time; start = clock(); while(--i)n=BitCount2(123456789);finish = clock(); printf( "bit number::%d \n", n); Total_time = (double)(finish-start) / CLOCKS_PER_SEC; printf( "BitCount2::%f seconds\n", Total_time); printf( "\n", n); i=100000000;start = clock(); while(--i)n=BitCount4(123456789);finish = clock(); Total_time = (double)(finish-start) / CLOCKS_PER_SEC; printf( "bit number::%d \n", n); printf( "BitCount4::%f seconds\n", Total_time); return 0;}
运行结果:
如上所示:一个好的算法是多么重要。。。