Trong bài toán này, ta được cho hai số nguyên a và b. Nhiệm vụ: tìm bitwise OR (|) 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** – 15
Giải thích** – 3 | 4 | 5 | 6 | 7 | 8 = 15
Cách đơn giản: từ a tính OR lần lượt đến b.
Cách hiệu quả hơn:**
Bước 1** – Tìm bit quan trọng nhất (MSB) của a và b, gọi là MSBa, MSBb.
Bước 2** – So sánh MSBa và MSBb.
2.1** Nếu bằng nhau: đặt bit MSB của kết quả = 1. Trừ giá trị MSB khỏi a và b, quay lại Bước 1.
2.2** Nếu khác nhau: đặt tất cả bit từ 0 đến max(MSBa, MSBb) của kết quả = 1.
Bước 3** – In kết quả.
Minh họa: a=3 (MSB=1), b=8 (MSB=3). MSB khác nhau → đặt bit 3,2,1,0 = 1 → kết quả = 1111₂ = 15.
Ví dụ
Code giải bài toán:
#include <iostream>
using namespace std;
int FindPositionMSB(long long int n) {
int MSBval = -1;
while (n) {
n = n >> 1;
MSBval++;
}
return MSBval;
}
long int CalcBitwiseORRange(long int a, long int b) {
long int result = 0;
int msba = FindPositionMSB(a);
int msbb = FindPositionMSB(b);
while (msba == msbb) {
long int value = (1 << msba);
result += value;
a -= value;
b -= value;
msba = FindPositionMSB(a);
msbb = FindPositionMSB(b);
}
msba = max(msba, msbb);
for (int i = msba; i >= 0; i--) {
long int res_val = (1 << i);
result += res_val;
}
return result;
}
int main() {
long int a = 3, b = 8;
cout << "The bitwise OR (|) of all integers in the range from " << a << " to " << b << " is " << CalcBitwiseORRange(a, b);
return 0;
}
Đầu ra
The bitwise OR (|) of all integers in the range from 3 to 8 is 15