i was looking google android's source codes, and found this. method's comment is quite funny though.

it does use brian w. kernighan's counting 1 bits method. this code is known as brian kernighan's method(if i'm not wrong he mentions this on the c programming language book) but it was first published by peter wagner in cacm vol. 3, number 5, may 1960 issue with a title "a technique for counting ones in a binary computer".

static int countOnes(u4 val)
{
  int count = 0;
  while (val != 0) {
    val &= val-1;
    count++;
  }
 return count;
}

there are some other ways to improve this code, but it's clear as a crystal that the person who coded this didn't bother to do so. The idea is to turn off the rightmost 1-bit repeatedly until the result is 0. it's very fast as long as the number of 1-bits is small.

i know at least three implementation of this, one of them runs on constant time on constant memory, but i provide divide and conquer method here as described in hacker's delight book. why? i like divide and conquer, we use it all the time(binary search, quicksort, merge sort, etc.).

int countOnes(unsigned int n){
  n = n - ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n + (n >> 4)) & 0x0F0F0F0F;
  n = n + (n >> 8);
  n = n + (n >> 16);
  return n & 0x0000003F;
}