10
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ The obvious tip is to remove your extraneous whitespace. I see 10 spaces that you could easily remove. \$\endgroup\$ – DJMcMayhem Apr 12 '17 at 20:01
  • \$\begingroup\$ Convert.ToString(k,2).IndexOf("1") is what you want, or something similar, wrong site though. \$\endgroup\$ – Magic Octopus Urn Apr 12 '17 at 20:17
  • 14
    \$\begingroup\$ @close-voters - Why the close-votes? I think this is an on-topic tips question. Or have there been any rules changes I've missed in this regard? \$\endgroup\$ – Digital Trauma Apr 12 '17 at 20:31
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Note that for code golf the Math would have to be fully qualified so your other version should be better although I haven't actually counted the bytes. \$\endgroup\$ – TheLethalCoder Jul 14 '17 at 13:02
  • \$\begingroup\$ You mean the one that produces the wrong output? @the \$\endgroup\$ – Cody Gray Jul 14 '17 at 13:15
  • \$\begingroup\$ Well you said there's a fix to it but it would make it longer. If the fix is shorter than when the OPs version includes System. then it should be shorter and correct. \$\endgroup\$ – TheLethalCoder Jul 14 '17 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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