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

by

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

More Related Contents:

  1. how to convert 0x8080 to 8080 int? [closed]
  2. How to detect Windows 64-bit platform with .NET?
  3. Reading 64bit Registry from a 32bit application
  4. Is shifting bits faster than multiplying and dividing in Java? .NET? [closed]
  5. C# – How to get Program Files (x86) on Windows 64 bit
  6. Fast computing of log2 for 64-bit integers
  7. Using Side-by-Side assemblies to load the x64 or x32 version of a DLL
  8. How to find if a native DLL file is compiled as x64 or x86?
  9. Checking if a bit is set or not
  10. Silent failures in C#, seemingly unhandled exceptions that does not crash the program
  11. C# int to byte[]
  12. How do I disable a system device programmatically?
  13. File getting copied to SysWOW64 instead of System32
  14. Add two integers using only bitwise operators?
  15. sizeof(int) on x64?
  16. Can I get Memcached running on a Windows (x64) 64bit environment?
  17. Visual Studio designer in x64 doesn’t work
  18. Compute fast log base 2 ceiling
  19. System.BadImageFormatException: Could not load file or assembly [duplicate]
  20. How do I tell if my application is running as a 32-bit or 64-bit application?
  21. Is an int a 64-bit integer in 64-bit C#?
  22. Reading the registry and Wow6432Node key
  23. What’s the quickest way to compute log2 of an integer in C#?
  24. Convert int bits to float bits
  25. .net Framework Error (HRESULT 0x8007000B)
  26. IIS 7.5 Fixing An attempt was made to load a program with an incorrect format problem?
  27. Memory limitations in a 64-bit .Net application?
  28. How can I convert bits to bytes?
  29. Is there a way to perform a circular bit shift in C#?
  30. Left bit shifting 255 (as a byte)

Leave a Comment