C # Pierwszy 1 (od prawej do lewej) w liczbie binarnej

Próbuję użyć C #, aby znaleźć indeks pierwszej 1 (od prawej do lewej) w binarnej reprezentacji liczby. Na przykład, ponieważ 100 w systemie binarnym to:

0b1100100

Pierwsza 1 znajduje się na trzeciej pozycji z prawej strony, więc powinna dać 3.

234 powinno dać 2, 0 powinno dać 0, itd.

Oto moje obecne rozwiązanie:

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

W jaki sposób mogę to skrócić?

Jeśli tylko C # obsługuje wewnętrzne specyficzne dla maszyny… Istnieje jedna instrukcja, która może to zrobić w języku asemblera x86, a także w większości innych architektur procesorów. Wtedy miałbyś nie tylko najkrótszy kod, ale najprawdopodobniej najszybszy.

W rzeczywistości skrócenie tego kodu jest niezwykle nudnym problemem w porównaniu do szybkiego uczynienia tego kodu . Istnieją różnego rodzaju naprawdę schludne, wydajne rozwiązania, które mogą być zmienne, a także można rozważyć użycie tabeli przeglądowej.

Nie ma to jednak znaczenia dla gry w golfa. Wydaje mi się, że twoje obecne rozwiązanie jest najlepsze, co możesz zrobić. Oczywiście można usunąć zbędne białe znaki:

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

Osobiście napisałbym to jako:

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

ponieważ myślę, że nieco łatwiej jest wyznaczyć kierunek testu warunkowego w ten sposób, a także porównać go z zerem, ale myślę, że jest sześć w jedną stronę, a pół tuzina w drugą.

C # nie obsługuje niejawna konwersja z intaby booljak C i C ++ zrobić, tak naprawdę nie można skracać the warunkowy test dalej.

Utknąłeś również z jawnym rzutowaniem z double(jak zwrócił mój Math.Log) na int, ponieważ C # nie pozwoli na to niejawnie. Oczywiście jest to zwykle dobra rzecz, ponieważ wskazywałoby, że masz tutaj duży problem z wydajnością: awans intna a double, obliczenie logu a double, a następnie przekonwertowanie doublewyniku z powrotem na a intbędzie bardzo wolne, więc zwykle jest to coś którego chcesz uniknąć. Ale to są rodzaje perwersji, z którymi musisz się pogodzić, grając w golfa kodowego.

Początkowo wymyśliłem

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

(oczywiście nie dla jasności), co pozwala uniknąć logarytmu, a zatem poprawia rozmiar i szybkość kodu. Niestety, nie zawsze jest to prawidłowa odpowiedź i zakładam, że jest to nieelastyczny wymóg. :-) W szczególności nie powiedzie się, jeśli wartość wejściowa ( k) ma współczynnik 8. Można to naprawić, ale nie bez wydłużenia kodu w stosunku do Math.Logwersji.