Friday, July 8, 2011

numbers of 1 in an integer n

Can you compute the number of 1 bits in a number N in O(N)? how about O(log N) and what about O(1)?


  1. I wonder if hand-crafted assembly procedure with loop operating on two registers wouldn't be faster than any O(1) solutions based on precomputed table kept in RAM...

  2. Probably this will be considered a bad trick, but anyway the popcnt machine instruction introduced in the SSE4 extension does the trick (obviously in constant time)