Binary to Decimal

Q: Apa kompleksitas waktu untuk mengonversi bilangan biner menjadi desimal?

Kedua perulangan mengunjungi setiap karakter dari n satu kali, jadi keduanya membutuhkan waktu O(n) . Keduanya hanya menyimpan satu atau dua angka, sehingga membutuhkan ruang tambahan O(1) .

Q: Bisakah kamu mengonversi bilangan biner ke desimal dengan pergeseran bit?

Ya. value = (value << 1) | digit sama dengan value * 2 + digit : pergeseran menggandakan nilai dan operasi or mengatur bit paling rendah. Bentuk aritmetika juga berfungsi untuk basis selain 2.

PemulaMatematika dan simulasi Manipulasi bit

+10

Kamu mendapatkan string s yang menuliskan bilangan nonnegatif dalam biner, hanya menggunakan karakter 0 dan 1. Kembalikan nilai bilangan tersebut sebagai bilangan bulat biasa. String ini tidak memiliki angka nol di awal, kecuali untuk bilangan nol, yang hanya terdiri dari satu karakter 0.

Fungsi

toDecimal(s: string) → integer

sstring: digit biner dari bilangan tersebut
Mengembalikaninteger: nilai s sebagai bilangan bulat

Batasan

1 ≤ s.length ≤ 31
s hanya berisi 0 dan 1.
s dimulai dengan 1, kecuali jika s adalah "0".
Baca digitnya sendiri alih-alih memanggil konversi basis bawaan.

Contoh

Input: s = "1101"
Output: 13
Penjelasan: Dibaca dari kanan, nilai tempatnya adalah 1, 2, 4, dan 8. 1101 memiliki angka 1 pada tempat untuk 8, 4, dan 1, sehingga 8 + 4 + 1 = 13.

Input: s = "0"
Output: 0
Penjelasan: 0 tunggal tidak memiliki angka 1 di posisi mana pun, jadi nilainya adalah 0.

Input: s = "10000000"
Output: 128
Penjelasan: Satu-satunya angka 1 memiliki tujuh angka 0 di sebelah kanannya, jadi angka tersebut berada di posisi bernilai 2^7 = 128.

Pertanyaan lanjutan

Bisakah kamu membaca angka yang ditulis dalam basis apa pun dari 2 hingga 16 dengan perulangan yang sama, dengan huruf a hingga f mewakili digit 10 hingga 15?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap digit biner mewakili pangkat dua, yang ditentukan oleh jaraknya dari ujung kanan. Kamu bisa menjumlahkan pangkat-pangkat tersebut dari kanan, atau membaca dari kiri dan menggandakan nilainya di setiap langkah: perulangan yang sama dengan yang membaca teks desimal, dengan 2 sebagai pengganti 10.

Tambahkan nilai tempat dari kanan

Intuisi

Digit paling kanan bernilai 1, dan setiap posisi di sebelah kirinya bernilai dua kali posisi sebelumnya. Bilangan tersebut adalah jumlah nilai posisi yang berisi 1, jadi telusuri dari karakter terakhir ke karakter pertama, simpan nilai posisi saat ini di power, lalu tambahkan nilainya setiap kali menemukan 1.

Setiap digit dikunjungi satu kali: waktu O(n) dan menggunakan memori untuk dua bilangan.

Algoritma

Tetapkan total = 0 dan power = 1.
Telusuri string dari karakter terakhir hingga karakter pertama.
Jika karakternya adalah 1, tambahkan power ke total.
Gandakan power sebelum berpindah satu posisi ke kiri.
Kembalikan 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

Kalikan dua lalu tambahkan dari kiri

Intuisi

Pertahankan value, angka yang dinyatakan oleh digit yang sudah dibaca. Menambahkan satu digit lagi menggeser setiap digit sebelumnya satu tempat ke kiri, sehingga nilainya menjadi dua kali lipat, lalu menambahkan digit baru: value = value * 2 + digit. Untuk 1101, value berubah menjadi 1, 3, 6, 13.

Setiap prefiks string adalah bilangan biner yang lebih kecil dan perulangan menyimpan tepat bilangan tersebut, sehingga setelah digit terakhir dibaca, perulangan menyimpan jawabannya. Nilainya tidak pernah melebihi jawaban akhir, jadi integer 32-bit cukup untuk 31 digit. Tidak ada perpangkatan yang dihitung.

Algoritma

Atur value = 0.
Untuk setiap karakter dari kiri ke kanan, ubah menjadi digit dengan mengurangi kode '0'.
Atur value = value * 2 + digit.
Kembalikan 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

Jebakan dan kasus tepi

Memberi digit paling kiri nilai tempat 1. 1101 lalu bernilai 11.
Menambahkan karakter, bukan digit. Dalam banyak bahasa, '1' adalah angka 49, jadi value * 2 + '1' nilainya terlalu besar. Kurangi '0' terlebih dahulu.
Menggandakan power setelah digit terakhir dalam integer 32-bit. Untuk string 31 digit, nilainya mencapai 2^31, yang dapat mengalami overflow atau menyebabkan program crash. Simpan nilainya dalam 64 bit atau lewati penggandaan terakhir.

Pertanyaan yang sering diajukan3

Bagaimana cara mengonversi biner ke desimal?

Berikan setiap digit nilai tempat, yaitu pangkat dua yang dimulai dari 1 di ujung kanan, lalu jumlahkan nilai tempat dari digit yang bernilai 1. Atau, baca digit dari kiri dan tetapkan value = value * 2 + digit pada setiap langkah.

Apa kompleksitas waktu untuk mengonversi bilangan biner menjadi desimal?

Kedua perulangan mengunjungi setiap karakter dari n satu kali, jadi keduanya membutuhkan waktu O(n). Keduanya hanya menyimpan satu atau dua angka, sehingga membutuhkan ruang tambahan O(1).

Bisakah kamu mengonversi bilangan biner ke desimal dengan pergeseran bit?

Ya. value = (value << 1) | digit sama dengan value * 2 + digit: pergeseran menggandakan nilai dan operasi or mengatur bit paling rendah. Bentuk aritmetika juga berfungsi untuk basis selain 2.

def toDecimal(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "1101"

Output yang diharapkan