1

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)
Improve this question
4
  • Did you 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. Commented Feb 18, 2014 at 2:31
  • You should show your code - I can't really imagine algorithm of checking at most 64 bits than takes "seconds" to complete... Commented Feb 18, 2014 at 2:55
  • Well Alexei, well, yeah, it needs less than a sec, for just 1 operation, but for 10.000 operations for example for the same number it takes 200 times more than 10.000 operations of get number of Digits in decimal, hexadecimal and even the bitcount, all together. Commented Feb 18, 2014 at 3:21
  • what about use of bsr asm instruction ? on some CPUs is dasblinkenlight way faster for 32bit but for 64bit should be bsr instruction much faster. still you should check by measurement ... btw hope you 2^n is done by shifting and not by pow. Commented Feb 18, 2014 at 8:44

2 Answers 2

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Does this process extend to ulong in C#?
@abiessu Yes, you should be able to extend this to 64 bit.
It looks good and linear, but the other website said that it takes time for big 64bits numbers, and recommend having a table in memory (if u can). Ill check the code speed tomorrow.
The DeBruijn sequence algorithm is faster for 32 bits, and can be extended to 64 bits. See stackoverflow.com/a/10150991/56778
ive just edited the question, based on Jim Mischel comentary.
|
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.