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 2 of 2 — ← Prev page 1 [2]

#1134

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.

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

#1135

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.


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]

#1140

On Dec 23, 2:58 am, Willem <wil...@toad.stack.nl> wrote:
> 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.

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.

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

#1141

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 ?


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]

#1146

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.

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

#1147

On Dec 25, 6:01 am, Robin Vowels <robin.vow...@gmail.com> wrote:
> 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.

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

Dave

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

#1144

In sci.math message <4344a25e-7fd5-43c5-b43a-a004c9f5f2ad@y7g2000vbe.goo
glegroups.com>, Sat, 17 Dec 2011 08:05:20, Andrew Tomazos
<andrew@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.

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

#1167

"Andrew Tomazos" <andrew@tomazos.com> ha scritto nel messaggio
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;

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.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.programming

csiph-web