What kind of mathematical order is this?

[matthew180]

What kind of mathematical "order" is this?

Disclaimer: Sorry if this question is off-topic, I really don't yet know where it "belongs".

I wrote a program that counts the number of "1" bits in a 16-bit value. My program is brute force right now (loop 0 to 65535, shift each number and count the bits), but I would like to understand the results and how this problem could be solved mathematically, i.e. with a formula vs brute force. Since any integer in the range 0 to 65535 will go into 1 of 17 "buckets", how can I make the determination without shifting and counting the bits?

Initially I thought the results were logarithmic, but the values rise and decline, so now I'm thinking they are more related to sine or cosine. Here are the results, can anyone explain to me the relationship I am looking at here?

Thanks,
Matthew

1 numbers had 0 1's
16 numbers had 1 1's
120 numbers had 2 1's
560 numbers had 3 1's
1820 numbers had 4 1's
4368 numbers had 5 1's
8008 numbers had 6 1's
11440 numbers had 7 1's
12870 numbers had 8 1's
11440 numbers had 9 1's
8008 numbers had 10 1's
4368 numbers had 11 1's
1820 numbers had 12 1's
560 numbers had 13 1's
120 numbers had 14 1's
16 numbers had 15 1's
1 numbers had 16 1's

 

[jedishrfu]

You have rediscovered hamming weights

http://en.wikipedia.org/wiki/Hamming_weight

 

[Hurkyl]

The k-th entry (0-up counting) in your table counts the number of ways you can select k bits out of 16 to be a 1 (and the rest 0), right?

 

[matthew180]

@jedishrfu: Thanks! Population count, I should have realized that.

@Hurkyl: Yes, that seems to be another way to describe the idea.

 

[blue_raver22]

The mathematical "order" in this case could be described as a binomial distribution. This type of distribution is commonly used to model the number of successes in a series of independent trials, which is similar to your problem of counting the number of 1's in a 16-bit value. The shape of the distribution follows a bell curve, with the peak at the middle and the values declining on either side. This explains the pattern you are seeing in your results, where the number of 1's increases and then decreases as the number of 1's in each value increases.

To solve this problem mathematically, you could use the binomial distribution formula to calculate the probability of getting a certain number of 1's in a 16-bit value. This would involve using the binomial coefficient (n choose k) and the probability of getting a 1 (which is 1/2 for a binary value). This would give you a formula to determine the number of values with a certain number of 1's, rather than having to brute force count them.

Alternatively, you could also use other mathematical methods such as generating functions or recurrence relations to find a formula for the number of values with a certain number of 1's. These methods may be more complex but can also provide a more general formula that can be applied to larger values.

Overall, understanding the underlying mathematical order can help you solve this problem more efficiently and accurately without having to rely on brute force methods.