Decimal to Binary

Q: Bạn có thể chuyển sang hệ nhị phân bằng các phép toán bit thay vì phép chia không?

Đúng. n & 1 cho ra bit thấp nhất và n >> 1 loại bỏ bit đó, tương tự như n % 2 và n / 2 với các số không âm. Vòng lặp và thao tác đảo ngược vẫn giữ nguyên.

Người mớiToán và mô phỏng Thao tác bit

+10

Bạn được cho một số nguyên không âm n. Hãy trả về biểu diễn nhị phân của số đó dưới dạng chuỗi (string) gồm các 0 và 1, không có số 0 ở đầu. Số duy nhất có đáp án bắt đầu bằng 0 là chính số 0, được viết là "0".

Hàm

toBinary(n: integer) → string

ninteger: số cần chuyển đổi
Trả vềstring: các chữ số nhị phân của n dưới dạng chuỗi (string)

Ràng buộc

0 ≤ n ≤ 2³¹-1
Tự xây dựng chuỗi (string) thay vì gọi hàm chuyển đổi cơ số có sẵn.

Ví dụ

Đầu vào: n = 13
Đầu ra: "1101"
Giải thích: 13 = 8 + 4 + 1. Các vị trí ứng với 8, 4, 2 và 1 lần lượt chứa 1, 1, 0 và 1, tạo thành 1101.

Đầu vào: n = 0
Đầu ra: "0"
Giải thích: Số không không có bit nào được đặt, nhưng đáp án vẫn cần một chữ số, nên là "0" chứ không phải chuỗi rỗng.

Đầu vào: n = 64
Đầu ra: "1000000"
Giải thích: 64 là 2^6: một 1 ở vị trí hàng 64, rồi sáu 0 ở các vị trí từ 32 xuống 1.

Câu hỏi mở rộng

Bạn có thể chuyển n sang bất kỳ cơ số nào từ 2 đến 16 bằng cùng một vòng lặp, dùng các chữ cái từ a đến f cho các chữ số lớn hơn 9 không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Số nhị phân là tổng các lũy thừa của 2, và mỗi chữ số cho biết một lũy thừa có nằm trong tổng đó hay không. Bạn có thể tìm các chữ số từ trên xuống bằng cách trừ các lũy thừa của 2, hoặc tìm từ dưới lên bằng cách lấy số dư sau khi liên tục chia cho 2. Phép chia là phương pháp tiêu chuẩn: phương pháp này không cần tìm lũy thừa lớn nhất và áp dụng được cho mọi cơ số.

Trừ các lũy thừa của 2 từ trên xuống

Ý tưởng

Đây là cách chuyển đổi thủ công. Lũy thừa lớn nhất của hai không vượt quá n cho chữ số đầu tiên, là 1. Sau đó giảm dần từng lũy thừa một: nếu lũy thừa đó không vượt quá phần còn lại, hãy viết 1 rồi trừ đi lũy thừa đó; nếu không, hãy viết 0.

Với 13: 8 vừa (còn lại 5), 4 vừa (còn lại 1), 2 không vừa, 1 vừa. Các chữ số đọc được là 1101. Chữ số đầu tiên luôn là 1, nên không có số 0 ở đầu. Chỉ nhân đôi power khi power ≤ n / 2 để tìm lũy thừa lớn nhất mà không vượt quá n. Một số 31 bit cần 31 bước, O(log n).

Thuật toán

Nếu n bằng 0, trả về "0".
Đặt power bằng 1 rồi nhân đôi power trong khi power ≤ n / 2.
Trong khi power > 0: nếu n ≥ power, thêm 1 rồi trừ power khỏi n; nếu không, thêm 0.
Chia đôi power rồi lặp lại.
Trả về các chữ số bạn đã thêm.

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)

Phép chia liên tiếp cho 2

Ý tưởng

n % 2 là chữ số nhị phân cuối cùng của n. Chia cho 2 rồi làm tròn xuống sẽ loại bỏ chữ số đó và dịch các chữ số còn lại sang phải một vị trí, nên chữ số tiếp theo trở thành chữ số cuối cùng. Lặp lại cho đến khi n bằng 0, bạn sẽ thu thập được mọi chữ số, từ hàng thấp nhất trước.

Với 13, các số dư lần lượt là 1, 0, 1, 1 (từ 13, 6, 3 và 1); khi đảo ngược, chúng tạo thành 1101. Vòng lặp dừng ở 0, nên chữ số cao nhất nó ghi ra là 1. Số 0 không bao giờ vào vòng lặp, vì vậy cần kiểm tra riêng trường hợp này. Mỗi bước giảm một nửa n: thời gian và bộ nhớ đều là O(log n).

Thuật toán

Nếu n bằng 0, trả về "0".
Khi n > 0, thêm n % 2 làm một chữ số rồi đặt n thành n / 2, làm tròn xuống.
Đảo ngược các chữ số vì chúng xuất hiện từ nhỏ nhất đến lớn nhất.
Trả về chúng dưới dạng chuỗi.

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)

Lỗi thường gặp và trường hợp biên

Trả về chuỗi rỗng (empty string) khi giá trị là 0. Vòng lặp chia không chạy khi giá trị bằng 0, vì vậy hãy kiểm tra trường hợp này trước.
Quên đảo ngược kết quả. Các số dư xuất hiện theo thứ tự từ chữ số thấp nhất đến cao nhất, nên kết quả là 011 thay vì 110.
Dùng / khi toán tử này trả về phân số, như trong JavaScript, Lua hoặc PHP. 13 / 2 phải cho ra 6, vì vậy hãy làm tròn xuống.
Nhân đôi lũy thừa cho đến khi nó lớn hơn n. Với n ≥ 2^30, lũy thừa sẽ đạt 2^31, gây tràn số nguyên 32 bit.
Trong C, cấp phát quá ít bộ nhớ: một số 31 bit cần 31 ký tự, cộng thêm ký tự kết thúc '\0'.

Câu hỏi thường gặp3

Làm thế nào để chuyển đổi một số thập phân sang hệ nhị phân?

Tiếp tục chia số đó cho 2 và ghi lại mỗi số dư cho đến khi số đó bằng 0. Đọc các số dư từ số cuối cùng đến số đầu tiên. Với 13, các số dư là 1, 0, 1, 1, nên 13 trong hệ nhị phân là 1101.

Độ phức tạp thời gian của việc chuyển đổi từ hệ thập phân sang hệ nhị phân là bao nhiêu?

Mỗi bước giảm số đi một nửa, nên vòng lặp chạy một lần cho mỗi chữ số nhị phân, khoảng log2(n) lần. Độ phức tạp thời gian là O(log n) và độ phức tạp bộ nhớ là O(log n) cho chuỗi kết quả, tối đa 31 bước với số nguyên 32 bit.

Bạn có thể chuyển sang hệ nhị phân bằng các phép toán bit thay vì phép chia không?

Đúng. n & 1 cho ra bit thấp nhất và n >> 1 loại bỏ bit đó, tương tự như n % 2 và n / 2 với các số không âm. Vòng lặp và thao tác đảo ngược vẫn giữ nguyên.

def toBinary(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 13

Đầu ra mong đợi

"1101"