The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Find all Decimals where Binary number has N number of 1's
Replies: 26   Last Post: Dec 14, 2014 11:51 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Calumnist

Posts: 554
Registered: 12/11/04
Re: Find all Decimals where Binary number has N number of 1's
Posted: Jul 1, 2009 11:59 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Wed, 01 Jul 2009 09:20:42 -0400, Anonymous wrote:
> Does anyone know of a formula or algorithm where I can find all the
> decimal numbers that contain N number of 1's when looking at their
> binary form.
>
> For example: Say I want to find all the decimal numbers, that in binary
> form have 11 ones in them. See the example table below where the
> numbers would be 2047, 3071, 3583, etc, etc.
>
> Decimal -> Binary -> Number of 1's
> 2047 -> 11111111111 -> 11
> 3071 -> 101111111111 -> 11
> 3583 -> 110111111111 -> 11
> 3839 -> 111011111111 -> 11
> 3967 -> 111101111111 -> 11
> 4031 -> 111110111111 -> 11
> 4063 -> 111111011111 -> 11
> etc etc etc
>
> Does anyone know a way of putting this into a formula or algorithm?


You haven't stated what problem you are trying to solve. You should
clearly state a problem before asking if anyone knows how to solve it.

Here's a formula for the infinite set of numbers with 11 1-bits: S =
{ m : m = sum_{i= 1 to 11} 2^{a_i} with (for any j,k) a_j != a_k }.
That is, to generate a member of S, choose any 11 distinct integer
numbers a_1 ... a_11 and compute sum 2^{a_i}.

If instead you want the finite set T(n,k) of positive integers having n
bits and exactly k 1's, then use a combinatorial algorithm to generate all
combinations of n integers taken k at a time, and use the elements e_i of
each combination e as exponents of 2, giving n_e = sum_{i= 1 to k} 2^{e_i}.

A fast method of generating all such combinations is Algorithm 2 on page
143 of "Permutation Generation Methods" by Robert Sedgewick, ACM Computing
Surveys, v.9 n.2, p.137-164, June 1977. If you don't have that journal,
see <http://www.ee.princeton.edu/~rblee/ELE572Papers/p137-sedgewick.pdf>
where a scan of it appears. Some various implementations appear at
<http://forums.sun.com/thread.jspa?threadID=696760> and
<http://msdn.microsoft.com/en-us/library/aa289166(VS.71).aspx>.
Also see <http://en.wikipedia.org/wiki/Combinadic> if instead of all
combinations you only need a certain few.

--
jiw


Date Subject Author
12/14/14
Read Find all Decimals where Binary number has N number of 1's
Guest
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
umumenu@gmail.com
7/1/09
Read Re: Find all Decimals where Binary number has N number of 1's
Jose Carlos Santos
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Calumnist
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
rossum
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Bacle
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Achava Nakhash, the Loving Snake
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Bacle
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Virgil
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
MeAmI.org
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Bacle
7/2/09
Read Re: Find all Decimals where Binary number has N number of 1's
Achava Nakhash, the Loving Snake
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
jbriggs444@gmail.com
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Bacle
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
mensanator
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Guest
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
mensanator
7/4/09
Read Re: Find all Decimals where Binary number has N number of 1's
Guest
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
mensanator
7/4/09
Read Re: Find all Decimals where Binary number has N number of 1's
abc
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Guest
7/5/09
Read Re: Find all Decimals where Binary number has N number of 1's
mensanator
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
mensanator
12/14/14
Read Re: Find all Decimals where Binary number has N number of 1's
Dave Dodson
7/2/09
Read Re: Find all Decimals where Binary number has N number of 1's
umumenu@gmail.com
7/2/09
Read Re: Find all Decimals where Binary number has N number of 1's
MeAmI.org
7/2/09
Read Re: Find all Decimals where Binary number has N number of 1's
Jose Carlos Santos

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.