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)?

2 comments:

  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...

    ReplyDelete
  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)

    http://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT

    ReplyDelete