Số Bit Bưu Điện Hà Nội

Mô tả

Bưu điện Hà Nội đang nâng cấp hệ thống định tuyến bưu phẩm tự động. Hiện tại trung tâm phân loại có N vùng bưu chính khác nhau, mỗi vùng cần được gắn một mã nhị phân duy nhất để máy quét có thể nhận diện trong tích tắc.

Để tiết kiệm băng thông và chi phí in tem barcode, ban giám đốc yêu cầu bạn — kỹ sư phần mềm — xác định số bit tối thiểu cần thiết để tạo đủ mã phân biệt cho tất cả N vùng.

Quy tắc rất đơn giản:

• Với k bit, bạn có thể tạo ra tối đa 2^k mã nhị phân khác nhau (từ 0 đến 2^k - 1).
• Bạn cần tìm k nhỏ nhất sao cho 2^k >= N.

Ví dụ:

• N = 1 thì k = 0 (chỉ cần 1 vùng, không cần bit nào vì mã rỗng cũng là một mã duy nhất).
• N = 4 thì k = 2 (4 mã: 00, 01, 10, 11).
• N = 5 thì k = 3 (vì 2^2 = 4 chưa đủ, cần 2^3 = 8).

Đầu vào

Một số nguyên dương N (1 <= N <= 10^9) — số vùng bưu chính cần mã hóa.

Đầu ra

Trả về một số nguyên không âm k — số bit tối thiểu cần thiết.

Ràng buộc

• 1 <= N <= 10^9
• k luôn nằm trong phạm vi số nguyên 32-bit.

Ví dụ

Ví dụ 1:

• Đầu vào: N = 1
• Đầu ra: 0
• Giải thích: Khi chỉ có 1 vùng, mã rỗng (0 bit) đã đủ để nhận diện. Không cần thêm bit nào.

Ví dụ 2:

• Đầu vào: N = 8
• Đầu ra: 3
• Giải thích: 2^3 = 8, vừa đủ cho 8 vùng. Các mã là 000, 001, 010, 011, 100, 101, 110, 111.

Ví dụ 3: