Re: algorithm to identify number from 0-16384 having at most 4 1s in its binary number


Ujjaval wrote:
> Hey all,
>
> I want to get the numbers from 0-16384 whose equivalent binary number
> has at the most 4 1s in it.
>
> I can do this by setting up a counter and doing an AND operation of a
> number with all numbers which are power of 2 between 0-16384. I update
> the couter for each successful AND operation and at the end check
> whether the counter is <= 4 or not.
>
> Is there any more efficient way to do this??

Why bother?

Suppose we have string with k bits.. We desire all such with 0,1,2,3,
or 4 bits
lit.

There are choose(k, 0) choices with no bits lit
choose(k,1) with 1 bit lit
choose(k,2) with 2

etc.

I put (k,j) for k choose j.
The answer is (k,0) + (k,1) + (k,2) + (k,3) + (k,4). This is a 4th
degree polynomial
in k.

.

Relevant Pages