经典面试题（1）：统计整数中1的个数

#include <iostream> using namespace std; typedef unsigned __int64 uint64; // 64位 /* * 统计一个整数中1的个数 * 作者：樊列龙 * from: * 时间：2014-01-15 */ int count1(uint64 num) { int count=0; while(num){ count += num & 1; num >>= 1; } return count; } int count2(uint64 num) { int count=0; uint64 flag = 1; while(flag){ if(flag & num) { count++; } flag = flag << 1; } return count; } // 如果大多数位置为0则使用下面的算法比较好. // 这里使用一种利用宏的技巧，而不是使用循环，其实原理和使用循环是一样的。 // 因为最多有64个1，因此只要把（64+1）中情况全部写出来就行了 #define f(y) if ((x &= x-1) == 0) return y; // 如果是1比较多可以把宏定义成这样 // #define f(y) if ((x |= x+1) == hff) return 64-y; int count3(uint64 x) { if (x == 0) return 0; f( 1) f( 2) f( 3) f( 4) f( 5) f( 6) f( 7) f( 8) f( 9) f(10) f(11) f(12) f(13) f(14) f(15) f(16) f(17) f(18) f(19) f(20) f(21) f(22) f(23) f(24) f(25) f(26) f(27) f(28) f(29) f(30) f(31) f(32) f(33) f(34) f(35) f(36) f(37) f(38) f(39) f(40) f(41) f(42) f(43) f(44) f(45) f(46) f(47) f(48) f(49) f(50) f(51) f(52) f(53) f(54) f(55) f(56) f(57) f(58) f(59) f(60) f(61) f(62) f(63) return 64; } int count4(uint64 num) { int n = 0; while(num) { num &= (num-1); n++; } return n; } ///====================================================== int count5(uint64 num, int bitSize); int count5(uint64 num) { return count5(num, sizeof(num) * 8); } int count5(uint64 num, int bitSize) { if(bitSize == 1) { return num; } else { int shiftLen = bitSize >> 1; // 移位数 int numR = num >> shiftLen; // 取高shiftLen位数字 int numL = num & (0xffffffffffffffff >> (sizeof(num) * 8-shiftLen));// 取低shiftLen位数字 return count5(numR, shiftLen) + count5( numL, shiftLen);// 合并 } } ///====================================================== const uint64 m1 = 0x5555555555555555; //binary: 0101... const uint64 m2 = 0x3333333333333333; //binary: 00110011.. const uint64 m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ... const uint64 m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ... const uint64 m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ... const uint64 m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones ... const uint64 hff = 0xffffffffffffffff; //binary: all ones const uint64 h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3... int count6(uint64 x) { x = (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits x = (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits x = (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits x = (x & m8 ) + ((x >> 8) & m8 ); //put count of each 16 bits into those 16 bits x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits return x; } //This uses fewer arithmetic operations than any other known //implementation on machines with slow multiplication. //It uses 17 arithmetic operations. int count7(uint64 x) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits x += x >> 8; //put count of each 16 bits into their lowest 8 bits x += x >> 16; //put count of each 32 bits into their lowest 8 bits x += x >> 32; //put count of each 64 bits into their lowest 8 bits return x &0xff; } //This uses fewer arithmetic operations than any other known //implementation on machines with fast multiplication. //It uses 12 arithmetic operations, one of which is a multiply. int count8(uint64 x) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits return (x * h01)>>56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... } int main() { cout << count1(27834) << endl; cout << count2(27834) << endl; cout << count3(27834) << endl; cout << count4(27834) << endl; cout << count5(27834) << endl; cout << count6(27834) << endl; cout << count7(27834) << endl; cout << count8(27834) << endl; cin.get(); }