Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #1472

Re: n bits on of m bits

Cross-posted to 3 groups.

Show all headers | View raw

"Andrew Tomazos" <andrew@tomazos.com> wrote in message 
news:4344a25e-7fd5-43c5-b43a-a004c9f5f2ad@y7g2000vbe.googlegroups.com...
> I want to loop over every number from 0 to (2^m-1) inclusive whos
> binary representation contains exactly n bits.
>
> ie
>
> for (int i = 0; i < (1<<m); i++)
> {
>    int bits = 0;
>    for (int j = 0; j < m; j++)
>        if (i & (1 << j))
>            bits++;
>    if (bits == n)
>        do_something_with(i);
> }
>
> Clearly this is terribly inefficient.  I'm sure there is a much faster

If m is small enough, use pre-calculated tables that will give you the 
number of bits. You can also link together entries of the same size, to 
avoid looking at every single entry.

If m is too large for one table, then bit-count tables for each byte or each 
half-word might work. But now it's more difficult to group together all 
entries totalling n bits, and you need to look at all the numbers in range.

What are the typical ranges of m and n?

> way (perhaps by enumerating with mod/div somehow each continous
> sequence of 1s and continuous sequence of 0'x) but I can't seem to see
> it.

That doesn't correspond to what you said about the total number of (one) 
bits, where it doesn't matter if they are consecutive or not.

-- 
Bartc 

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

n bits on of m bits Andrew Tomazos <andrew@tomazos.com> - 2011-12-17 08:05 -0800
  Re: n bits on of m bits Robert Wessel <robertwessel2@yahoo.com> - 2011-12-17 10:44 -0600
  Re: n bits on of m bits Dave <dave_and_darla@Juno.com> - 2011-12-17 08:56 -0800
  Re: n bits on of m bits richard@cogsci.ed.ac.uk (Richard Tobin) - 2011-12-17 17:22 +0000
  Re: n bits on of m bits "BartC" <bc@freeuk.com> - 2011-12-17 18:23 +0000
    Re: n bits on of m bits Andrew Tomazos <andrew@tomazos.com> - 2011-12-17 11:05 -0800
  Re: n bits on of m bits Robert Wessel <robertwessel2@yahoo.com> - 2011-12-17 13:24 -0600
    Re: n bits on of m bits Robert Wessel <robertwessel2@yahoo.com> - 2011-12-17 13:47 -0600
  Re: n bits on of m bits blp@cs.stanford.edu (Ben Pfaff) - 2011-12-17 11:28 -0800
  Re: n bits on of m bits "The Last Danish Pastry" <clivet@gmail.com> - 2011-12-19 21:52 +0000
    Re: n bits on of m bits kym@kymhorsell.com - 2011-12-19 22:44 +0000
      Re: n bits on of m bits Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-19 15:33 -0800
        Re: n bits on of m bits kym@kymhorsell.com - 2011-12-20 03:51 +0000
        Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-20 10:05 +0000
          Re: n bits on of m bits Patricia Shanahan <pats@acm.org> - 2011-12-20 07:16 -0800
            Re: n bits on of m bits Dave <dave_and_darla@Juno.com> - 2011-12-20 07:29 -0800
              Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-20 16:00 +0000
      Re: n bits on of m bits The Last Danish Pastry <clivet@gmail.com> - 2011-12-19 16:41 -0800
        Re: n bits on of m bits kym@kymhorsell.com - 2011-12-20 04:29 +0000
  Re: n bits on of m bits kym@kymhorsell.com - 2011-12-20 19:04 +0000
  Re: n bits on of m bits Robin Vowels <robin.vowels@gmail.com> - 2011-12-22 07:25 -0800
    Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-22 15:58 +0000
      Re: n bits on of m bits Robin Vowels <robin.vowels@gmail.com> - 2011-12-22 16:26 -0800
        Re: n bits on of m bits Willem <willem@toad.stack.nl> - 2011-12-23 18:58 +0000
          Re: n bits on of m bits Robin Vowels <robin.vowels@gmail.com> - 2011-12-25 04:01 -0800
            Re: n bits on of m bits Dave <dave_and_darla@Juno.com> - 2011-12-25 09:22 -0800
  Re: n bits on of m bits Dr J R Stockton <reply1151@merlyn.demon.co.uk> - 2011-12-24 23:36 +0000
  Re: n bits on of m bits "io_x" <a@b.c.invalid> - 2011-12-31 16:32 +0100

csiph-web