# What kind of mathematical order is this?

1. Jul 7, 2012

### 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

2. Jul 7, 2012

3. Jul 7, 2012

### Hurkyl

Staff Emeritus
Re: What kind of mathematical "order" is this?

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?

4. Jul 7, 2012

### matthew180

Re: What kind of mathematical "order" is this?

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

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