[Buffalo-pm] Re: [tpm] Bit Counting

[Mike Stok]

On Wed, 1 Oct 2003, Quantum Mechanic wrote:

> I'm looking for an elegant way to generate a list of
> numbers whose binary representation has a given number
> of 1's. I also want to generate this list in numerical
> order.
> 
> For example, with 4 bits on, less than 50:
> 
> 15 1111
> 23 10111
> 27 11011
> 29 11101
> 30 11110
> 39 100111
> 43 101011
> 45 101101
> 46 101110
> 
> Now it's easy enough to check every number up to the
> limit, but it seems there should be a more efficient
> method. On the other hand, the overhead involved in
> "skipping" some numbers may be more expensive than the
> straightforward approach. 
> 
> Anyone have any insights into this?

If you know the number of bits in your upper limit and you know how many 
of them have to be 1 then you can just generate the right bit strings 
quite easily (and then filter those bigger than your limit)

50 has 6 bits, and you want 4 of them on, so you're generating all the 
strings with 2 0s and 4 1s.  Then you need to check that they are all <= 
your limit...

Hope this helps,

Mike

-- 
mike at stok.co.uk                    |           The "`Stok' disclaimers" apply.
http://www.stok.co.uk/~mike/       | GPG PGP Key      1024D/059913DA 
mike at exegenix.com                  | Fingerprint      0570 71CD 6790 7C28 3D60
http://www.exegenix.com/           |                  75D2 9EC4 C1C0 0599 13DA