Bitwise OR (หรือ - ) ของช่วงใน C++

ในปัญหานี้ เราได้รับค่าจำนวนเต็มสองค่า a และ b และงานของเราคือค้นหาระดับบิต OR (|) ของช่วงจาก a ถึง b ซึ่งหมายความว่าเราจะต้องหาค่าของ | a+1 | a+2 | … b-1 | ข.

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − a =3 , b =8

ผลผลิต − 15

คำอธิบาย − 3 | 4 | 5 | 6 | 7 | 8 =15

ในการแก้ปัญหา วิธีแก้ไขง่ายๆ คือเริ่มจาก a และค้นหา OR ที่ฉลาดระดับบิตของตัวเลขทั้งหมดโดยเพิ่มจากหนึ่งเป็น b

โซลูชันที่มีประสิทธิภาพยิ่งขึ้น

นี่เป็นวิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้น ซึ่งสามารถทำได้โดยใช้ −

ขั้นตอนที่ 1 − ค้นหาบิต MSB สำหรับทั้ง a และ b สมมติว่าเป็น MSBa และ MSBb

ขั้นตอนที่ 2 − ตรวจสอบว่า MSBa เท่ากับ MSBb หรือไม่

ขั้นตอนที่ 2.1 − ถ้า MSBa และ MSBb เท่ากัน ทำ

ขั้นตอนที่ 2.1.1 - ตั้งค่า MSB ของผลลัพธ์เป็น 1

ขั้นตอนที่ 2.1.2 - ลบ MSB จาก a และ b ซึ่งจะเป็นค่าใหม่สำหรับ a และ b ไปที่ขั้นตอนที่ 1

ขั้นตอนที่ 2.2 − หาก MSBa และ MSBb เท่ากัน ทำ

ขั้นตอนที่ 2.2.1 - ตั้งค่าบิตทั้งหมดตั้งแต่ 0 ถึงสูงสุด (MSBa, MSBb) ของผลลัพธ์

ขั้นตอนที่ 3 − พิมพ์ผลลัพธ์

ตอนนี้เรามาดูอัลกอริธึมด้านบนในการทำงานกัน -

ตัวอย่าง − a =3 และ b =8

วิธีแก้ปัญหา −

ขั้นที่ 1 − MSBa =1; MSBb =3

ขั้นที่ 2 − MSBa !=MSBb ตั้งค่าบิตทั้งหมดจากตำแหน่งบิต 3 เป็นตำแหน่งบิต 0 ของผลลัพธ์เป็น 1 ผล =(1111)2 =15

ตัวอย่าง

มาดูโค้ดแก้ปัญหากัน

#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;
}

ผลลัพธ์

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