ในปัญหานี้ เราได้รับจำนวนเต็ม X หน้าที่ของเราคือค้นหาจำนวนขั้นตอนทั้งหมดที่ใช้ในการแปลงจาก 0 เป็น X
การแปลงที่ถูกต้อง − หนึ่งขั้นตอนจะถูกนับเมื่อการแปลงหนึ่งเกิดขึ้นจาก A ถึง B เงื่อนไขสำหรับการแปลงที่จะเกิดขึ้นคือ A !=B และ A &B =A (&คือระดับบิต AND) ดังนั้น 1 ขั้นตอนคือการแปลงจาก A เป็น B และเราต้องสร้างโปรแกรมที่จะนับจำนวนขั้นตอนสูงสุดในการแปลง 0 เป็น X
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − X =7
ผลผลิต − 3
คำอธิบาย −
เราต้องเปลี่ยนจาก 0 เป็น 7
Steps taken will be Step1: 0(00) to 1(01) , 0!= 1 and 0&1 = 0, transform 00=>01 Step2: 1(001) to 3(011) , 1!= 3 and 1&3 = 1, transform 001=>011 Step3: 3(0011) to 7(0111) , 3!= 7 and 3&7 = 3, tranform 0011=>0111.
เพื่อแก้ปัญหานี้ เราจะนับจำนวนชุดบิตใน X ซึ่งจะให้การแปลงสูงสุดจาก 0 เป็น X
เนื่องจากเราต้องการการแปลงสูงสุด เราจึงต้องดำเนินการทีละขั้นตอนสำหรับแต่ละชุดบิต (บิตที่มีค่า 1) การแปลงบิตแล้วบิตจะให้ขั้นตอนสูงสุดในการแปลงจาก 0 เป็น X
ในการแปลงจาก A เป็น B เซตบิตทั้งหมดของ A ควรตั้งค่าเป็น B แต่ไม่จำเป็นต้องย้อนกลับ ดังนั้น การแปลงขั้นต่ำอาจเป็น 1 เนื่องจากไม่มีเซ็ตบิตใน 0 ซึ่งทำให้การแปลงโดยตรงน้อยที่สุด
ดังที่เราเห็นในตัวอย่างแล้ว การแปลงเลขฐานสองของตัวเลขและ ANDs ระดับบิตของพวกมัน
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา -
//โปรแกรมค้นหาขั้นตอนสูงสุดในการแปลง 0 เป็น X ด้วยระดับบิต AND ใน C++
#include <bits/stdc++.h>
using namespace std;
int maxtransformation(int x){
int steps = 0;
// counting number of bits
while (x) {
steps += x & 1;
x >>= 1;
}
return steps;
}
int main(){
int x = 7;
cout<<"The maximum number of steps to transform 0 to "<<x<<" with bitwise AND are "<<maxtransformation(x);
return 0;
} ผลลัพธ์
The maximum number of steps to transform 0 to 7 with bitwise AND are 3
