Trong bài toán này, ta được cho hai số nguyên a và b. Nhiệm vụ: tìm bitwise AND (&) của khoảng từ a đến b, tức tính a & (a+1) & (a+2) & ... & b.
Ví dụ minh họa
Đầu vào** – a = 3, b = 8
Đầu ra** – 0
Giải thích** – 3 & 4 & 5 & 6 & 7 & 8 = 0
Cách đơn giản: từ a tính AND lần lượt đến b.
Cách hiệu quả hơn:**
Bước 1** – Lật bit thấp nhất (LSB) của b.
Bước 2** – So sánh số mới với a và b, kiểm tra xem có trong khoảng không.
2.1** Nếu số mới > a: lật LSB tiếp theo.
2.2** Nếu không: số mới là kết quả.
Minh họa: a=3, b=8. b=8 (1000₂), lật LSB (bit 3) → 0000 = 0. 0 < 3 → kết quả = 0.
Ví dụ
Code giải bài toán:
#include <stdio.h>
int main() {
long a, b;
a = 3; b = 8;
do {
b -= (b & -b);
} while(a < b);
printf("%li", b);
}
Đầu ra
0