书中提到五种解法,我也没想到其他方法了。
1.除以2
int Count(BYTE v) { int num = 0; while(v) { if(v % 2 == 1) { num++; } v = v / 2; } return num; }
2. 位操作
int Count(BYTE v) { int num = 0; while(v) { num += v & 0x01; v >>= 1; } return num; }
3.减一操作
int Count(BYTE v) { int num = 0; while(v) { v &= (v - 1); num++; } return num; }
4.分支。5.查表法。这两种相对来说比较固定,没有灵活性,在此不列举了。
扩展问题:
1.如果变量是32位的DWORD,你会使用上述的哪一个算法,或者改进哪一个算法?
个人认为是第三个,时间复杂度是O(M),M为v中1的个数。