Number of 1 Bits

Q: Độ phức tạp thời gian của Number of 1 Bits là bao nhiêu?

Vòng lặp dịch bit chạy một lần cho mỗi chữ số nhị phân: O(log n) , tối đa 31 bước ở đây. Vòng lặp n & (n-1) chạy một lần cho mỗi bit 1: O(k) , trong đó k là đáp án. Cả hai đều dùng thêm O(1) không gian.

DễThao tác bit

+10

Bạn được cho một số nguyên không âm n. Hãy viết n ở dạng nhị phân và trả về số chữ số 1 của nó. Số lượng này còn được gọi là số bit được đặt, số bit 1 hoặc trọng số Hamming. Ví dụ, 6 được viết là 110 ở dạng nhị phân, nên có hai bit 1.

Hàm

hammingWeight(n: integer) → integer

ninteger: một số nguyên không âm vừa với kiểu int có dấu 32 bit
Trả vềinteger: số chữ số 1 trong dạng nhị phân của n

Ràng buộc

0 ≤ n ≤ 2³¹-1

Ví dụ

Đầu vào: n = 11
Đầu ra: 3
Giải thích: 11 là 1011 trong hệ nhị phân, bằng 8 + 2 + 1. Ba trong số bốn chữ số nhị phân của nó là 1, vậy đáp án là 3.

Đầu vào: n = 128
Đầu ra: 1
Giải thích: 128 là 2^7, được viết là 10000000: một số 1 duy nhất theo sau là các số 0, vậy đáp án là 1.

Câu hỏi mở rộng

Nếu hàm (function) này chạy hàng triệu lần, làm thế nào bạn có thể đếm số bit của một số 32-bit chỉ với bốn lần tra cứu trong bảng gồm 256 số đếm đã tính trước?

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

Duyệt qua các chữ số nhị phân của n mà không tạo chuỗi. Đọc bit cuối cùng rồi dịch nó đi mất một bước cho mỗi chữ số nhị phân, tối đa 31 bước. Xóa bit 1 thấp nhất bằng n & (n-1) mất một bước cho mỗi bit 1, chính xác bằng số bước của đáp án.

Kiểm tra phần cuối cùng và dịch sang phải

Ý tưởng

n & 1 là chữ số nhị phân cuối cùng của n: bằng 1 khi n là số lẻ, bằng 0 khi n là số chẵn. Hãy cộng chữ số đó vào số đếm. Sau đó, n >> 1 loại bỏ chữ số đó và chuyển chữ số tiếp theo vào vị trí cuối cùng; với số không âm, thao tác này tương đương với phép chia cho 2 rồi làm tròn xuống. Với 11, 1011, các bit cuối lần lượt là 1, 1, 0 và 1 khi n giảm dần về 0: có ba bit 1.

Vòng lặp dừng khi n bằng 0, nên không bao giờ duyệt các số 0 ở đầu: khoảng log2(n) bước, 8 bước với 128 và tối đa 31 bước. Nó chỉ lưu n và số đếm.

Thuật toán

Bắt đầu bộ đếm ở giá trị 0.
Khi n lớn hơn 0, cộng n & 1 vào bộ đếm.
Dịch n sang phải một bit.
Khi n đạt đến 0, trả về bộ đếm.

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

Xóa bit 1 thấp nhất bằng n & (n-1)

Ý tưởng

Trừ 1 sẽ biến bit 1 thấp nhất thành 0 và mọi bit 0 bên dưới nó thành 1, đồng thời giữ nguyên các bit phía trên. Vì vậy, n & (n-1) giữ lại các bit phía trên và xóa bit 1 thấp nhất: 12 là 1100, 11 là 1011, và 1100 & 1011 là 1000.

Mỗi bước xóa chính xác một bit 1, nên số bước cần để n bằng 0 chính là đáp án. Với 128, chỉ cần 1 bước thay vì 8, dù 2^31-1 vẫn cần 31 bước. Lua 5.1 không có toán tử bit, nên phiên bản này tìm bit 1 thấp nhất bằng cách chia đôi rồi trừ bit đó; vòng lặp vẫn chạy một lần cho mỗi bit 1.

Thuật toán

Bắt đầu bộ đếm ở giá trị 0.
Khi n khác 0, thay n bằng n & (n-1).
Tăng bộ đếm thêm 1 sau mỗi lần thay thế.
Trả về bộ đếm.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

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

Lặp khi n > 1. Vòng lặp dừng trước bit 1 cuối cùng và trả về 0 khi n = 1.
Chia bằng số thực. Trong JavaScript, Lua và R, 11 / 2 bằng 5.5 và các số dư tiếp theo là phân số. Làm tròn xuống bằng Math.floor, math.floor hoặc %/%, hoặc dùng phép dịch bit.
Viết n & 1 trong Lua 5.1. Lua 5.1 không có toán tử bit, nên code không biên dịch được; hãy dùng n % 2 và math.floor(n / 2).

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

Độ phức tạp thời gian của Number of 1 Bits là bao nhiêu?

Vòng lặp dịch bit chạy một lần cho mỗi chữ số nhị phân: O(log n), tối đa 31 bước ở đây. Vòng lặp n & (n-1) chạy một lần cho mỗi bit 1: O(k), trong đó k là đáp án. Cả hai đều dùng thêm O(1) không gian.

Có hàm dựng sẵn nào đếm các bit được đặt không?

Hầu hết các ngôn ngữ đều có sẵn một hàm như vậy, thường được hỗ trợ bởi một lệnh xử lý duy nhất: Integer.bitCount trong Java, __builtin_popcount trong GCC, bits.OnesCount trong Go, count_ones trong Rust và int.bit_count trong Python 3.10 trở lên. Khi phỏng vấn, hãy viết vòng lặp và nhắc đến hàm dựng sẵn.

Trọng số Hamming và khoảng cách Hamming khác nhau như thế nào?

Trọng số Hamming của một số là số chữ số nhị phân bằng 1 của số đó, và bài toán này trả về giá trị ấy. Khoảng cách Hamming giữa hai số là số vị trí bit mà chúng khác nhau: hãy đếm số bit bằng 1 trong a ^ b, vì XOR chỉ đặt bit ở những vị trí mà chúng khác nhau.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 11

Đầu ra mong đợi