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

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

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

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

เอาต์พุต − 0

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

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

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

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

ขั้นตอน 1 − กลับบิต LSB (Least Significant Bit) ของ b

ขั้นตอน 2 − เปรียบเทียบตัวเลขกับ a และ b ตรวจสอบว่าอยู่ในช่วงหรือไม่

ขั้นตอน 2.1 − ถ้าตัวเลขมากกว่า a ให้กลับบิต LSB อีกครั้ง

ขั้นตอน 2.2 − ถ้าไม่มากกว่า a แล้วตัวเลข = ผลลัพธ์

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

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

วิธีแก้ −

ขั้นตอน 1 − b = 8 (1000) การกลับบิต LSB ซึ่งเป็น 1 ตัวเดียวในตัวเลข ตัวเลขกลายเป็น 0000 คือ 0

ขั้นตอน 2 − 0 น้อยกว่า 3 ดังนั้น 0 คือผลลัพธ์

ตัวอย่างโปรแกรม

#include <stdio.h>
int main() {
    long a, b;
    a = 3; b = 8;
    do {
        b -= (b & -b);
    } while(a < b);
    printf("%li", b);
}