Cho hai số x và n, tìm vị trí bắt đầu của dãy 1 liên tiếp đầu tiên (32-bit) có độ dài ≥ n. Nếu không có trả về -1. Ví dụ x=35 (000...00100011), n=2 → vị trí 31.
Tìm số 0 dẫn đầu, sau đó tìm dãy 1 liên tiếp.
Ví dụ
#include<iostream> using namespace std; int leadingZeroCount(int x) { unsigned y; int n; n = 32; for(int i = 16; i > 1; i = i/2 ){ y = x >> i; if(y != 0){ n -= i; x = y; } } y = x >> 1; if (y != 0) return n - 2; return n - x; } int consecutiveOnePosition(unsigned x, int n) { int k, p; p = 0; while (x != 0) { k = leadingZeroCount(x); x = x << k; p = p + k; k = leadingZeroCount(~x); if (k >= n) return p + 1; x = x << k; p = p + k; } return -1; } int main() { int x = 35; int n = 2; cout << "Consecutive 1s of length " << n << " is starting from index: " << consecutiveOnePosition(x, n); }
Kết quả
Consecutive 1s of length 2 is starting from index: 31