Bitwise OR (hoặc -) của một dải ô trong C ++

Trong bài toán này, chúng ta được cho hai giá trị nguyên a và b. Và nhiệm vụ của chúng ta là tìm bitwise OR (|) của phạm vi từ a đến b. Điều này có nghĩa là chúng ta sẽ phải tìm giá trị của một | a + 1 | a + 2 | … B-1 | b.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - a =3, b =8

Đầu ra - 15

Giải thích - 3 | 4 | 5 | 6 | 7 | 8 =15

Để giải quyết vấn đề, một giải pháp đơn giản là bắt đầu từ a và tìm HOẶC theo bit khôn ngoan của tất cả các số bằng cách tăng một đến b.

Giải pháp hiệu quả hơn,

Đây là một giải pháp hiệu quả hơn, điều này có thể được thực hiện bằng cách sử dụng -

Bước 1 - Tìm bit MSB cho cả a và b, giả sử chúng là MSBa và MSBb.

Bước 2 - Kiểm tra xem MSBa có bằng MSBb không.

Bước 2.1 - nếu MSBa và MSBb bằng nhau. Làm,

Bước 2.1.1 - Đặt MSB của kết quả là 1.

Bước 2.1.2 - Trừ MSB cho a và b sẽ được giá trị mới của a và b. Chuyển đến bước 1.

Bước 2.2 - Nếu MSBa và MSBb bằng nhau. Làm,

Bước 2.2.1 - Đặt tất cả các bit từ 0 đến max (MSBa, MSBb) của kết quả.

Bước 3 - In kết quả.

Bây giờ, hãy xem thuật toán trên hoạt động -

Ví dụ - a =3 và b =8.

Giải pháp -

Bước 1 - MSBa =1; MSBb =3

Bước 2 - MSBa! =MSBb, đặt tất cả các bit từ vị trí bit 3 đến vị trí bit 0 của kết quả thành 1. result =(1111) 2 =15.

Ví dụ

Bây giờ, hãy xem mã để giải quyết vấ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 CalcBitwiseORRaneg( 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 "<<CalcBitwiseORRaneg(a, b);
   return 0;
}

Đầu ra

The bitwise OR (|) of all integers in the range from 3 to 8 is 15