fast binary digit counter 64bits numbers c#

Question

I try to find a solution of this everywhere. My Request is to find a very fast algorithm code in order to get the number of digits in a binary representation of a unsigned 64bit integrer (ulong).

For example:

127 = 7 binary digits.

153 = 8 binary digits.

I found by now 2 ways to get this.

• By getting the binary representation trimmed in a string, and use ".Length" property.
• By getting the biggest power of 2 that does NOT pass the number. The result is the very last position of the binary representation, and also indicates the number of digits if you add 1 (that represent 2^0)

Both ways are good, but takes too long to calculate when the number is big. After 10.000.000.000 (10 billions) u have to count the time spent in seconds, instead of miliseconds, and that is so bad for the performance of the rest of the code.

Thanks so much and sorry about the presentation, this is written from a phone and i dont have all the tools to put this fancier and correct.

EDIT 1

By taking a deeply look into Bithacks website and having the speed as the first priority. I think I am going to use the Lookup table Method with the De Bruijn sequence implementation.

As i found here: the lookup table for 64bits with 2^6 should be something like this.

static readonly int[] MultiplyDeBruijnBitPosition2 = new int[64]
{
  0,1,2,4,8,17,34,5,11,23,47,31,63,62,61,59,
  55,46,29,58,53,43,22,44,24,49,35,7,15,30,60,57,
  51,38,12,25,50,36,9,18,37,10,21,42,20,41,19,39,
  14,28,56,48,33,3,6,13,27,54,45,26,52,40,16,32
};

And based on this, the user "R.." from Stackoverflow, he makes his own paramether that in C# should be something like this:

public static int GetLog2_DeBruijn(ulong v)
{
return MultiplyDeBruijnBitPosition2[(ulong)(v * 0x022fdd63cc95386dull) >> 58];
}

The result is really fast but wrong, and i dont know exactly why. PD: As you can see "0x022fdd63cc95386dull" is for 128bits, the accepted code for C# is "0x022fdd63cc95386d". The same that appear in the lookup tables here.

I think because i cant use the "0x022fdd63cc95386dull" in C#, i have to use another number instead of 58, or maybe a whole different hexadecimal 64bit multiplicator.

By now, for the input number: 17012389719861204799 (64bits used)

• Using pow2 method i get the result 64 1 Million times in 1380ms.
• Using DeBruijn method i get the result 40 1 Million times in 32ms. (Dont know why 40)

Answer 1

According to bit twiddling hack page, you can find the highest bit set like this:

uint v;
uint r;
uint shift;

r =     (uint)((v > 0xFFFF) ? 1 : 0) << 4; v >>= (int)r;
shift = (uint)((v > 0xFF  ) ? 1 : 0) << 3; v >>= (int)shift; r |= shift;
shift = (uint)((v > 0xF   ) ? 1 : 0) << 2; v >>= (int)shift; r |= shift;
shift = (uint)((v > 0x3   ) ? 1 : 0) << 1; v >>= (int)shift; r |= shift;
                                        r |= (v >> 1);
// At this point r has the result

Here is a demo on ideone.

Answer 2

Try squaring 2 up to the greatest value smaller than the number you are considering. Then shift by that digit count (2^n digits after n squaring steps), and repeat, summing the digit counts along the way. This should be an order log log n process.