What is the most efficient way to count the number of bits which are set in an integer?
Many “bit-fiddling” problems like this one can be sped up and streamlined using lookup tables (but see question 20.13). Here is a little function which computes the number of bits in a value, 4 bits at a time: static int bitcounts[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; int bitcount(unsigned int u) { int n = 0; for(; u != 0; u >>= 4) n += bitcounts[u & 0x0f]; return n; } comp.lang.c FAQ list ยท Question 20.13 Q: What’s the best way of making my program efficient? A: By picking good algorithms, implementing them carefully, and making sure that your program isn’t doing any extra work. For example, the most microoptimized character-copying loop in the world will be beat by code which avoids having to copy characters at all. When worrying about efficiency, it’s important to keep several things in perspective. First of all, although efficiency is an enormously popular topic, it is not always as important as people tend to think it is. Most of the code in most programs is not
