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

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 3: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

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.