The Bit counting Problem

This problem was first given to me in march 2005 by Thorkil Naur, a collegue of mine at IBM.

Problem
Write C-code that fills an array of integers so that the i'th element contains the number of bits set to 1 in i.


  int buf[N];



  buf[0] = 0;

  buf[1] = 1;

  buf[2] = 1;

  buf[3] = 2;

  buf[4] = 1;

  buf[5] = 2;

  buf[6] = 2;

  buf[7] = 3;

  .

  .

  .

  buf[N - 1] =

I came up with a solution, that You can see here, but Thorkil's solution is a bit more simple and beautiful, see Thorkil's solution here.