Count number of bits in a 64-bit (long, big) integer?

Question

I have read through this SO question about 32-bits, but what about 64-bit numbers? Should I just mask the upper and lower 4 bytes, perform the count on the 32-bits and then add them together?

Abject

Answer 1

You can find 64 bit version here http://en.wikipedia.org/wiki/Hamming_weight

It is something like this

static long NumberOfSetBits(long i)
{
    i = i - ((i >> 1) & 0x5555555555555555);
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
    return (((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56;
}

This is a 64 bit version of the code form here How to count the number of set bits in a 32-bit integer?

Using Joshua's suggestion I would transform it into this:

static int NumberOfSetBits(ulong i)
{
    i = i - ((i >> 1) & 0x5555555555555555UL);
    i = (i & 0x3333333333333333UL) + ((i >> 2) & 0x3333333333333333UL);
    return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56);
}

EDIT: I found a bug while testing 32 bit version. I added missing parentheses. The sum should be done before bitwise &, in the last line

EDIT2 Added safer version for ulong

Osterhus

should be unsigned long to avoid being burned – Mcclung

Operations should be unchecked. Otherwise the multiplication in the last line overflows very easily. But if they are unchecked, I think it works for signed long too. Even if the shift is an arithmetic one, most significant bits are discarded by a bitwise & and subtraction in the first line can overflow silently to the correct result. – Osterhus

Answer 2

A fast (and more portable than using non-standard compiler extensions) way:

int bitcout(long long n)
{
   int ret=0;
   while (n!=0)
   {
       n&=(n-1);
       ret++;
   }
   return ret;
}

Every time you do a n&=(n-1) you eliminate the last set bit in n. Thus this takes O(number of set bits) time.

This faster than the O(log n) you would need if you tested every bit - not every bit is set unless the number is 0xFFFFFFFFFFFFFFFF), thus usually you need far fewer iterations.

Wrongly

It has less loop than thecoop's if ((val & 0x1) == 0x1) count++; – Miru

Answer 3

Standard answer in C#:

ulong val = //whatever
byte count = 0;

while (val != 0) {
    if ((val & 0x1) == 0x1) count++;
    val >>= 1;
}

This shifts val right one bit, and increments count if the rightmost bit is set. This is a general algorithm that can be used for any length integer.

Marplot

Answer 4

What about an one liner:

BitOperations.PopCount(Mask);

Returns the population count (number of bits set) of a mask. Similar in behavior to the x86 instruction POPCNT. Compatible with x64! It uses an intrinsic (built-in instruction of the X86 architecture) to count the number of bits very fast in a 32 bit or 64 bit value.

NOTE: BitOperations.PopCount() is not CLS compliant. Take this under consideration.

Cheers

Kienan

While this code may solve the question, including an explanation of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please edit your answer to add explanations and give an indication of what limitations and assumptions apply. – Spillage