Binary to Decimal

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

Cả hai vòng lặp đều duyệt qua từng ký tự trong n ký tự đúng một lần, nên có độ phức tạp thời gian là O(n) . Chúng chỉ giữ lại một hoặc hai số, nên cần thêm O(1) bộ nhớ.

Q: Bạn có thể chuyển đổi từ nhị phân sang thập phân bằng cách dịch bit không?

Đúng vậy. value = (value << 1) | digit tương đương với value * 2 + digit : phép dịch trái nhân đôi giá trị, còn phép OR đặt bit thấp nhất. Dạng số học cũng dùng được với các cơ số khác 2.

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

+10

Bạn nhận được một chuỗi s biểu diễn một số không âm ở dạng nhị phân, chỉ dùng các ký tự 0 và 1. Hãy trả về giá trị của số đó dưới dạng số nguyên thông thường. Chuỗi không có số 0 ở đầu, ngoại trừ số 0 được biểu diễn bằng duy nhất ký tự 0.

Hàm

toDecimal(s: string) → integer

sstring: các chữ số nhị phân của số
Trả vềinteger: giá trị của s dưới dạng số nguyên

Ràng buộc

1 ≤ s.length ≤ 31
s chỉ chứa 0 và 1.
s bắt đầu bằng 1, trừ khi s là "0".
Tự đọc các chữ số thay vì gọi hàm chuyển đổi cơ số có sẵn.

Ví dụ

Đầu vào: s = "1101"
Đầu ra: 13
Giải thích: Đọc từ phải sang trái, các vị trí có giá trị lần lượt là 1, 2, 4 và 8. 1101 có chữ số 1 ở các vị trí 8, 4 và 1, nên 8 + 4 + 1 = 13.

Đầu vào: s = "0"
Đầu ra: 0
Giải thích: Một chữ số 0 không có chữ số 1 ở bất kỳ vị trí nào, nên giá trị của nó là 0.

Đầu vào: s = "10000000"
Đầu ra: 128
Giải thích: Số 1 duy nhất có bảy số 0 ở bên phải, nên nó nằm ở vị trí có giá trị 2^7 = 128.

Câu hỏi mở rộng

Bạn có thể đọc một số được viết ở bất kỳ cơ số nào từ 2 đến 16 bằng cùng một vòng lặp, trong đó các chữ cái từ a đến f biểu thị các chữ số từ 10 đến 15 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

Mỗi chữ số nhị phân biểu thị một lũy thừa của hai, được xác định bởi vị trí của nó tính từ đầu bên phải. Bạn có thể cộng các lũy thừa đó từ phải sang trái, hoặc đọc từ trái sang phải và nhân đôi giá trị ở mỗi bước: cùng một vòng lặp dùng để đọc văn bản thập phân, nhưng thay 10 bằng 2.

Thêm giá trị hàng từ bên phải

Ý tưởng

Chữ số ngoài cùng bên phải có giá trị là 1, mỗi vị trí bên trái có giá trị gấp đôi vị trí liền trước. Số đó bằng tổng các giá trị vị trí có chữ số 1, vì vậy hãy duyệt từ ký tự cuối cùng về ký tự đầu tiên, giữ giá trị vị trí hiện tại trong power và cộng giá trị đó mỗi khi gặp chữ số 1.

Mỗi chữ số được duyệt đúng một lần: thời gian O(n) và bộ nhớ dùng hai số.

Thuật toán

Đặt total = 0 và power = 1.
Duyệt chuỗi từ ký tự cuối cùng đến ký tự đầu tiên.
Nếu ký tự là 1, cộng power vào total.
Nhân đôi power trước khi dịch sang trái một vị trí.
Trả về 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

Nhân đôi rồi cộng từ bên trái

Ý tưởng

Giữ value làm giá trị của số được biểu diễn bằng các chữ số đã đọc. Thêm một chữ số sẽ dịch mỗi chữ số trước đó sang trái một vị trí, khiến giá trị của nó tăng gấp đôi, rồi cộng thêm chữ số mới: value = value * 2 + digit. Với 1101, value lần lượt là 1, 3, 6, 13.

Mỗi tiền tố của chuỗi là một số nhị phân nhỏ hơn và vòng lặp luôn giữ đúng giá trị của số đó, nên sau chữ số cuối cùng, nó giữ đáp án. Giá trị không bao giờ vượt quá đáp án cuối cùng, vì vậy số nguyên 32 bit là đủ cho 31 chữ số. Không cần tính lũy thừa.

Thuật toán

Đặt value = 0.
Với mỗi ký tự từ trái sang phải, chuyển ký tự đó thành một chữ số bằng cách trừ đi mã của '0'.
Đặt value = value * 2 + digit.
Trả về 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

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

Gán giá trị hàng là 1 cho chữ số ngoài cùng bên trái. Khi đó, 1101 được đọc là 11.
Cộng ký tự thay vì chữ số. Trong nhiều ngôn ngữ, '1' là số 49, nên value * 2 + '1' có giá trị lớn hơn nhiều; hãy trừ '0' trước.
Nhân đôi power sau chữ số cuối cùng trong số nguyên 32 bit. Với chuỗi gồm 31 chữ số, giá trị này đạt đến 2^31, khiến số bị tràn hoặc chương trình gặp sự cố; hãy giữ giá trị trong 64 bit hoặc bỏ qua lần nhân đôi cuối cùng.

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

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

Gán cho mỗi chữ số một giá trị vị trí, là một lũy thừa của 2 bắt đầu từ 1 ở ngoài cùng bên phải, rồi cộng các giá trị vị trí của những chữ số bằng 1. Hoặc đọc các chữ số từ trái sang phải và đặt value = value * 2 + digit ở mỗi bước.

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

Cả hai vòng lặp đều duyệt qua từng ký tự trong n ký tự đúng một lần, nên có độ phức tạp thời gian là O(n). Chúng chỉ giữ lại một hoặc hai số, nên cần thêm O(1) bộ nhớ.

Bạn có thể chuyển đổi từ nhị phân sang thập phân bằng cách dịch bit không?

Đúng vậy. value = (value << 1) | digit tương đương với value * 2 + digit: phép dịch trái nhân đôi giá trị, còn phép OR đặt bit thấp nhất. Dạng số học cũng dùng được với các cơ số khác 2.

def toDecimal(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "1101"

Đầu ra mong đợi