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

"Ujjaval" <ujjaval@xxxxxxxxx> writes in article <1138072953.428412.252450@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> dated 23 Jan 2006 19:22:33 -0800:
>Yes I need the numbers with at the most 4 1s or less than that. so i
>also need numbers with 3 1s, 2 1s and 1 1s.
>
>
>i didn't really get what Erik Naggum suggested. But I worked out the
>following way:
>
>
>n = 2^14
>count = 0
>
>for ( i=0;i< n;i++)
>{
> for (j=0;j<n;j=j*2)
> {
> if (i AND j) = j
> count = count + 1
> }
> if (count <=4)
> print i
>}
>
>This will print all the numbers having at most 4 1s in its equivalent
>binary number.
>
>What do you think of this??

There's room for improvement. Many times the numbers with more than 4 1's
come in groups. For example, 1921-2047.

for ( i=0; i<n; i+=increment)
{
for (j=n;j>0;j=j/2) /* scan bits in reverse order */
{
if (i AND j) = j
{
count = count + 1
least_bit = j /* remember least bit which is set */
}
}
if (count <=4)
print i

if (count >= 4) /* == should even be good enough */
increment = least_bit /* we won't hit another until this bit flips */
else
increment = 1
}

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
.