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

[Mike Stok]

On 1 Oct 2003, Derek Wueppelmann wrote:

> On Wed, 2003-10-01 at 14:40, Mike Stok wrote:
> > 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?
> 
> Sorry I didn't post directly to your post but here's a thought.

? :-)

If you want perl then this does the same as he ruby but is smarter about 
generating all 0s or 1s:


[mike at ratdog tmp]$ cat try.pl
#!/usr/bin/env perl 

use POSIX 'ceil';

sub make_strings (&$$);

sub make_strings (&$$) {
    my ( $block, $ones, $length ) = @_;

    return if $ones > $length or $length < 1;

    if ( $ones == 0 ) {
        $block->( '0' x $length );
    }
    elsif ( $ones == $length ) {
        $block->( '1' x $length );
    }
    else {
        make_strings { $block->( "0$_[0]" ) } $ones, $length - 1;
        make_strings { $block->( "1$_[0]" ) } $ones - 1, $length - 1 
          if $ones > 0;
    }
}

( $ones, $limit ) = @ARGV;
$bits = ceil( log( $limit + 1 ) / log(2) );

ITERATION: {
    make_strings {
        my $s     = shift;
        my $value = oct("0b$s");
        last ITERATION if $value > $limit;
        print "$s $value\n";
    } $ones, $bits;
}
[mike at ratdog tmp]$ ./try.pl 4 50
001111 15
010111 23
011011 27
011101 29
011110 30
100111 39
101011 43
101101 45
101110 46

(shame I can't put the & in the prototype at the end and be able to keep 
dropping the sub keyword...)

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