n bits on of m bits

[Andrew Tomazos]

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.

[Robert Wessel]

On Sat, 17 Dec 2011 08:05:20 -0800 (PST), 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.
>
>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.

[Dave]

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

[Richard Tobin]

In article <4344a25e-7fd5-43c5...@y7g2000vbe.googlegroups.com>,

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.

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

-- Richard

[BartC]

"Andrew Tomazos" <and...@tomazos.com> wrote in message
news:4344a25e-7fd5-43c5...@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

[Andrew Tomazos]

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.

[Robert Wessel]

On Sat, 17 Dec 2011 08:05:20 -0800 (PST), 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.
>
>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.

[Ben Pfaff]

Andrew Tomazos <and...@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

[Robert Wessel]

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.

[The Last Danish Pastry]

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

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

[k...@kymhorsell.com]

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;

[Daniel Pitts]

On 12/19/11 2: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;
>

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

[The Last Danish Pastry]

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

--
Clive Tooth

[k...@kymhorsell.com]

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.

[k...@kymhorsell.com]

In sci.math The Last Danish Pastry <cli...@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.

...

Yes, it should have been
const int y = (-x)&x;
x ^= y;

that may be inferior to working from the other end.

[k...@kymhorsell.com]

In sci.math The Last Danish Pastry <cli...@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.

[Willem]

Daniel Pitts wrote:
) On 12/19/11 2: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;
)>
)
) 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

[Patricia Shanahan]

On 12/20/2011 2:05 AM, Willem wrote:
> Daniel Pitts wrote:
> ) On 12/19/11 2: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;
> )>
> )
> ) 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

[Dave]

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

[Willem]

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.

[k...@kymhorsell.com]

In sci.math 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.

...

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.

[Robin Vowels]

On Dec 18, 3: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.
>
> 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.

It is unclear what you want.
By "n bits" do you mean n binary digits? (i.e., expressible in
n binary digits (not counting leading zeros).
Or do you mean n one-bits (as someone has assumed)?

If you mean n binary digits, then the range of values
that you need to look at is from 2**(n-1) to 2**n-1.
Thus, if n = 8, you'd be looking at values from
128 to 255.

[Willem]

Robin Vowels wrote:
) On Dec 18, 3: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.
)>
)> 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.
)
) It is unclear what you want.

Read the code then. It does what the OP wants, it's just very slow.

) Or do you mean n one-bits (as someone has assumed)?

Not assumed, inferred. And not someone, everyone (except you).

HTH, HAND.

[Robin Vowels]

The code and the description of the what it dod contradict
one another.

Anyway, even if the OP wants to count one-bits,
he doen't need to start at 0, because a number that has fewer than
n bits (without leading zeros) cannot possibly have n one-bits.
Thus, he needs only consider values from 2**n-1 through 2**m-1.

[Willem]

Robin Vowels wrote:
) On Dec 23, 2:58?am, Willem <wil...@toad.stack.nl> wrote:

)> Robin Vowels wrote:
)> ) It is unclear what you want.

)>
)> Read the code then. ?It does what the OP wants, it's just very slow.
)
) The code and the description of the what it dod contradict
) one another.

No, the code and *your interpretation* contradict one another.

) Anyway, even if the OP wants to count one-bits,
) he doen't need to start at 0, because a number that has fewer than
) n bits (without leading zeros) cannot possibly have n one-bits.
) Thus, he needs only consider values from 2**n-1 through 2**m-1.

What kind of speedup would you expect from this if, say,
n is 24 and m is 32 ?

[Dr J R Stockton]

In sci.math message <4344a25e-7fd5-43c5...@y7g2000vbe.goo
glegroups.com>, Sat, 17 Dec 2011 08:05:20, Andrew Tomazos
<and...@tomazos.com> posted:

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

Does it matter whether you get the numbers in numerical order?

In either case, you just need to consider all possible orders of n ones
and (m-n) zeroes. Set a "ones" count to n and a "zeroes" count to
(m-n).

The first digit can be picked in two ways, so use a J = 0 to 1 loop for
that; choose 0 or 1, and decrement the corresponding counter. Now
recurse for the next digit. At each step, however, check the counters
first; don't choose a value whose count is zero. In this simple case,
that can be done by setting the loop start and end values accordingly;
but it will may more efficient to test the reserves of digits first,
since if either is empty all remaining choices must be from the other.

It now should be fairly obvious that you do not need the loop. to be
explicit. At each step, if there are no zeroes left use all of the
ones, and vice versa. Otherwise, include both choices of digit.

--
(c) John Stockton, nr London UK ?@merlyn.demon.co.uk IE8 FF8 Op11 Sf5 Cr15
news:comp.lang.javascript FAQ <http://www.jibbering.com/faq/index.html>.
<http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

[Robin Vowels]

On Dec 24, 5:58 am, Willem <wil...@toad.stack.nl> wrote:
> Robin Vowels wrote:
>
> ) On Dec 23, 2:58?am, Willem <wil...@toad.stack.nl> wrote:)> Robin Vowels wrote:
>
> )> ) It is unclear what you want.
> )>
> )> Read the code then. ?It does what the OP wants, it's just very slow.
> )
> ) The code and the description of the what it dod contradict
> ) one another.
>
> No, the code and *your interpretation* contradict one another.

Have it your own way, but the OP's description of what
the code did, and the code itself, contradict each other.

[Dave]

Please explain how the OP's code and description contradict each
other. I'm having a mental block.

Dave

[io_x]

"Andrew Tomazos" <and...@tomazos.com> ha scritto nel messaggio
news:4344a25e-7fd5-43c5...@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;

the rilevant part is below for loop
fun(i, m)
in: i the number to calc bits
in: m the number to of bits allowed

> for (int j = 0; j < m; j++)

> if (i & (1 << j))

> bits++;

-----------------------------------

u32 fun(u32 i, u32 m)
{u32 mask;
if(m>=32) ;
else {mask=1; mask<<=m; --mask; i&=mask;}
return CountBit32(i);
}

where BountBit32() is done using tables or some other trick
other have said

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