c/c++ 演算法技巧

今天看code 看到一個莫名其妙的東西，上網搜尋一下

unsigned popcount (unsigned u)
{
u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
return u;
}

原來是個不知為何的演算法得出來的結果，原理大概是查表，此用法只適用於32位無號整數，目的是在算input u 總共有幾個bit為1，稍微紀錄一下。

=> 使用分治法
https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F

簡單來說就是先算出兩個bit裡面有幾個1
A=b'1111
(A) &(b'0101) +(A>>1)&(b'0101) =b'1010 
代表第
0,1 bit 有兩個為1 
2,3bit 有兩個為1
接著就是 shift跟加法的問題



ref.

http://blog.csdn.net/rappy/article/details/1788969