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.