Muszę obliczyć bazę logów 2 liczby w C, ale nie mogę korzystać z biblioteki matematycznej. Odpowiedź nie musi być dokładna, tylko do najbliższej int. Zastanawiałem się nad tym i wiem, że mogłem po prostu użyć pętli while i dalej dzielić liczbę przez 2, aż będzie to < 2 i zachować liczbę iteracji, ale czy jest to możliwe za pomocą operatorów bitowych?Jak wykonać komputerową bazę 2 przy użyciu operatorów bitowych?
Jeśli policzyć shifting jako operator bitowy, jest to łatwe.
Wiesz już, jak to zrobić przez kolejne dzielenia przez 2.
x >> 1 jest taka sama jak x/2 dla dowolnej liczby całkowitej bez znaku w C
Jeśli musisz zrobić to szybciej, można zrobić "dziel i rządź" - przesuń, powiedzmy, 4 bity naraz, aż osiągniesz 0, a następnie wróć i zobacz ostatnie 4 bity. Oznacza to co najwyżej 16 zmian i 19 porównań zamiast 63 każdego z nich. Niezależnie od tego, czy jest to rzeczywiście szybsze na nowoczesnym procesorze, nie mogłem powiedzieć bez testowania. I możesz zrobić to o krok dalej, najpierw zrobić grupy 16, potem 4, potem 1. Prawdopodobnie nie jest to użyteczne, ale gdybyś miał 1024-bitowe liczby całkowite, może być warte rozważenia.
Dzięki, nie zdawałem sobie sprawy, jak było oczywiste. Rozgryzłem to. – SKLAK
@SKLAK: Dla dodatkowej zabawy spróbuj skompilować kod '/ 2' i' >> 1' za pomocą -O2 i zobacz, jak to się różni. Jeśli jeden jest znacznie szybszy od drugiego, możesz uzyskać ten sam kod dla obu. – abarnert
Będą one takie same dla "unsigned". Dla 'int', istnieje dodatkowa operacja, aby wcześniej dodać bit znaku, co zapewnia, że wynik zaokrągla się w kierunku zera zamiast ujemnej nieskończoności. –
już odpowiedział przez abamert ale po prostu być bardziej konkretne to jak byś go kod:
Log2(x) = result
while (x >>= 1) result++;
Czy liczysz [przesunięcie] (http://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts) jako operator bitowy? Jeśli tak, odpowiedź jest dość oczywista. Jeśli nie, to jest trudniejsze. – abarnert
0_o Dlaczego nie możesz skorzystać z biblioteki matematycznej? –
@JackManey: Prawdopodobnie jest to zadanie domowe lub samouczący odpowiednik. Ale to w porządku; wydaje się, że włożył w to trochę wysiłku (zawsze ma rozwiązanie robocze) i szuka wskazówek, czy istnieje inny sposób, aby to zrobić, nie prosząc nas, abyśmy zrobili dla niego swoją pracę domową. – abarnert