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!

Felix Crazzolara
  • 982
  • 9
  • 24
  • 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... – Felix Crazzolara May 12 '17 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 '17 at 17:33
  • @yshavit Didn't know this function, thanks, I'll give it a shot! – Felix Crazzolara May 12 '17 at 17:35
  • @yshavit Wouldn't [`numberOfTrailingZeros(long i)`](https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#numberOfTrailingZeros-long-) be better, assuming index value should be 0 for the least significant bit (LSB), which is generally the norm. – Andreas May 12 '17 at 17:54
  • @Andreas Ah yes, good catch. – yshavit May 12 '17 at 17:56

2 Answers2

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.

Andreas
  • 154,647
  • 11
  • 152
  • 247
apangin
  • 92,924
  • 10
  • 193
  • 247
-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.

D. Mika
  • 2,577
  • 1
  • 13
  • 29
  • Bit shifting is the same as multiply/divide by two, at least if it's compiled, but byte code should do the same. – Felix Crazzolara May 12 '17 at 17:44
  • 1
    @Felix.C Maybe bit shifting is *functionally* the same as division by 2, but bit shifting is *faster* than division. In integer math, division is a slow operation, much slower than add, subtract, shift, and even multiply. E.g. see "[Why is division more expensive than multiplication?](http://stackoverflow.com/q/15745819/5221149)" or "[Why is multiplying cheaper than dividing?](http://stackoverflow.com/q/1117674/5221149)" – Andreas May 12 '17 at 18:02