Several. You can compute all possible ways to arrange four 1s in a
field of 14 bits.
for (i = 1; i < (1 << (14 - 3)); i <<= 1)
for (j = i << 1; j < (1 << (14 - 2)); j <<= 1)
for (k = j << 1; k < (1 << (14 - 1)); k <<= 1)
for (m = k << 1; m < (1 << (14 - 0)); m <<= 1)
printf("%d ", i | j | k | m);
Then repeat this idea for 3, 2, and finally a single 1. Finally tack
on 0 and 16384.
The inner loop bodies execute only 1470 times rather than 16385.
If you still want to seive all numbers in 0..16384, then there are many
ways to compute the number of 1's in a binary number. See
http://www.cap-lore.com/code/Hamming.txt . My favorite is the idea of
using the bits of the ALU as a parallel processor.
(x and 5555 hex) + ((x and AAAA hex) shift_right 1)
does 8 parallel 1-bit add operations producing 2-bit results. Repeat
to get 4 parallel 2-bit adds, 2 parallel 4-bit adds, and a final
addition to get the number of 1s. In general to count 1s in an N-bit
number you need log-N of these mask-shift-and-add operations.
But in your case it's likely to be quicker to exploit the fact that
x and (x - 1)
is x with the least significant 1 removed.
So in C you would have something like
for (i = 0; i <= 16384; i++) {
int x = i;
x &= x - 1;
x &= x - 1;
x &= x - 1;
x &= x - 1;
if (x == 0) printf("%d ", i);
}
