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


Ujjaval wrote:
> 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.

Actually, it won't -- note that you never reset 'count' to 0 ...

>
> What do you think of this??

It's probably worth using the well-known algorithm for counting
the number of bits set in a word (and shortcircuiting the thing
when you _know_ that you're going to skip the current candidate).
Here's a C implementation:

#include <stdio.h>

int main(void)
{
int n_bits;
int limit = 16384;
unsigned long word;
unsigned long cword;

for ( word=1 ; word <= limit ; ++word ) {
n_bits = 0;
cword = word;
while ( cword ) {
cword &= (cword-1);
if ( ++n_bits > 4 )
break;
}
if ( n_bits <= 4 )
printf("%ld\n",word);
}

return 0;
}

.

Relevant Pages

  • [ncurses] cat xxx |more
    ... int main ... int ch, prev, row, col; ... Works something like a linux cat. ... But this program is limited by *term window size. ...
    (comp.unix.programmer)
  • Re: return the start of a substring in a string in c
    ... where calculating was more common than counting and ints were ... Counting is usually done with integers, ... That's not every cycle, of course, nor is every single integer a count of something - cryptography is an obvious exception, as are intermediate results in frequency transforms, or pixel colours. ... void setpixel(long *img, int width, int height, int x, int y, long val) ...
    (comp.lang.c)
  • RE: Formula counts incorrectly
    ... > I assume that it is only counting 5/5/2005 one time? ... > Could someone please modify this formula to work the way I want it to? ... > was's Profile: http://www.excelforum.com/member.php?action=getinfo&userid=20211 ... Prev by Date: ...
    (microsoft.public.excel.misc)
  • Re: 16x16Matrix
    ... assume int, but you can pick any other type (including the ones you ... then other replies in the thread might. ... Vladimir ... Prev by Date: ...
    (comp.lang.c)
  • Re: counting down or up is faster
    ... int main ... assuming everything as same except the for loops and if variable i 's ... usage has no problem with up or down counting which is faster? ... Pay particular attention to the sections titled "Bottlenecks", ...
    (comp.lang.c)