Decimal to Binary

Q: Czy potrafisz przekonwertować na system binarny za pomocą operacji bitowych zamiast dzielenia?

Tak. n & 1 daje najmłodszy bit, a n >> 1 usuwa go, co dla liczb nieujemnych jest tym samym co n % 2 i n / 2 . Pętla i odwracanie pozostają bez zmian. Dzielenie łatwiej wyjaśnić, a wersja z przesunięciem jest często stosowana w kodzie niskopoziomowym.

PoczątkującyMatematyka i symulacja Operacje na bitach

+10

Otrzymujesz nieujemną liczbę całkowitą n. Zwróć jej reprezentację binarną jako ciąg znaków złożony z 0 i 1, bez zer wiodących. Jedyną liczbą, której odpowiedź zaczyna się od 0, jest samo zero, zapisywane jako "0".

Funkcja

toBinary(n: integer) → string

ninteger: liczba do przekonwertowania
Zwracastring: binarne cyfry n jako ciąg

Ograniczenia

0 ≤ n ≤ 2³¹-1
Zbuduj ciąg samodzielnie, zamiast wywoływać wbudowaną konwersję między systemami liczbowymi.

Przykłady

Wejście: n = 13
Wyjście: "1101"
Wyjaśnienie: 13 = 8 + 4 + 1. Miejsca dla 8, 4, 2 i 1 zawierają odpowiednio 1, 1, 0 i 1, co daje zapis 1101.

Wejście: n = 0
Wyjście: "0"
Wyjaśnienie: Zero nie ma ustawionych bitów, ale odpowiedź nadal musi zawierać jedną cyfrę, więc jest to "0", a nie pusty ciąg.

Wejście: n = 64
Wyjście: "1000000"
Wyjaśnienie: 64 to 2^6, pojedyncza 1 na pozycji 64, po której następuje sześć 0 dla pozycji od 32 do 1.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz przekonwertować n na dowolny system o podstawie od 2 do 16 za pomocą tej samej pętli, używając liter a–f dla cyfr większych niż 9?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Liczba binarna jest sumą potęg liczby 2, a każda cyfra określa, czy dana potęga jest składnikiem tej sumy. Możesz wyznaczać cyfry od góry, odejmując potęgi liczby 2, albo odczytywać je od dołu jako reszty z kolejnych dzieleń przez 2. Pętla dzielenia to standardowa metoda: nie trzeba najpierw znajdować największej potęgi i działa tak samo dla każdej podstawy.

Odejmij potęgi dwójki od góry

Intuicja

Tak właśnie wykonujesz konwersję ręcznie. Znajdź największą potęgę dwójki, która mieści się w n; to pierwsza cyfra, 1. Następnie schodź o jedną potęgę niżej. Jeśli potęga nadal mieści się w tym, co pozostało, zapisz 1 i odejmij ją; w przeciwnym razie zapisz 0.

Dla 13 największą potęgą jest 8. Zapisz 1 i pozostaje 5. Następnie mieści się 4 (1, pozostaje 1), 2 się nie mieści (0), a 1 się mieści (1). Odczytane cyfry to 1101. Pierwsza cyfra jest zawsze równa 1, więc nie może pojawić się zero wiodące.

Znajdowanie największej potęgi wymaga ostrożności. Podwajanie power, aż przekroczy n, powoduje przepełnienie 32-bitowej liczby całkowitej, gdy n ≥ 2^30, ponieważ następna potęga to 2^31. Podwajanie tylko wtedy, gdy power ≤ n / 2, kończy się na właściwej potędze i nigdy nie przekracza n. Liczba 31-bitowa wymaga 31 kroków, czyli O(log n).

Algorytm

Jeśli n wynosi 0, zwróć "0".
Ustaw power na 1 i podwajaj je, dopóki power ≤ n / 2.
Dopóki power > 0: jeśli n ≥ power, dopisz 1 i odejmij power od n; w przeciwnym razie dopisz 0.
Podziel power przez 2 i powtórz.
Zwróć dopisane cyfry.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

Wielokrotne dzielenie przez 2

Intuicja

Ostatnia cyfra binarna n informuje, czy n jest nieparzyste, czyli jest nią n % 2. Dzielenie przez 2 i odrzucanie reszty przesuwa każdą cyfrę o jedno miejsce w prawo, więc następna cyfra staje się ostatnią. Powtarzaj to, aż nic nie zostanie, zbierając wszystkie cyfry od najmniej znaczącej.

Dla 13: 13 daje resztę 1, 6 daje 0, 3 daje 1, a 1 daje 1, po czym liczba wynosi 0. Reszty w kolejności to 1, 0, 1, 1; po odwróceniu dają 1101. Pętla kończy się, gdy liczba osiąga 0, więc najwyższa zapisywana przez nią cyfra zawsze wynosi 1 i nie pojawia się zero wiodące. Samo zero nigdy nie trafia do pętli, dlatego wymaga osobnego sprawdzenia.

Każdy krok zmniejsza liczbę o połowę, więc wartość 31-bitowa wymaga 31 kroków, czas O(log n), a ciąg cyfr zajmuje O(log n) pamięci.

Algorytm

Jeśli n wynosi 0, zwróć "0".
Gdy n > 0, dodaj n % 2 jako cyfrę i ustaw n na n / 2, zaokrąglając w dół.
Odwróć cyfry, ponieważ pojawiły się w odwrotnej kolejności.
Zwróć je jako ciąg znaków.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

Pułapki i przypadki brzegowe

Pętla jest krótka, a większość błędnych odpowiedzi wynika z jej dwóch końców.

Zwracanie pustego ciągu dla 0. Pętla dzielenia nie wykonuje się dla zera, więc sprawdź je najpierw.
Zapominanie o odwróceniu wyniku. Reszty pojawiają się od najmniej znaczącej cyfry, więc 6 daje 011 zamiast 110.
Używanie / w języku, w którym zwraca ułamek, takim jak JavaScript, Lua lub PHP. 13 / 2 musi dać 6, więc zaokrąglaj w dół lub użyj dzielenia całkowitoliczbowego.
Wyznaczanie największej potęgi przez podwajanie jej aż do przekroczenia n. Dla n = 2^31-1 następna potęga, 2^31, nie mieści się w 32-bitowej liczbie całkowitej.
Przydzielanie zbyt małej ilości pamięci w C. 31-bitowa liczba wymaga 31 znaków oraz kończącego ciąg znaku '\0'.

Najczęstsze pytania4

Jak zamienić liczbę dziesiętną na binarną?

Wielokrotnie dziel tę liczbę przez 2, zapisując każdą resztę, aż liczba osiągnie 0. Odczytaj reszty od ostatniej do pierwszej. Dla 13 reszty wynoszą 1, 0, 1, 1, więc 13 w systemie binarnym to 1101.

Dlaczego reszty odczytuje się w odwrotnej kolejności?

Pierwsze dzielenie przez 2 informuje, czy liczba jest nieparzysta, co odpowiada ostatniej cyfrze binarnej. Każde kolejne dzielenie ujawnia następną cyfrę po lewej stronie. Reszty otrzymujesz więc od najmniej znaczącej cyfry, a następnie odwracasz ich kolejność, aby zapisać liczbę w zwykły sposób.

Jaka jest złożoność czasowa konwersji liczby dziesiętnej na binarną?

Każdy krok dzieli liczbę przez dwa, więc pętla wykonuje się raz na każdą cyfrę binarną, czyli około log2(n) razy. To czas O(log n), a ciąg znaków z odpowiedzią zajmuje O(log n) miejsca. W przypadku liczby całkowitej 32-bitowej jest to maksymalnie 31 kroków.

Czy potrafisz przekonwertować na system binarny za pomocą operacji bitowych zamiast dzielenia?

Tak. n & 1 daje najmłodszy bit, a n >> 1 usuwa go, co dla liczb nieujemnych jest tym samym co n % 2 i n / 2. Pętla i odwracanie pozostają bez zmian. Dzielenie łatwiej wyjaśnić, a wersja z przesunięciem jest często stosowana w kodzie niskopoziomowym.