Bit Manipulation Loop: Programming Problem

[NewUser2006]

I've got a programming problem that I need some suggestions about how to solve.

I need a routine that runs through all 13 bit numbers and does something "special" if the number has exactly 5 or 6 bits that are 1s, and goes on to the next number if it has any other amount of 1s in its bit pattern.

Can anyone think of a slick method to do this?

[WoolyHat]

Haven't tested this... but I think something like this would work.

<font class="small">Code:</font><hr /><pre>
unsigned int i;
unsigned int c;
unsigned int t;

for (i = 8191 ; i ; i-- )
{
t = i;

for (c = 0; t; c++)
{
t &amp;= t - 1;
}

if ( c == 5 || c = 6 )
// do something
}
</pre><hr />

Edit: I've randomly assumed C / C++

[NewUser2006]

Wooly,

Thanks! It works perfectly, but I'm not exactly sure HOW this loop works, could you please explain it a little?

<font class="small">Code:</font><hr /><pre>
for (c = 0; t; c++)
{ t &amp;= t - 1; }
</pre><hr />

[WoolyHat]

Easiest to explain with a scrap of paper, but I'll try here...

Imagine a binary number, subtract one from it. Look how the number changes. You basically unset the least significant bit and set all the bits lower than that. A few examples:

<font class="small">Code:</font><hr /><pre>
2 - 1 = 0010 - 0001 = 0001
4 - 1 = 0100 - 0001 = 0011
12 - 1 = 1100 - 0001 = 1011
</pre><hr />

So, if you subtract one from a number and logically AND it with itself then you are basically unsetting the least significant bit. Same examples again:

<font class="small">Code:</font><hr /><pre>
2 - 1 = 0010 - 0001 = 0001
=&gt; 0010 &amp; 0001 = 0000

4 - 1 = 0100 - 0001 = 0011
=&gt; 0100 &amp; 0011 = 0000

12 - 1 = 1100 - 0001 = 1011
=&gt; 1100 &amp; 1011 = 1000
</pre><hr />

So, each time that loop goes around it unsets the least significant bit. Eventually, the last bit will be unset and the number will equal zero... and since zero = false in C/C++ the loop terminates.

Hope that makes sense... :-S

[NewUser2006]

Yes this makes perfect sense, thanks a lot!

[Mogobu The Fool]

Just so you know, it would run faster if you did this with a lookup table.

Write a program that will go through all the numbers from 0 to 8191 (that's 1111111111111 in binary), and figure out if it has five or six 1's in it. Write the results into a table like this:

1: False,
2: False,
3: False,
(etc)
30: False,
31: True,
32: False,
(etc)

(31 is the first number with five 1's.)

Don't actually write the line numbers like that in your output; instead, just do his:
False,
False,
False,
(etc.)

When you're done, you'll have a list of all 8191 results, pre-computed. Copy the whole thing and drop it into a declared array in your program, like so:

private static readonly Bool HasFiveOrSix =
{
False,
False,
False,
{etc.}
False
}

Now you have an easy to use lookup table in your code.

If you want to see if myBitMask has five or six ones, you do this:

if (HasFiveOrSix(myBitMask))
{
}