425,719 Members | 1,046 Online
Need help? Post your question and get tips & solutions from a community of 425,719 IT Pros & Developers. It's quick & easy.

# Count number of bits set in a number

 P: n/a Hi all, I want to write a program to count number of bits set in a number. The condition is we should not loop through each bit to find whether its set or not. Thanks in advance, -Mukesh Sep 27 '07 #1
11 Replies

 P: n/a "Mack"

 P: n/a Mack wrote: Hi all, I want to write a program to count number of bits set in a number. The condition is we should not loop through each bit to find whether its set or not. Start by writing down a few numbers along with their bit counts, using any method you like to count the bits: Number Bits 0 0 1 1 2 1 3 2 Now find the straight line that gives the best least-squares fit to the observed data (any spreadsheet will do this for you if you can't recall the math). Take the fitted coefficients and write your function: double bit_count(int number) { return 0.6 * number + 0.1; } Use more data points, if you like, to get a statistically more accurate fit. There, that wasn't so hard, was it? -- Eric Sosman es*****@ieee-dot-org.invalid Sep 27 '07 #3

 P: n/a On Sep 27, 5:48 pm, Eric Sosman

 P: n/a karthikbalaguru wrote: On Sep 27, 5:48 pm, Eric Sosman Mack wrote: >>Hi all, I want to write a program to count number of bits set in a number.The condition is we should not loop through each bit to find whetherits set or not. [Snip] A rough idea will be like this... Just a very very high level idea. Not the exact algorithm for you. Take the number in which you want to count the bits set , And the first bit, check if it is set, add it to your bitset counter if it is set. Move to next bit And the next bit, check if it is set , add it to your bitset counter if it is set. Move to next bit. What part of "we should not loop through each bit" didn't you understand? Sep 27 '07 #5

 P: n/a On Sep 27, 6:06 pm, Mark Bluemel

 P: n/a Mack wrote: Hi all, I want to write a program to count number of bits set in a number. I think you meant to say "my homework is to write ...". The condition is we should not loop through each bit to find whether its set or not. We're not going to write it for you, but a few moments with Google for "bit manipulation tricks" or some similar search term would be valid research I'd say... I found a wonderfully elegant solution in a matter of moments... Sep 27 '07 #7