Which count set bit function has the better performance?

Question

int a(int i) {
  int c = 0;
  while(i > 0) {
    if(i&1){c++;}
    i >>= 1;
  }
  return c;
}

// what does this function do?
int b(int i) {
  static char chs[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
  int c = 0;
  while(i > 0) {
    c += chs[15&i];
    i >>= 4;
  }
  return 0;
}

How to use gettimeofday() function to verify their performance and which one has better performance? I am not familiar with count bit, so please explan with more details. Thank you!

Answer 1

Whereas the first function loops through the given number, checking one bit at a time, the second checks groups of four bits – so it will run four times fewer iterations of its loop (in theory, at least^†) than the first does.

It works by 'masking' the number against the value 15, which, in hexadecimal is 0xF and in binary is 0b1111; thus, on each loop, the expression, i&15 (used as the array index) extracts the number represented by lowest four bits; the array, chs is a pre-defined list of how many bits are set in each of the possible values of that extracted number: the appropriate value is added to the running total, then the bits in the number are shifted down by 4 places (the i >>= 4 operation).

---

^† I say, "in theory," because many compilers will be able to optimize the code generated for either or both of your functions/loops, so predicting which will be the most efficient is not a trivial matter.

Further, the number of loops required before the test number is reduced to zero will be heavily dependent on the initial value of that number so, if your test numbers are biased towards low values, then the reduction of the loop count will become less significant.

Answer 2

The 2nd function will be more efficient. It counts the number of set bits in the last 4 bits at each step. And then trim the last 4 bit using i >>= 4