
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 1bits: 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.137164, June 1977. If you don't have that journal, see <http://www.ee.princeton.edu/~rblee/ELE572Papers/p137sedgewick.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/enus/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

