Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.