Tuyên bố vấn đề
Cho một số n, nhiệm vụ là tìm số 0 lớn nhất giữa hai số 1 ngay lập tức trong biểu diễn nhị phân của n đã cho. Trả về -1 nếu biểu diễn nhị phân chứa ít hơn hai chữ 1
Ví dụ
Nếu số đầu vào là 35 thì biểu diễn nhị phân của nó là -
00100011
Trong biểu diễn nhị phân ở trên, có 3 số 0 nằm giữa hai số 1 ngay lập tức. Do đó câu trả lời là 3.
Thuật toán
Chúng ta có thể sử dụng toán tử dịch chuyển bitwise để giải quyết vấn đề này. Chúng ta cần tìm vị trí của hai số 1 ngay lập tức trong biểu diễn nhị phân của n và tối đa hóa sự khác biệt của các vị trí này.
- Nếu số là 0 hoặc lũy thừa của 2 thì trả về -1
- Biến IInitialize chiếm ưu thế với vị trí của phần lớn bên phải đầu tiên 1. Nó lưu trữ vị trí của biến đã thấy trước đó 1.
- Lấy một biến cur khác lưu trữ vị trí số 1 ngay sau vị trí trước đó.
- Nhận thấy sự khác biệt của cur - trước - 1, nó sẽ là số của giá trị 0 từ trước đến giá trị 1 ngay lập tức và so sánh nó với giá trị tối đa trước đó của 0 và cập nhật trước đó, tức là; trước =cur cho lần lặp tiếp theo.
- SetBit biến IUse, quét tất cả các bit của n và giúp phát hiện xem các bit hiện tại là 0 hay 1. Sử dụng setBit biến phụ trợ, quét tất cả các bit của n và giúp phát hiện xem các bit hiện tại là 0 hay 1.
Ví dụ
Bây giờ chúng ta hãy xem một ví dụ -
#include <bits/stdc++.h>
using namespace std;
int getMaxZeros(int n) {
if (n == 0 || (n & (n - 1) == 0)) {
return -1;
}
int setBit = 1;
int prev = 0;
int i;
for (i = 1; i < sizeof(int) * 8; ++i) {
++prev;
if ((n & setBit) == setBit) {
setBit = setBit << 1;
break;
}
setBit = setBit << 1;
}
int maxZeros = INT_MIN;
int cur = prev;
for (int j = i + 1; j <= sizeof(int) * 8; ++j) {
++cur;
if ((n & setBit) == setBit) {
if (maxZeros < (cur - prev - 1)) {
maxZeros = cur - prev - 1; prev = cur;
}
}
setBit = setBit << 1;
}
return maxZeros;
}
int main() {
int n = 35;
cout << "Maximum zeros = " << getMaxZeros(n) << endl;
return 0;
} Đầu ra
Maximum zeros = 3