title: Patterns of set bits in a byte
body: <p>Joel mentioned counting the number of set bits in a byte as a programming question in his <a href="http://www.joelonsoftware.com/articles/fog0000000073.html" rel="nofollow noreferrer">Guerrilla Guide to Interviewing</a>, and talked of a way to take advantage of patterns that occur in the lookup table. I wrote an article about it awhile back after I found the pattern.</p>
  
  <p>To summarize:</p>
  
  <pre><code>Number of bits set in a byte in 16x16
  0   1   1   2   1   2   2   3   1   2   2   3   2   3   3   4  
  1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
  1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
  2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
  1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
  2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
  2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
  3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
  1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
  2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
  2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
  3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
  2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
  3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
  3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
  4   5   5   6   5   6   6   7   5   6   6   7   6   7   7   8  
  </code></pre>
  
  <p>The first row and column are exactly the same, and each position in the grid can be calculated by adding the first values in that position's row and column. Because of this, you only need a lookup table with 16 entries for an 8-bit number, and can just use the first 16 numbers. Then, if you wanted to count the set bits in the number 243, for example, you'd just do:</p>
  
  <pre><code>a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
  x = 243 / 16 =&gt; 15 # (int)
  y = 243 % 16 =&gt; 3
  
  a[x] + a[y] =&gt; 6
  
  # Are there six bits set in the number 243?
  243 = 11110011 # yep
  </code></pre>
  
  <p>The next pattern I noticed after that was that each time you double the size of the NxN grid, each quadrant could be calculated by adding 0, 1, 1, and 2 to each quadrant, respectively, like so:</p>
  
  <pre><code># Make a 4x4 grid on the paper, and fill in the upper left quadrant with the values of the 2x2 grid.  
  # For each quadrant, add the value from that same quadrant in the 2x2 grid to the array.  
  
  # Upper left quad add 0 to each number from 2x2  
  0   1   *   *  
  1   2   *   *  
  *   *   *   *  
  *   *   *   *  
  
  # Upper right quad add 1 to each number from 2×2  
  0   1   1   2  
  1   2   2   3  
  *   *   *   *  
  *   *   *   *  
  
  # Lower left quad add 1 to each number from 2×2  
  0   1   1   2  
  1   2   2   3  
  1   2   *   *  
  2   3   *   *  
  
  # Lower right quad add 2 to each number from 2×2  
  0   1   1   2  
  1   2   2   3  
  1   2   2   3  
  2   3   3   4  
  </code></pre>
  
  <p>Repeat this process two more times, and you'll get the 16x16 grid from above, so I figured there must be some sort of quadtree algorithm that would allow you to start from the grid:</p>
  
  <pre><code>0 1
  1 2
  </code></pre>
  
  <p>and given a number N, generate the lookup table on the fly and figure out the number of bits. So my question/challenge is, <strong>can you figure out an algorithm to do just that?</strong></p>