Search All of the Math Forum:

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

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

 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

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://msdn.microsoft.com/en-us/library/aa289166(VS.71).aspx>.
combinations you only need a certain few.

--
jiw

Date Subject Author
12/14/14 Guest
7/1/09 Jose Carlos Santos
12/14/14 Calumnist
12/14/14 rossum
12/14/14 Bacle
12/14/14 Achava Nakhash, the Loving Snake
12/14/14 Bacle
12/14/14 Virgil
12/14/14 MeAmI.org
12/14/14 Bacle
7/2/09 Achava Nakhash, the Loving Snake
12/14/14 jbriggs444@gmail.com
12/14/14 Bacle
12/14/14 mensanator
12/14/14 Guest
12/14/14 mensanator
7/4/09 Guest
12/14/14 mensanator
7/4/09 abc
12/14/14 Guest
7/5/09 mensanator
12/14/14 mensanator
12/14/14 Dave Dodson