hi can anyone give me efficient algorithm to count the number of bits in a number. proposed complexity is number of bits in a number itself.
Printable View
hi can anyone give me efficient algorithm to count the number of bits in a number. proposed complexity is number of bits in a number itself.
Try this:
Hope this helps,Code:int Number = 1234;
int BitSize = sizeof(Number) * 8; // bit width of number variable
int BitTest = 1; // should be same data type as 'Number'
int NumberOfBitsInNumber = 0;
for(int BitCount = 0; BitCount < BitSize; BitCount++)
{
if(Number & BitTest)
NumberOfBitsInNumber++;
BitTest <<= 1;
}
printf("NumberOfBitsInNumber = %d\n", NumberOfBitsInNumber);
- Nigel
A little more C++...
Code:#include <iostream>
#include <bitset>
#include <limits>
int main()
{
unsigned long ul = 15476536;
std::cout << "Number of bits set: "
<< std::bitset<std::numeric_limits<unsigned long>::digits>(ul).count()
<< std::endl;
return 0;
}
Yes, but if you want FAST:
No loops involved. I actually found this on the web, at http://www-db.stanford.edu/~manku/bi.../bitcount.html . The proof is at the web site there, but the idea is this. Consider a 3 bit number as 4a + 2b + c. If you shift right and subtract, you get 2a + b + c. Shift the original by 2 bits, and subtract again, you get a + b + c, or the number of bits in the original number! They then go on to extend this concept to triplets of the octal representation of the original number.Code:int bitCount(unsigned int n)
{
// This is for 32 bit numbers. Need to adjust for 64 bits
register unsigned int tmp;
tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
Viggy
Nifty!
Clearly the folks up at Stanford have little better to do with their time :eek:
Although, better them than me I guess... :ehh:
Regards,
- Nigel
HA! I always figured that was why I'm an engineer, not a scientist. I'd rather take something someone has figured out, and put it to good use for the benefit of all mankind (oh, and for the benefit of my bank account as well).
:cool:
Viggy
In Dr. Paul Carter's online asm book (http://www.drpaulcarter.com/pcasm/) shows several algos. to count the number of bits (3 ways, to be exact, with one of the methods being similiar to MrViggy's post).
2 examples from the book (assumes int is 32-bits)
Code:int count_bits(unsigned int data)
{ int count = 0;
while (data != 0)
{ data = data & (data - 1);
count++;
}
return count;
}
The last one use's a look-up table and is the longest of the 3. Explanations for all 3 methods are explained in his book (section 3.6).Code:int count_bits(unsigned int data)
{ static unsigned int mask[] = { 0x55555555,
0x33333333,
0x0F0F0F0F,
0x00FF00FF,
0x0000FFFF }
;
for (int i = 0, shift = 1; i < 5; i++, shift *= 2)
data = (data & mask[i]) + (x >> shift) & mask[i]);
return data;
}
thanx for the replies,
but what i was looking for was a algorithm that do it in order k, where k is number of 1 bits ie our answer.
I think Mr. Viggy's post will do the job in even a better way.
thnx all once again.
I find this one rather intersting in that all it's doing is using one of the algorthims I had found earlier to find out wether something was a power of 2 or not, but just in a loop ;).Quote:
Originally Posted by cma
Err... what does "register" do?Quote:
Originally Posted by MrViggy
In today's modern optimizing compiler, absolutely nothing. It's suppose to suggest to the compiler that instead of allocating space for a variable in slower memory, to use a register instead. The register keyword now is about as useless as the auto keyword.Quote:
Originally Posted by YourSurrogateGod
And I am equally clueless what auto does as well :) .Quote:
Originally Posted by cma
It could be used to explicitly state that you want to put the variable etc. onto the stack (which basically happens for not dynamically allocated objects anyway), however, it is basically obsolete in C++...Quote:
Originally Posted by YourSurrogateGod
Both are so-called storage class specifiers. From the standard:
Quote:
Originally Posted by 7.1.1 Storage class specifiers
number of bits in x:
static_cast<int> floor(1+log(x)/log(2))