ในปัญหานี้ เราได้รับค่าจำนวนเต็มสองค่า a และ b และหน้าที่ของเราคือค้นหา ระดับบิตและ (&) ของช่วงจาก a ถึง b . ซึ่งหมายความว่าเราจะต้องหาค่าของ a &a+1 &a+2 &… b-1 &b
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − a =3 , b =8
ผลผลิต − 0
คำอธิบาย − 3 &4 &5 &6 &7 &8 =0
ในการแก้ปัญหา วิธีแก้ไขง่ายๆ คือเริ่มจาก a และค้นหาระดับบิตและตัวเลขทั้งหมดโดยเพิ่มจากหนึ่งเป็น b
โซลูชันที่มีประสิทธิภาพยิ่งขึ้น
นี่เป็นวิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้น ซึ่งสามารถทำได้โดยใช้ −
ขั้นที่ 1 − พลิก LSB ของ b.
ขั้นที่ 2 − เปรียบเทียบตัวเลขกับ a และ b ตรวจสอบว่าอยู่ในช่วงหรือไม่
ขั้นตอนที่ 2.1 − หากตัวเลขมากกว่าการพลิกกลับ LSB จะได้รับ
ขั้นตอนที่ 2.2 − ถ้าไม่เกิน a แล้ว number =ผลลัพธ์
ตอนนี้ ให้ 's ดูอัลกอริธึมด้านบนในการทำงาน -
ตัวอย่าง − a =3 และ b =8
วิธีแก้ปัญหา −
ขั้นที่ 1 − b =8 (1000) พลิก LSB ซึ่งเป็นตัวเดียวในตัวเลข ตัวเลขกลายเป็น 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);
} ผลลัพธ์
0
