đếm các con số sao cho một số phải có số lượng các bit được đặt làm số hiệu mã số?

Question

Với phạm vi [x, y], hãy tìm số đếm sao cho một số phải có số lượng bit được đặt làm số hiệu mã số?

Ví dụ: [15,17]

15 - 1111 - Count of bits is 4 - (4 is not a fibonacci number) 

16 - 10000 - Count of bits is 1 - (1 is a fibonacci number) 

17 - 10001 - Count of bits is 2 - (2 is a fibonacci number) 

Vì vậy, câu trả lời là 2 (16,17)

Rõ ràng chúng tôi đếm các bit bộ và kiểm tra xem nó một số fibonacci sử dụng tình trạng này dù (5x^2 +/- 4) là một hình vuông hoàn hảo ..

LƯU Ý: đây là câu hỏi phỏng vấn. Người phỏng vấn không hài lòng với cách tiếp cận trên.

Chúng ta có thể làm tốt hơn không?

Answer 1

Bạn có thể đảo ngược và đếm, cho mỗi số Fibonacci (tối đa một giới hạn, tôi sẽ nhận được điều đó), số lượng nó "tạo" nằm trong phạm vi.

Giả sử k là mã số (rõ ràng là bạn sẽ chỉ thử k là số Fibonacci, không đáng kể để tạo). Có bao nhiêu số có k bit được đặt và nằm giữa x và y? Gọi số này countBetween(x, y, k). Nó đơn giản hơn để đếm đến một giới hạn trên chỉ, do đó, xác định countBetween(x, y, k) = countUpTo(y, k) - countUpTo(x, k) (giả sử giới hạn trên độc quyền mà bạn có thể dễ dàng thay đổi).

countUpTo(x, k) rất đơn giản khi x là công suất của hai, cụ thể là log(x) nCr k. Nếu x không phải là một sức mạnh của hai, sau đó chia nó thành hai dãy,

1. quyền lực cao nhất của hai nhỏ hơn x, q và
2. phần còn lại lên đến x.

Phần thứ nhất lên đến q bạn đã có thể tính toán, phần thứ hai có một hàng đầu 1 và sau đó một số dòng sản phẩm mới bắt đầu (sau khi xoá 1) ở mức 0, vì vậy bạn có thể tính toán countUpTo(x - q, k - 1).

Điều này cung cấp cho bạn định nghĩa đệ quy là countUpTo và giả sử bạn có thể thực hiện a nCr b trong thời gian ít hơn O(a nCr b), thuật toán này không tương đương với việc hiển thị mọi số và kiểm tra nó.

Đối với giới hạn, rõ ràng là bạn không thể đặt nhiều bit hơn chiều dài của giới hạn trên, vì vậy bạn có thể dừng ở đó.

---

Ví dụ: countBetween(1024, 1000000, 5) = 15251

Chúng ta cần countUpTo(1024, 5) và countUpTo(1000000, 5). countUpTo(1024, 5) là trường hợp cơ sở, kết quả là nhật ký (1024) nCr 5 = 252.

Để countUpTo(1000000, 5), viết 1000000 dưới dạng thập lục phân để dễ dàng hơn để xem điều gì đang diễn ra: 0xF4240, công suất lớn nhất trong số đó tất nhiên là 0x80000, đóng góp nhật ký (0x80000) nCr 5 = 11628 và để lại một phần từ 0x80000 lên đến 0xF4240. Phần đó có thể được đếm với countUpTo(0x74240‬, 4) - bit trên luôn được đặt trong phạm vi đó, do đó nó được loại bỏ khỏi vấn đề bằng cách điều chỉnh giới hạn và số bit thiết lập.

Công suất lớn nhất của hai trong 0x74240 là 0x40000, đóng góp của log (0x40000) nCr 4 = 3060, để lại countUpTo(0x34240‬, 3).

Công suất lớn nhất của hai trong 0x34240 là 0x20000, đóng góp của log (0x20000) nCr 3 = 680, để lại countUpTo(0x14240‬, 2).

Công suất lớn nhất của hai trong 0x14240 là 0x10000, đóng góp của log (0x10000) nCr 2 = 120, để lại countUpTo(0x4240‬, 1).

Công suất lớn nhất của hai trong 0x4240 là 0x4000, đóng góp log (0x4000) nCr 1 = 14. Lá này là countUpTo(0x240‬, 0) là 1 vì không có bit để đặt và chỉ có một cách để đặt không bit.

Thêm tất cả chúng lên, 11628 + 3060 + 680 + 120 + 14 + 1 = 15503. Subtract 252 từ ràng buộc thấp và chúng tôi nhận 15251.

Ví dụ sử dụng số hợp lý nhỏ để bạn có thể dễ dàng xác minh họ bởi lực lượng vũ phu, ví dụ:

int count = 0; 
for (int i = 1024; i < 1000000; i++) 
    if (__popcnt(i) == 5) count++; 
std::cout << count << std::endl;