Assuming that the integer is 32 bits, this is pretty good: x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
Notice that the hex constants are respectively alternate bits, alternate pairs of bits, alternate groups of four bits, alternate bytes, and the low-order half of the int. The first statement determines the number of one-bits in each pair of bits. The second statement adds adjacent pairs of bits to get the number of bits in each group of four bits. Then these are added to get the number of bits in each byte, short int, and finally in the whole int. Dave On Jul 11, 12:44 pm, rShetty <[email protected]> wrote: > What is the most efficient algorithm to count the number of bits in an > unsigned integer ? > Explain your approach to the problem ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
