0

I have a long with a single bit set and I need to know which it is, e.g. the index. I need to calculate this as fast as possible. The naive idea is to divide by 2 and check whether the result is 1. But this would need up to 63 iterations (worst case).

My next idea was to make like a binary search, e.g. to look wether it is bit 63-32 or 31-0 then 63 - 48, 47 - 31, 31 - 16, 15 - 0 and so on having many if-else statements, but this gives me hell of a bunch of code...

Furthermore I'd like to minimize object creation and memory used. You might suggest that I'm wrong then with Java and should use perhaps C/C++. Well it's for a school competition and I don't have a choice :)

I'd like to see some sample code!

5
  • My program relies heavily on this function and it is called very often, hopefully many hundreds of thousand times per second, does that mean, that I can assume that it will be compiled into machine code, e.g. no more bytecode interpretation somewhat soon after application start? As this is just a small side question and I'm more interested into code I put this into the comments, I hope this isn't against any rules... May 12, 2017 at 17:32
  • 2
    How about Long.html#numberOfLeadingZeros? The implementation of that does have a few branches, though fewer than 64.
    – yshavit
    May 12, 2017 at 17:33
  • @yshavit Didn't know this function, thanks, I'll give it a shot! May 12, 2017 at 17:35
  • @yshavit Wouldn't numberOfTrailingZeros(long i) be better, assuming index value should be 0 for the least significant bit (LSB), which is generally the norm.
    – Andreas
    May 12, 2017 at 17:54
  • @Andreas Ah yes, good catch.
    – yshavit
    May 12, 2017 at 17:56

2 Answers 2

6

Use Long.numberOfTrailingZeros - this will be exactly the index you are looking for.

Long.numberOfLeadingZeros can be also useful if you count bits starting from the highest one.

Both methods are JVM intrinsics, i.e. they are treated specially by JIT compiler. These methods are translated to a special CPU instruction (TZCNT / LZCNT) and thus are very efficient.

-3

You could prepare a Map<Int, Int>, holding the number of the set bit for each possible value, but I'm not sure if it is really faster than a loop.

Maybe bit shifting is faster than dividing by 2.

2

Not the answer you're looking for? Browse other questions tagged or ask your own question.