bit count

[Amit Sebiz]

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.

[NigelQ]

Try this:

	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);

Hope this helps,

- Nigel

[Andreas Masur]

A little more C++...

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

[MrViggy]

Yes, but if you want FAST:

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;
}

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.

Viggy

[NigelQ]

Nifty!

Clearly the folks up at Stanford have little better to do with their time

Although, better them than me I guess...

Regards,

- Nigel

[MrViggy]

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).



Viggy

[cma]

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)

int count_bits(unsigned int data)
{   int count = 0;

    while (data != 0)
    {    data = data & (data - 1);
         count++;
    }
    
    return count;
}

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;
}

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).

[Amit Sebiz]

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.

[barrensoul]

int count_bits(unsigned int data)
{   int count = 0;

    while (data != 0)
    {    data = data & (data - 1);
         count++;
    }
    
    return count;
}

[/code]
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).

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 .

[YourSurrogateGod]

Yes, but if you want FAST:

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;
}

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.

Viggy

Err... what does "register" do?

[cma]

Err... what does "register" do?

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.

[YourSurrogateGod]

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.

And I am equally clueless what auto does as well .

[Andreas Masur]

And I am equally clueless what auto does as well .

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++...

Both are so-called storage class specifiers. From the standard:

2 The auto or register specifiers can be applied only to names of objects declared in a block (6.3) or to function parameters (8.4). They specify that the named object has automatic storage duration (3.7.2). An object declared without a storage-class-specifier at block scope or declared as a function parameter has
automatic storage duration by default. [Note: hence, the auto specifier is almost always redundant and not often used; one use of auto is to distinguish a declaration-statement from an expression-statement (6.8) explicitly. —end note]

3 A register specifier has the same semantics as an auto specifier together with a hint to the implementation that the object so declared will be heavily used. [Note: the hint can be ignored and in most implementations it will be ignored if the address of the object is taken. —end note]

[T.G.]

number of bits in x:

static_cast<int> floor(1+log(x)/log(2))