Decimal to Binary

Q: Bisakah kamu mengonversi ke biner dengan operasi bit, bukan pembagian?

Ya. n & 1 menghasilkan bit paling rendah dan n >> 1 menghapusnya, sama seperti n % 2 dan n / 2 untuk bilangan nonnegatif. Perulangan dan pembalikan tetap sama.

PemulaMatematika dan simulasi Manipulasi bit

+10

Kamu mendapatkan bilangan bulat nonnegatif n. Kembalikan representasi binernya sebagai string yang terdiri dari 0 dan 1, tanpa nol di depan. Satu-satunya bilangan yang jawabannya diawali dengan 0 adalah nol itu sendiri, yang ditulis "0".

Fungsi

toBinary(n: integer) → string

ninteger: angka yang akan dikonversi
Mengembalikanstring: digit biner dari n sebagai string

Batasan

0 ≤ n ≤ 2³¹-1
Bangun string itu sendiri alih-alih memanggil konversi basis bawaan.

Contoh

Input: n = 13
Output: "1101"
Penjelasan: 13 = 8 + 4 + 1. Posisi untuk 8, 4, 2, dan 1 berisi 1, 1, 0, dan 1, sehingga terbaca 1101.

Input: n = 0
Output: "0"
Penjelasan: Nol tidak memiliki bit yang disetel, tetapi jawabannya tetap memerlukan satu digit, jadi hasilnya adalah "0", bukan string kosong.

Input: n = 64
Output: "1000000"
Penjelasan: 64 adalah 2^6: satu 1 pada posisi 64, lalu enam 0 untuk posisi dari 32 hingga 1.

Pertanyaan lanjutan

Bisakah kamu mengonversi n ke basis apa pun dari 2 hingga 16 dengan perulangan yang sama, menggunakan huruf a hingga f untuk digit di atas 9?

Petunjuk

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

0 dari 3 dibuka

Solusi

Bilangan biner adalah jumlah pangkat-pangkat dua, dan setiap digit menunjukkan apakah suatu pangkat termasuk dalam jumlah tersebut. Kamu bisa menemukan digit-digitnya dari atas dengan mengurangkan pangkat-pangkat dua, atau dari bawah sebagai sisa pembagian berulang dengan 2. Pembagian adalah metode standar: metode ini tidak memerlukan pangkat terbesar dan berlaku untuk setiap basis.

Kurangi dengan pangkat dua tertinggi

Intuisi

Ini adalah konversi secara manual. Pangkat dua terbesar yang dapat dimuat ke dalam n memberikan digit pertama, yaitu 1. Lalu turunkan satu pangkat setiap kali: jika pangkat tersebut muat ke dalam sisa nilai, tulis 1 dan kurangi nilainya; jika tidak, tulis 0.

Untuk 13: 8 muat (tersisa 5), 4 muat (tersisa 1), 2 tidak muat, 1 muat. Digitnya terbaca sebagai 1101. Digit pertama selalu 1, jadi tidak ada nol di depan. Menggandakan power hanya selama power ≤ n / 2 akan menemukan pangkat terbesar tanpa melampaui n. Bilangan 31-bit memerlukan 31 langkah, O(log n).

Algoritma

Jika n adalah 0, kembalikan "0".
Mulai dengan power bernilai 1 dan gandakan selama power ≤ n / 2.
Selama power > 0: jika n ≥ power, tambahkan 1 dan kurangi n dengan power; jika tidak, tambahkan 0.
Bagi dua power dan ulangi.
Kembalikan digit yang kamu tambahkan.

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)

Pembagian berulang dengan 2

Intuisi

n % 2 adalah digit biner terakhir dari n. Membagi dengan 2 lalu membulatkan ke bawah akan menghapus digit itu dan menggeser sisanya satu posisi ke kanan, sehingga digit berikutnya menjadi digit terakhir. Ulangi sampai n bernilai 0, lalu kamu mengumpulkan setiap digit, mulai dari yang paling rendah.

Untuk 13, sisanya adalah 1, 0, 1, 1 (dari 13, 6, 3, dan 1); jika dibalik, hasilnya 1101. Perulangan berhenti saat nilainya 0, jadi digit tertinggi yang ditulisnya adalah 1. Nol tidak pernah masuk ke perulangan, karena itu nol perlu diperiksa secara terpisah. Setiap langkah membagi n menjadi dua: waktu dan ruang O(log n).

Algoritma

Jika n adalah 0, kembalikan "0".
Selama n > 0, tambahkan n % 2 sebagai digit dan atur n menjadi n / 2, dibulatkan ke bawah.
Balik urutan digitnya karena digit tersebut muncul dari yang terkecil terlebih dahulu.
Kembalikan digit tersebut sebagai string.

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)

Jebakan dan kasus tepi

Mengembalikan string kosong untuk 0. Perulangan pembagian tidak pernah berjalan untuk nol, jadi periksa terlebih dahulu.
Lupa membalik urutan. Sisa muncul mulai dari digit terendah, jadi 6 menghasilkan 011, bukan 110.
Menggunakan / saat operator itu menghasilkan pecahan, seperti di JavaScript, Lua, atau PHP. 13 / 2 harus menjadi 6, jadi bulatkan ke bawah.
Menggandakan pangkat hingga nilainya melebihi n. Untuk n ≥ 2^30, nilainya mencapai 2^31, yang menyebabkan overflow pada integer 32-bit.
Di C, mengalokasikan terlalu sedikit: angka 31-bit memerlukan 31 karakter ditambah '\0' sebagai terminator.

Pertanyaan yang sering diajukan3

Bagaimana cara mengonversi bilangan desimal ke biner?

Bagi angka tersebut dengan 2 berulang kali, catat setiap sisanya, hingga angkanya mencapai 0. Baca sisa-sisanya dari yang terakhir hingga yang pertama. Untuk 13, sisanya adalah 1, 0, 1, 1, jadi 13 dalam biner adalah 1101.

Berapa kompleksitas waktu untuk mengubah desimal menjadi biner?

Setiap langkah membagi dua bilangan, jadi perulangan berjalan sekali untuk setiap digit biner, sekitar log2(n) kali. Kompleksitas waktunya O(log n) dan penggunaan ruangnya O(log n) untuk string jawaban, paling banyak 31 langkah untuk bilangan bulat 32-bit.

Bisakah kamu mengonversi ke biner dengan operasi bit, bukan pembagian?

Ya. n & 1 menghasilkan bit paling rendah dan n >> 1 menghapusnya, sama seperti n % 2 dan n / 2 untuk bilangan nonnegatif. Perulangan dan pembalikan tetap sama.

def toBinary(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

n = 13

Output yang diharapkan

"1101"