calculate permutations of a 32 bit word (Marching 1's)

Question

I am not mathematically proficient so please keep that in mind and am tackling a programming problem I'd like to solve optimally.

I have a register $32$ bits wide at any one time only $16$ bits(flags) can be set

I would like to calculate the number of possible permutations, but not sure where to start.

Ultimately I would like to store the $32$ bit register in as few bits as possible. There is less than $2^{32}$ permutations but more than $2^{16}$. It seems to be a factorial problem but I cannot work out how.

I tried to nut it out using much smaller register widths where half the registers can be set at any one time but other than manually writing out each one I still couldn't work it out.

If anyone could help I'd appreciate it.

Chris

Are precisely 16 bits set or are less than 16 bits possible too? — ccorn, Jul 30 '13 at 03:32
As asked fixed at 16. in actual fact it is somewhere between 12 and 16. Ross's answer covered that nicely as well — DeveloperChris, Jul 30 '13 at 12:07

Ross Millikan · Accepted Answer · 2013-07-30T04:07:20.400

2

From Alpha $\sum_{n=0}^{16} {32 \choose n} = 2448023843$, which needs $32$ bits to represent it. This is not surprising-it is over half the combinations (match up the ones with less than $16$ bits set with those with more than $16$ and you have all the ones with $16$. For exactly $16$ bits set there are $601080390$ possibilities.

edited Jul 30 '13 at 04:07

answered Jul 30 '13 at 03:37

Ross Millikan

374,822

thank you for your quick response. I guess in this case my intuition failed me. there is no savings to be had – DeveloperChris Jul 30 '13 at 12:06

calculate permutations of a 32 bit word (Marching 1's)

1 Answers1