Bitwise OR (|) ของช่วงตัวเลขใน C++

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

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต − a = 3, b = 8

เอาต์พุต − 15

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

วิธีง่ายคือเริ่มจาก a หา bitwise OR ของทุกตัวเลขโดยเพิ่มทีละ 1 จนถึง b

วิธีที่มีประสิทธิภาพมากกว่า

วิธีนี้ทำได้โดย −

ขั้นตอน 1 − หา MSB (Most Significant Bit) ของทั้ง a และ b ให้เป็น MSBa และ MSBb

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

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

− กำหนด MSB ของผลลัพธ์เป็น 1

− ลบค่า MSB ออกจาก a และ b ซึ่งจะเป็นค่าใหม่ของ a และ b กลับไปขั้นตอน 1

ขั้นตอน 2.2 − ถ้า MSBa และ MSBb ไม่เท่ากัน ทำ:

− กำหนดบิตทั้งหมดจาก 0 ถึง max(MSBa, MSBb) ของผลลัพธ์เป็น 1

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

ตอนนี้ มาดูตัวอย่างการทำงานของอัลกอริทึมข้างต้น −

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

วิธีแก้ −

ขั้นตอน 1 − MSBa = 1; MSBb = 3

ขั้นตอน 2 − MSBa != MSBb กำหนดบิตทั้งหมดจากตำแหน่งบิต 3 ถึง 0 ของผลลัพธ์เป็น 1 result = (1111)₂ = 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 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;
}

เอาต์พุต

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