# __builtin_popcount() 的 sourece code 如何實作

###### tags: `source code` `進階電腦系統理論與實作` `sysprog`

參考 [Hamming weight - Wikipedia](https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation) 的範例：

<table>
<thead>
<tr>
<th>Expression</th>
<th>Binary</th>
<th>Decimal</th>
<th>Comment</th>
</tr>
</thead>
<tbody>
<tr>
<th>a</th>
<th>01 10 11 00 10 11 10 10</th>
<th> </th>
<th>The original number</th>
</tr>
<tr>
<th>b0 = (a >> 0) & 01 01 01 01 01 01 01 01</th>
<th>01 00 01 00 00 01 00 00</th>
<th>1,0,1,0,0,1,0,0</th>
<th>every other bit from a</th>
</tr>
<tr>
<th>b1 = (a >> 1) & 01 01 01 01 01 01 01 01</th>
<th>00 01 01 00 01 01 01 01</th>
<th>0,1,1,0,1,1,1,1</th>
<th>the remaining bits from a</th>
</tr>
<tr>
<th>c = b0 + b1</th>
<th>01 01 10 00 01 10 01 01</th>
<th>1,1,2,0,1,2,1,1</th>
<th><font color=red>list giving # of 1s in each 2-bit slice of a</font></th>
</tr>
<tr>
<th>d0 = (c >> 0) & 0011 0011 0011 0011</th>
<th>0001 0000 0010 0001</th>
<th>1,0,2,1</th>
<th>every other count from c</th>
</tr>
<tr>
<th>d2 = (c >> 2) & 0011 0011 0011 0011</th>
<th>0001 0010 0001 0001</th>
<th>1,2,1,1</th>
<th>the remaining counts from c</th>
</tr>
<tr>
<th>e = d0 + d2</th>
<th>0010 0010 0011 0010</th>
<th>2,2,3,2</th>
<th><font color=red>list giving # of 1s in each 4-bit slice of a</font></th>
</tr>
<tr>
<th>f0 = (e >> 0) & 00001111 00001111</th>
<th>00000010 00000010</th>
<th>2,2</th>
<th>every other count from e</th>
</tr>
<tr>
<th>f4 = (e >> 4) & 00001111 00001111</th>
<th>00000010 00000011</th>
<th>2,3</th>
<th>the remaining counts from e</th>
</tr>
<tr>
<th>g = f0 + f4</th>
<th>00000100 00000101</th>
<th>4,5</th>
<th><font color=red>list giving # of 1s in each 8-bit slice of a</font></th>
</tr>
<tr>
<th>h0 = (g >> 0) & 0000000011111111</th>
<th>0000000000000101</th>
<th>5</th>
<th>every other count from g</th>
</tr>
<tr>
<th>h8 = (g >> 8) & 0000000011111111</th>
<th>0000000000000100</th>
<th>4</th>
<th>the remaining counts from g</th>
</tr>
<tr>
<th>i = h0 + h8</th>
<th>0000000000001001</th>
<th>9</th>
<th><font color=red>the final answer of the 16-bit word</font></th>
</tr>
</tbody>
</table>

<style>
table {
font-weight:normal;
}
table th:first-of-type {
width: 150px;
}
table th:nth-of-type(2) {
width: 220px;
}
</style>

可以看到他的基本流程就是 ：
1. 根據 a 計算出 c，c 中 **每 2 個 bits** 紀錄的值代表「a 中每 2 bits 有幾個"1"」
2. 根據 c 計算出 e，e 中 **每 4 個 bits** 紀錄的值代表「a 中每 4 bits 有幾個"1"」
3. 根據 e 計算出 g，g 中 **每 8 個 bits** 紀錄的值代表「a 中每 8 bits 有幾個"1"」
4. 根據 g 計算出 i，i 中 **每 16 個 bits** 紀錄的值代表「a 中每 16 bits 有幾個"1"」