ผลรวมเท่ากับและ XOR ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็ม n งานของเราคือสร้างโปรแกรมเพื่อหาจำนวนเต็มตั้งแต่ i =0 ถึง n โดยที่ sum เท่ากับ XOR เช่น (n+i) =(n^i)

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

ป้อนข้อมูล: n =4

ผลลัพธ์: 4

คำอธิบาย:

พิจารณาค่าทั้งหมดของ i ตั้งแต่ 0 ถึง n

ผม =0, 4 + 0 =4, 4^0 =4
ผม =1, 4 + 1 =5, 4^1 =5
ผม =2, 4 + 2 =6, 4^2 =6
ผม =3, 4 + 3 =7, 4^3 =7
ผม =4, 4 + 4 =8, 4^4 =0
นับ =4

แนวทางการแก้ปัญหา:

วิธีแก้ไขอย่างง่ายคือการหาค่าของผลรวมของ n และ i และ xor ของ n และ i เปรียบเทียบค่าทั้งสองนี้แล้วนับค่าที่เท่ากัน

อัลกอริทึม:

ขั้นตอนที่ 1: วนซ้ำสำหรับค่าทั้งหมดตั้งแต่ i =0 ถึง n

ขั้นตอนที่ 1.1: หาค่าของ (n + i)

ขั้นตอนที่ 1.2: หาค่าของ (n^i)

ขั้นตอนที่ 1.3: เปรียบเทียบค่าที่พบในขั้นตอนที่ 1.1 และ 1.2
ขั้นตอนที่ 1.4: หากเท่ากันให้เพิ่มจำนวน

ขั้นตอนที่ 2: พิมพ์ นับ ค่า

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;

int main() {
   
   int n = 5;
   int counter = 0;
   for(int i=0; i<=n; i++ )
      if ( (n+i) == (n^i) )
         counter++;
   cout<<"The count of integers with equal sum and XOR is "<<counter;
   return 0;
}

ผลลัพธ์ -

The count of integers with equal sum and XOR is 2

วิธีนี้ดีแต่อาจเป็นวิธีแก้ปัญหาที่ดีกว่า ซึ่งก็คือการใช้ข้อเท็จจริงที่ว่า

ถ้า n^i =n+i จากนั้น n&i =0 .

หากค่าของ n&i =0 สำหรับสิ่งนั้น เราต้องการให้ตัวเลขทั้งสองมีค่าตรงข้ามกับ set และ unset bits และเราจำเป็นต้องนับค่าดังกล่าว นี่คือโปรแกรมที่จะทำ

ตัวอย่าง

#include <iostream>
using namespace std;

int countValuesWithEqualSumXOR(int n) {
   
   int countUnSetBits=0;
   while (n) {
      if ((n & 1) == 0)
         countUnSetBits++;
      n=n>>1;
   }
   return 1 << countUnSetBits;
}

int main()
{
   int n = 6;
   cout<<"The count of integers with equal sum and XOR is "<<countValuesWithEqualSumXOR(n);
   return 0;
}

ผลลัพธ์ -

The count of integers with equal sum and XOR is 2