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
[...] > with 3 1s, 2 1s and 1 1s.
[...] > 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)
No, should be: for (count=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??

This method, and the variations posted by Ed Hook and
Keith Lewis, are O(2^n) methods, as mentioned by C.
Heckman. You enumerate all 2^n numbers (or most of
them, anyway, for Lewis's method) and test each one
you generate. Heckman's revised method generates,
by some unspecified method, the 0, 1, 2, 3, and 4-
member subsets of {0...13}, ie, 1471 subsets, which
correspond directly to your desired numbers. Erik
Naggum's apparently generates the same values by a
recursive Lisp program. Anyhow, the intent of both
is to cut the run time back to O(C(n,4)), ie, the
number of combinations of n things taken 4 at a time.

The following code snippet shows a simple way to
generate in turn 0-ones numbers, 1-ones numbers,
2-ones numbers, and so forth:

int main() {
int valu[ASIZE+1], tbit[ASIZE+1];
int jLo=0, jHi=1, i, j, k, n=1, w;
valu[0] = 0;
tbit[0] = -1;

for (i=1; i<5; ++i) { // This is the Add-A-Bit outer loop
for (j=jLo; j<jHi; ++j) { // Add a bit to previous-pass values
for (k=tbit[j]+1; k<WSIZE; ++k) {
valu[n] = valu[j] | (1<<k);
tbit[n] = k;
++n;
}
}
jLo = jHi;
jHi = n;
}
}

For small n, the program (at http://pat7.com/jp/4bits.c )
takes about the same amount of time as an enumerational
program, ie, under a millisecond.

For bigger n (up to 32 bits) 4bits.c is immmensely faster
than enumeration. For example, on my 1.2GHz AMD machine
a loop that counts to 2^32 takes about 7.5 seconds, but
4bits.c takes only 2 milliseconds to generate the
41449 desired values under 2^32.
-jiw
.

Loading