Binary to Decimal

Q: Jaka jest złożoność czasowa konwersji liczby binarnej na dziesiętną?

Obie pętle odwiedzają każdy z n znaków raz, więc działają w czasie O(n) . Przechowują tylko jedną lub dwie liczby, co oznacza O(1) dodatkowej pamięci. Dla ciągu o długości 31 znaków to 31 kroków.

Q: Czy potrafisz przekształcić liczbę binarną na dziesiętną za pomocą przesunięć bitowych?

Tak. value << 1 podwaja wartość, a | digit ustawia najmłodszy bit, więc value = (value << 1) | digit robi to samo co value * 2 + digit . Zapis z przesunięciem jasno pokazuje, że przesuwasz bity, natomiast zapis arytmetyczny działa również dla podstaw innych niż 2.

PoczątkującyMatematyka i symulacja Operacje na bitach

+10

Otrzymujesz ciąg znaków s, który zapisuje nieujemną liczbę w systemie binarnym, używając wyłącznie znaków 0 i 1. Zwróć wartość tej liczby jako zwykłą liczbę całkowitą. Ciąg nie zawiera zer wiodących, z wyjątkiem liczby zero, która składa się z pojedynczego znaku 0.

Funkcja

toDecimal(s: string) → integer

sstring: cyfry binarne liczby
Zwracainteger: wartość s jako liczba całkowita

Ograniczenia

1 ≤ s.length ≤ 31
s zawiera tylko 0 i 1.
s zaczyna się od 1, chyba że s ma wartość "0".
Odczytaj cyfry samodzielnie, zamiast wywoływać wbudowaną konwersję systemu liczbowego.

Przykłady

Wejście: s = "1101"
Wyjście: 13
Wyjaśnienie: Czytając od prawej strony, pozycje mają wartości 1, 2, 4 i 8. 1101 ma jedynki na pozycjach odpowiadających 8, 4 i 1, a 8 + 4 + 1 = 13.

Wejście: s = "0"
Wyjście: 0
Wyjaśnienie: Pojedyncze 0 nie ma jedynki na żadnej pozycji, więc jego wartość wynosi 0.

Wejście: s = "10000000"
Wyjście: 128
Wyjaśnienie: Jedynka ma po swojej prawej stronie siedem zer, więc znajduje się na miejscu o wartości 2^7 = 128.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz odczytać liczbę zapisaną w dowolnym systemie o podstawie od 2 do 16 za pomocą tej samej pętli, w której litery a–f oznaczają cyfry od 10 do 15?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każda cyfra binarna oznacza potęgę liczby dwa, zależną od jej odległości od prawego końca. Możesz dodawać te potęgi, zaczynając od prawej strony, albo odczytywać ciąg od lewej i podwajać wartość na każdym kroku. Pętla podwajająca nigdy nie oblicza potęgi i jest tą samą pętlą, której używasz do odczytywania tekstu dziesiętnego, z 2 zamiast 10.

Dodawaj wartości pozycyjne od prawej

Intuicja

Skrajna prawa cyfra ma wartość 1, następna 2, potem 4, 8 i tak dalej, podwajając się z każdym krokiem w lewo. Liczba jest sumą wartości pozycyjnych tych cyfr, które mają wartość 1. Przejdź więc od ostatniego znaku do pierwszego, przechowuj bieżącą wartość pozycyjną w power i dodawaj ją za każdym razem, gdy cyfra wynosi 1.

Dla 1101 napotykasz 1 (dodaj 1), 0 (pomiń 2), 1 (dodaj 4) i 1 (dodaj 8), co daje w sumie 13. Każda cyfra jest odwiedzana raz, więc pętla działa w czasie O(n) i zużywa pamięć na dwie liczby.

Zwróć uwagę na wielkość power. Dla 31-cyfrowego ciągu osiąga ono wartość 2^30 przy ostatniej cyfrze, a następnie jest jeszcze raz podwajane do 2^31, co nie mieści się w 32-bitowej liczbie całkowitej ze znakiem. Przechowuj power w zmiennej 64-bitowej albo przestań podwajać po ostatniej cyfrze.

Algorytm

Ustaw total = 0 i power = 1.
Przejdź przez ciąg znaków od ostatniego znaku do pierwszego.
Jeśli znakiem jest 1, dodaj power do total.
Podwój power przed przesunięciem się o jedno miejsce w lewo.
Zwróć total.

def toDecimal(s):
    total = 0
    power = 1  # the place value of the rightmost digit
    for i in range(len(s) - 1, -1, -1):
        if s[i] == "1":
            total += power
        power *= 2
    return total

Podwajaj i dodawaj od lewej

Intuicja

Odczytuj ciąg znaków od lewej strony i przechowuj w value liczbę zapisaną przez odczytane dotąd cyfry. Dopisanie kolejnej cyfry binarnej przesuwa każdą wcześniejszą cyfrę o jedno miejsce w lewo, co podwaja jej wartość, a następnie dodaje nową cyfrę. Dlatego każdy krok ma postać value = value * 2 + digit.

Dla 1101 wartość value wynosi kolejno 1, potem 1 * 2 + 1 = 3, następnie 3 * 2 + 0 = 6, a na końcu 6 * 2 + 1 = 13. Każdy prefiks ciągu znaków jest mniejszą liczbą binarną, a pętla przechowuje dokładnie tę liczbę, więc po odczytaniu ostatniej cyfry zawiera całą wartość.

Wartość nigdy nie przekracza końcowego wyniku, więc dla ciągu 31-cyfrowego mieści się w zakresie do 2^31-1, a 32-bitowa liczba całkowita wystarczy. Cyfra to kod znaku pomniejszony o kod znaku '0', co zamienia '1' na 1, a '0' na 0. To standardowy sposób parsowania liczby z tekstu w dowolnym systemie liczbowym.

Algorytm

Ustaw value = 0.
Dla każdego znaku, od lewej do prawej, zamień go na cyfrę, odejmując kod znaku '0'.
Ustaw value = value * 2 + digit.
Zwróć value.

def toDecimal(s):
    value = 0
    for ch in s:
        # Shift the digits read so far one place left, then add the new one.
        value = value * 2 + (ord(ch) - ord("0"))
    return value

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z kierunku przechodzenia lub z typu cyfry.

Przypisanie skrajnej lewej cyfrze wartości pozycyjnej 1. Wartości pozycyjne zaczynają się od prawego końca, więc przechodź od ostatniego znaku albo użyj pętli podwajającej, zaczynając od lewej.
Dodawanie znaku zamiast cyfry. W wielu językach '1' ma wartość liczby 49, więc value * 2 + '1' daje zdecydowanie za dużą wartość. Najpierw odejmij '0'.
Przepełnienie wartości pozycyjnej. Podwojenie power po 31. cyfrze daje 2^31, co w 32-bitowej liczbie całkowitej powoduje zawinięcie wartości lub awarię.
Obliczanie każdej wartości pozycyjnej za pomocą funkcji potęgowej zmiennoprzecinkowej. W C, C++ i Java pow(2, k) zwraca wartość typu double, którą trzeba następnie z powrotem przekonwertować na liczbę całkowitą.

Najczęstsze pytania4

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

Przypisz każdej cyfrze wartość pozycyjną: 1 dla skrajnej prawej, następnie 2, 4, 8 i tak dalej w lewo. Dodaj wartości pozycyjne cyfr, które mają wartość 1. Dla 1101 jest to 8 + 4 + 1 = 13.

Dlaczego podwojenie wartości działa?

Dopisanie kolejnej cyfry na końcu liczby binarnej przesuwa każdą wcześniejszą cyfrę o jedno miejsce w lewo, a każda pozycja ma wartość dwa razy większą niż pozycja po jej prawej stronie. Wartość dotychczasowej liczby się więc podwaja, a nowa cyfra dodaje 0 lub 1. Powtarzanie tego działania od pierwszej cyfry do ostatniej pozwala zbudować całą liczbę.

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

Obie pętle odwiedzają każdy z n znaków raz, więc działają w czasie O(n). Przechowują tylko jedną lub dwie liczby, co oznacza O(1) dodatkowej pamięci. Dla ciągu o długości 31 znaków to 31 kroków.

Czy potrafisz przekształcić liczbę binarną na dziesiętną za pomocą przesunięć bitowych?

Tak. value << 1 podwaja wartość, a | digit ustawia najmłodszy bit, więc value = (value << 1) | digit robi to samo co value * 2 + digit. Zapis z przesunięciem jasno pokazuje, że przesuwasz bity, natomiast zapis arytmetyczny działa również dla podstaw innych niż 2.