Is there a away of amount the on bits in of n binary length number in lognsteps?

Question

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?

score 0 · Answer 1 · answered Jul 22 '12 at 11:51

0

A lookup table will find this in constant time.

answered Jul 22 '12 at 11:51

Mike Kwan

23,549
10
59
94

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

Is there a away of amount the on bits in of n binary length number in lognsteps?

1 Answers1