Purpose of the init() instructions in popcount (The Go Programming Language Book)

<p>Hi,</p> <p>I&#39;m working some days now on the example here:</p> <p><a href="https://github.com/adonovan/gopl.io/blob/master/ch2/popcount/main.go" rel="nofollow">https://github.com/adonovan/gopl.io/blob/master/ch2/popcount/main.go</a></p> <p>After some days of research I finally undestand what the instruction in the init function does. But I don&#39;t know why it does it.</p> <p>Can someone please explain, how does this implementation of popcount work? I also still not understand how exactly the PopCount() algorithm works.</p> <p>I&#39;m sorry if this is a newbie question, but these concepts of computer science / math are new to me (shifting bits, bitwise comparison) - coming from a front end and PHP world...</p> <p>Thanks!</p> <hr/>**评论：**<br/><br/>FUZxxl: <pre><p>So, the popcount (<strong>pop</strong>ulation <strong>count</strong>, also known as sideways add (sadd) or Hamming weight) of a number is the number of set bits in the number. For example, the number 42 has binary representation <code>101010</code> and population count 3. The <code>init</code> function populates the <code>pc</code> table so at each index it contains the popcount of the index. This is achieved by observing that</p> <pre><code>popcount(i) = popcount(i/2) + (i &amp; 1) </code></pre> <p>where <code>i &amp; 1</code> is the last bit of <code>i</code> and <code>i/2</code> is half <code>i</code>, equal to <code>i &gt;&gt; 1</code>, i.e. <code>i</code> right-shifted by one. Here is an example of this, all numbers are in binary:</p> <pre><code>popcount(101010) = popcount(10101) + 0 popcount(10101) = popcount(1010) + 1 popcount(1010) = popcount(101) + 0 popcount(101) = popcount(10) + 1 popcount(10) = popcount(1) + 0 popcount(1) = popcount(0) + 1 </code></pre> <p>Note that due to Go rules, <code>pc</code> starts out initialized with all zeros. Thus, the entry for <code>pc[0]</code> is already correct which makes the rest of the algorithm work as we initialize from i = 0 to 255, so each iteration of the loop (except for the first one with <code>i = 0</code>) only ever uses values of <code>pc[i]</code> that have already been initialized.</p> <p>In the <code>PopCount</code> function itself, the input is split into bytes, the population counts of each byte is looked up in <code>pc</code> and then the results are summed to yield the population count of <code>x</code>.</p></pre>ls42: <pre><p>Thanks for the (exquisite) explanation. I get it now :)</p> <p>Have a splendid day</p></pre>ls42: <pre><p>Aahh, it all makes sense now. So I guess when you do a byte() on a uint64 it just takes the most right 8 bits from the whole number,is that correct?</p></pre>FUZxxl: <pre><p>Yes!</p></pre>ls42: <pre><p>I am very happy now.</p></pre>kpmy: <pre><p>Bit magic :D</p></pre>ls42: <pre><p>-_-</p></pre>anacrolix: <pre><p>No good, two bit...</p></pre>