经典算法：数一
下面的函数得到数t的二进制表示中1的个数：
template <typename T> size_t foo(T t) {
size_t ret = 0;
while (t) {
t &= t - 1;
++ret;
}
return ret;
}
评论已关闭
秋梦无痕
一场秋雨无梦痕，春夜清风冻煞人。冬来冷水寒似铁，夏至京北蟑满城。
一场秋雨无梦痕，春夜清风冻煞人。冬来冷水寒似铁，夏至京北蟑满城。
下面的函数得到数t的二进制表示中1的个数：
template <typename T> size_t foo(T t) {
size_t ret = 0;
while (t) {
t &= t - 1;
++ret;
}
return ret;
}
评论已关闭
The hacker's delights里头的hard code的做法，会快一点。
假设x是32位的数，统计x中1的个数。共log(32)五步：
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
第一个看过，不过第二个实在觉得凭空想不太好想出来，我觉得肯定是根据什么公式推算出来的吧！
分治法