C# First 1 (right to left) in binary number

Question

I am trying to use C# to find the index of the first 1 (right to left) in the binary representation of a number. For example, since 100 in binary is:

0b1100100

The first 1 is in the third position from the right, so it should yield 3.

234 should yield 2, 0 should yield 0, etc.

Here is my current solution:

k < 1 ? 0 :(int)Math.Log(k & -k, 2) + 1;

Any ways I can make this shorter?

Answer 1

If only C# supported machine-specific intrinsics… There is a single instruction that can do this in x86 assembly language, and on most other processor architectures as well. Then you'd have not only the shortest code, but very likely the fastest.

In fact, making this code shorter is an extremely boring problem compared to making this code fast. There are all sorts of really neat, efficient, bit-twiddling solutions, and you could also consider using a look-up table.

None of that matters for golfing, though. It looks to me like your current solution is the best you can do. Of course, you can remove the superfluous whitespace:

k<1?0:(int)Math.Log(k&-k,2)+1

I would personally write it as:

k>0?(int)Math.Log(k&-k,2)+1:0

because I think it's slightly clearer to have the direction of the conditional test that way, as well as to compare it against zero, but I guess it's six one way, half a dozen the other.

C# doesn't support implicit conversion from int to bool like C and C++ do, so you can't really shorten the conditional test any further.

You are also stuck with the explicit cast from double (as returned my Math.Log) to int, as C# won't allow this to happen implicitly. Of course, that's normally a good thing because it would point out that you have a big performance problem here: promoting an int to a double, computing the log of a double, and then converting the double result back to an int will be massively slow, so it's normally something that you'd want to avoid. But these are the kinds of perversions you have to put up with when playing code golf.

---

I had initially come up with

k > 0
      ? ((k & -k) >> 1) + 1
      : 0

(ungolfed for clarity, of course), which avoids taking the logarithm and is therefore an improvement in code size and speed. Unfortunately, this doesn't always get the right answer, and I assume that's an inflexible requirement. :-) Specifically, it fails if the input value (k) is a factor of 8. This is fixable, but not without making the code longer than the Math.Log version.