I'm trying to find out if there's away for evaluating the number of on bits in a binary number of length n using O(1) space, in logn steps? If so- How?
Asked
Active
Viewed 38 times
1 Answers
0
A lookup table will find this in constant time.
Mike Kwan
- 24,123
- 12
- 63
- 96
-
He also wanted `O(1)` *space* (he called it "place" instead of "space") – Sergey Kalinichenko Jul 22 '12 at 11:52
-
Oh in that case, this question is really a duplicate of this one: http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer – Mike Kwan Jul 22 '12 at 11:53
-
I'm sorry. I edited the question. I'm basically want to know what's the algoritham for doing it in logn steps. – Joni Jul 22 '12 at 11:59
-
strictly speaking, lookup table is constant space – Lie Ryan Jul 22 '12 at 15:36