Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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?

like image 795
Jeff Meatball Yang Avatar asked Apr 25 '10 18:04

Jeff Meatball Yang


People also ask

Is long long a 64 bit?

long , ptr , and off_t are all 64 bits (8 bytes) in size. The 32-bit data model for z/OS® XL C/C++ compilers is ILP32 plus long long.

How can I get total number of bits in set?

Using Standard Libraries. We can also use bitset::count(), an inbuilt STL in C++ that returns the count of the total number of set bits in an integer.

How do you count set bits in a number STL?

bitset count() in C++ STL bitset::count() is an inbuilt STL in C++ which returns the number of set bits in the binary representation of a number. Parameter: The function accepts no parameter. Return Value: The function returns the number of set bits.


2 Answers

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

like image 111
Maciej Hehl Avatar answered Oct 07 '22 17:10

Maciej Hehl


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.

like image 24
MAK Avatar answered Oct 07 '22 17:10

MAK