#1
|
|||
|
|||
Bit Manipulation Loop: Programming Problem
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? |
#2
|
|||
|
|||
Re: Bit Manipulation Loop: Programming Problem
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 &= t - 1; } if ( c == 5 || c = 6 ) // do something } </pre><hr /> Edit: I've randomly assumed C / C++ |
#3
|
|||
|
|||
Re: Bit Manipulation Loop: Programming Problem
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 &= t - 1; } </pre><hr /> |
#4
|
|||
|
|||
Re: Bit Manipulation Loop: Programming Problem
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 => 0010 & 0001 = 0000 4 - 1 = 0100 - 0001 = 0011 => 0100 & 0011 = 0000 12 - 1 = 1100 - 0001 = 1011 => 1100 & 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 |
#5
|
|||
|
|||
Re: Bit Manipulation Loop: Programming Problem
Yes this makes perfect sense, thanks a lot!
|
#6
|
|||
|
|||
Re: Bit Manipulation Loop: Programming Problem
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)) { } |
|
|