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

Groups > comp.programming > #1098 > unrolled thread

n bits on of m bits

Back to article view | Back to comp.programming

Contents

  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

Page 1 of 2  [1] 2  Next page →

#1098 — n bits on of m bits

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
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.

Can anyone see it?  Or post a link?  I'm sure this is a fairly common
one.

Thanks,
Andrew.

[toc] | [next] | [standalone]

#1099

On Sat, 17 Dec 2011 08:05:20 -0800 (PST), Andrew Tomazos
<andrew@tomazos.com> wrote:

>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
>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.



A recursive approach comes to mind.  Approximately:


#include <stdio.h>

void n_of_m_bits_r(int nbr, int b, int m, int n)
// nbr = candidate number
// b = current number of one bits in nbr
// m = number of additional bits to add to nbr
// n = desired number of one bits
{
    if (m==0)
        { // Gotten to the end 
        if (b == n)
            printf("%i\n", nbr);  // Finished with correct # of bits
        return;
        }

    if ((n-b)>m)
        return;  // no longer enough bits left to get to n

    // Add zero bit case (IOW nbr was "abcd", process "abcd0"):
    n_of_m_bits_r((nbr<<1), b, (m-1), n);

    // Add one bit case (IOW nbr was "abcd", process "abcd1"):
    if ((b+1) <= n)
        n_of_m_bits_r(((nbr<<1)+1), (b+1), (m-1), n);
}

void n_of_m_bits(int m, int n)
{
      n_of_m_bits_r(0, 0, m, n);
}

int main()
{
    n_of_m_bits(7, 2);  // list all seven bit numbers w/two bits set
    return 0;    
}

(minimally tested, etc.)

This lengthens the number by a single bit each recursion, but short
circuits the process when the accumulated number of bits becomes too
high, or the number of remaining bits becomes too low to reach the
required total.

[toc] | [prev] | [next] | [standalone]

#1100

On Dec 17, 10:05 am, Andrew Tomazos <and...@tomazos.com> wrote:
> I want to loop over every number from 0 to (2^m-1) inclusive whos
> binary representation contains exactly n bits.

Try something like this:

    i = (1 << n) -1;
    while( !(i >> m) )
    {
        do_something_with(i);
        i = (i+(i&(-i)))|(((i^(i+(i&(-i))))>>2)/(i&(-i)));
    }

The first "i =" statement sets i to the smallest number with n 1-
bits.

The second "i =" statement is some bit manipulation "magic" that sets
i to the next sequential number that has the same number of 1-bits.
For an explanation, see http://groups.google.com/group/programming-puzzles/msg/3a05b3c8b4042d5b,
which points to a PowerPoint presentation that gives a multi-statement
expression of the one-liner that I constructed from it.

The "while" statement loops as long as i remains less than 2^m.

Dave

[toc] | [prev] | [next] | [standalone]

#1101

In article <4344a25e-7fd5-43c5-b43a-a004c9f5f2ad@y7g2000vbe.googlegroups.com>,
Andrew Tomazos  <andrew@tomazos.com> wrote:

>I want to loop over every number from 0 to (2^m-1) inclusive whos
>binary representation contains exactly n bits.

If n is substantially less than m, any algorithm that loops through
all 2^m numbers will be unecessarily slow.

-- Richard

[toc] | [prev] | [next] | [standalone]

#1103

"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 

[toc] | [prev] | [next] | [standalone]

#1104

On Dec 17, 7:23 pm, "BartC" <b...@freeuk.com> wrote:
> "Andrew Tomazos" <and...@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.

No, I mean if you reverse the bit order and partition a binary number
into alternating sequences of 1s and 0s...

    111010110001

   "111", "0" , "1" ,"0", "11", "000", "1"

and then count each partitions size

   (3, 1, 1, 1, 2, 3, 1)

then I thought there was a way to more easily enumerate them.

ie in psuedo-code with strings recursively...

function recurse(char c, string selected, int numcsleft, int
numotherleft)
{
    if (numcsleft == 0 and numotherleft == 0)
       do_something_with(selected);

    for (int i = 1; i <= numcsleft; i++)
    {
       string nextselected = selected + repeat(i, c); // append
sequence of c chars of i length;
       char nextc = (c == '0' ? '1' : '0'); // alternate to other char

       recurse(nextc, nextselected, numotherleft, numcsleft - i);
   }
}

function loopall(int m, int n)
{
    recurse("0", m-n, n);
    recurse("1", n, m-n);
}

but it was just an idea.
     -Andrew.

[toc] | [prev] | [next] | [standalone]

#1105

On Sat, 17 Dec 2011 08:05:20 -0800 (PST), Andrew Tomazos
<andrew@tomazos.com> wrote:

>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
>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.


An even better idea - just generate all the combinations of C(m|n).
Hard coded for n=3:

for (i=0; i<(m-2); i++)
    for (j=(i+1); j<(m-1); j++)
        for (k=(j+1); k<m; k++)
            nbr = (1<<i) + (1<<j) + (1<<k);
            // output nbr

Use the usual recursive loop plus array to deal with a variable number
of nested loops/n.

That's particularly interesting, since it runs in time strictly
proportional to the actual number of outputs, which should approach
optimal.

[toc] | [prev] | [next] | [standalone]

#1107

On Sat, 17 Dec 2011 13:24:53 -0600, Robert Wessel
<robertwessel2@yahoo.com> wrote:

>On Sat, 17 Dec 2011 08:05:20 -0800 (PST), Andrew Tomazos
><andrew@tomazos.com> wrote:
>
>>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
>>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.
>
>
>An even better idea - just generate all the combinations of C(m|n).
>Hard coded for n=3:
>
>for (i=0; i<(m-2); i++)
>    for (j=(i+1); j<(m-1); j++)
>        for (k=(j+1); k<m; k++)
>            nbr = (1<<i) + (1<<j) + (1<<k);
>            // output nbr
>
>Use the usual recursive loop plus array to deal with a variable number
>of nested loops/n.
>
>That's particularly interesting, since it runs in time strictly
>proportional to the actual number of outputs, which should approach
>optimal.


And for this you don't even need the array:

#include <stdio.h>

void n_of_m_bits_r(int nbr, int p, int m, int n)
// nbr = partial number
// p = prior loop start
// m = length of number
// n = number of additional of one bits needed
{
    int i, t;
 
    for (i=(p+1); i<(m-n); i++)
        {
        t = nbr + (1<<i);
        if (n == 0)
            printf("%i\n", t);
        else
            n_of_m_bits_r(t, i, m, (n-1));
        }
}

void n_of_m_bits(int m, int n)
{
      n_of_m_bits_r(0, -1, m, (n-1));
}

int main()
{
    n_of_m_bits(7, 2);  // list all seven bit numbers w/two bits set
    return 0;    
}


Unfortunately doesn't generate the numbers in order, though.

[toc] | [prev] | [next] | [standalone]

#1106

Andrew Tomazos <andrew@tomazos.com> writes:

> I want to loop over every number from 0 to (2^m-1) inclusive whos
> binary representation contains exactly n bits.

This is a permutation problem so you will find a general solution
(probably more than one, in fact) in Knuth vol. 4A.
-- 
I love deadlines.
I love the whooshing noise they make as they go by.
--Douglas Adams

[toc] | [prev] | [next] | [standalone]

#1119

"Andrew Tomazos" <andrew@tomazos.com> wrote...

>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
> 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.
>
> Can anyone see it?  Or post a link?  I'm sure this is a fairly common
> one.

Here is the C# code that I use to count the number of 1 bits in a 
non-negative long:

  public static int CountBinaryOnes(long x)
  {
    int result = 0;

    while (x > 0)
    {
      ++result;
      x &= x-1;
    }
    return result;
  } // CountBinaryOnes

-- 
Clive Tooth 

[toc] | [prev] | [next] | [standalone]

#1120

In sci.math The Last Danish Pastry <clivet@gmail.com> wrote:
...
>  public static int CountBinaryOnes(long x)
>  {
>    int result = 0;
> 
>    while (x > 0)
>    {
>      ++result;
>      x &= x-1;

The traditional method on 2s compl machinery is
	x &= -x;

[toc] | [prev] | [next] | [standalone]

#1121

On 12/19/11 2:44 PM, kym@kymhorsell.com wrote:
> In sci.math The Last Danish Pastry<clivet@gmail.com>  wrote:
> ....
>>   public static int CountBinaryOnes(long x)
>>   {
>>     int result = 0;
>>
>>     while (x>  0)
>>     {
>>       ++result;
>>       x&= x-1;
>
> The traditional method on 2s compl machinery is
> 	x&= -x;
>

I've seen cleverer ways that are O(logn) best/worse case.

[toc] | [prev] | [next] | [standalone]

#1123

In sci.math Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
> On 12/19/11 2:44 PM, kym@kymhorsell.com wrote:
>> In sci.math The Last Danish Pastry<clivet@gmail.com>  wrote:
>> ....
>>>   public static int CountBinaryOnes(long x)
>>>   {
>>>     int result = 0;
>>>
>>>     while (x>  0)
>>>     {
>>>       ++result;
>>>       x&= x-1;
>>
>> The traditional method on 2s compl machinery is
>>       x&= -x;
> I've seen cleverer ways that are O(logn) best/worse case.

Yes, these bit shifting/masking methods became popular when big shifters
became cheap and looping caused bubbles in the pipeline.

E.g.
	y = (x&0x55555555)+((x>>1)&0x55555555)

will convert  a vector of bit quantities "x[i]" to a vector of 2-bit 
quanitites "y[j]" where y[j] = x[2*j]+x[2*j+1]

Then
	z = (y&0x33333333)+((y>>2)&0x33333333)

willconvert a vector of 2-bit quantities y[i] into  a vector of 4-bit
quantities z[j] such that z[j] = y[2*j]+y[2*j+1]

Etc, until all the bits in the wordsize have been added. Or maybe cheat with
some MMX instructions. :)

Which of the shift/mask or "count number of 1's using 2s compl" is actually
the fastest for a given architecture usually devolves to measurement
after appropriately weighting the expected arguments.

[toc] | [prev] | [next] | [standalone]

#1127

Daniel Pitts wrote:
) On 12/19/11 2:44 PM, kym@kymhorsell.com wrote:
)> In sci.math The Last Danish Pastry<clivet@gmail.com>  wrote:
)> ....
)>>   public static int CountBinaryOnes(long x)
)>>   {
)>>     int result = 0;
)>>
)>>     while (x>  0)
)>>     {
)>>       ++result;
)>>       x&= x-1;
)>
)> The traditional method on 2s compl machinery is
)> 	x&= -x;
)>
)
) I've seen cleverer ways that are O(logn) best/worse case.

None of which is relevant to the OP because he wants to enumerate all
n-bit numbers that have exactly m bits set, and that can be done in
O(Choose(m,n)) time, instead of the O(2^n*logn) that this would do.

Hell, even if you just enumerated over all 2^n numbers you could still
keep/update a parallel count in O(1) time per step.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#1128

On 12/20/2011 2:05 AM, Willem wrote:
> Daniel Pitts wrote:
> ) On 12/19/11 2:44 PM, kym@kymhorsell.com wrote:
> )>  In sci.math The Last Danish Pastry<clivet@gmail.com>   wrote:
> )>  ....
> )>>    public static int CountBinaryOnes(long x)
> )>>    {
> )>>      int result = 0;
> )>>
> )>>      while (x>   0)
> )>>      {
> )>>        ++result;
> )>>        x&= x-1;
> )>
> )>  The traditional method on 2s compl machinery is
> )>  	x&= -x;
> )>
> )
> ) I've seen cleverer ways that are O(logn) best/worse case.
>
> None of which is relevant to the OP because he wants to enumerate all
> n-bit numbers that have exactly m bits set, and that can be done in
> O(Choose(m,n)) time, instead of the O(2^n*logn) that this would do.

I agree that the original problem is best regarded as enumerating all
the ways of choosing m bit numbers from n bit numbers.

If the input is narrow enough to fit in an hardware data type that has
fast addition, bit operations, and shifts, counting the one bits only
takes log(w) steps, where w is the width in bits, not the value of the
input number.

Patricia

[toc] | [prev] | [next] | [standalone]

#1129

On Dec 20, 9:16 am, Patricia Shanahan <p...@acm.org> wrote:
> If the input is narrow enough to fit in an hardware data type that has
> fast addition, bit operations, and shifts, counting the one bits only
> takes log(w) steps, where w is the width in bits, not the value of the
> input number.

The code I posted in http://groups.google.com/group/sci.math/msg/cb1e398f74688e66
steps from one number with n bits set directly to the next one, so the
loop count is mCn.

Dave

[toc] | [prev] | [next] | [standalone]

#1130

Dave wrote:
) On Dec 20, 9:16?am, Patricia Shanahan <p...@acm.org> wrote:
)> If the input is narrow enough to fit in an hardware data type that has
)> fast addition, bit operations, and shifts, counting the one bits only
)> takes log(w) steps, where w is the width in bits, not the value of the
)> input number.
)
) The code I posted in http://groups.google.com/group/sci.math/msg/cb1e398f74688e66
) steps from one number with n bits set directly to the next one, so the
) loop count is mCn.

Making the same assumption about hardware data types as above, of course.

But that goes for the complexity of just about all algorithms out there, really.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#1122

On Dec 19, 10:44 pm, k...@kymhorsell.com wrote:

> In sci.math The Last Danish Pastry <cli...@gmail.com> wrote:
> ...
>
> >  public static int CountBinaryOnes(long x)
> >  {
> >    int result = 0;
>
> >    while (x > 0)
> >    {
> >      ++result;
> >      x &= x-1;
>
> The traditional method on 2s compl machinery is
>         x &= -x;

That is not correct. It simply replaces x by its rightmost bit.

--
Clive Tooth

[toc] | [prev] | [next] | [standalone]

#1125

In sci.math The Last Danish Pastry <clivet@gmail.com> wrote:
> On Dec 19, 10:44?pm, k...@kymhorsell.com wrote:
...
>> > ? ? ?x &= x-1;
>>
>> The traditional method on 2s compl machinery is
>> ? ? ? ? x &= -x;
> 
> That is not correct. It simply replaces x by its rightmost bit.
...

I think I have mis-remembered the magic -- it essentially resets the
lsb just at your code does.

[toc] | [prev] | [next] | [standalone]

#1131

In sci.math Andrew Tomazos <andrew@tomazos.com> wrote:
> I want to loop over every number from 0 to (2^m-1) inclusive whos
> binary representation contains exactly n bits.
...

The somewhat brute force method is to think of the "encoding" of
the necessary permutation.

I.e. from a "code" [0,mCn) you wish to extract n numbers [0,m) that
indicate which bits to set.

The trick is to maintain a table of "available bit numbers" and use
the div/rem method you suspect to select one of the available numbers
and then remove it from the table.

There are other methods used to generate permutations that only need exchanges
of table elements, but these don't seem to guarantee each perumtation is 
generated once.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming

csiph-web