XOR สูงสุดโดยใช้ตัวเลข K ตั้งแต่ 1 ถึง n ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มบวกสองจำนวน n และ k งานของเราคือการหาค่า xor สูงสุดระหว่าง 1 ถึง n โดยใช้ตัวเลข X สูงสุด

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

ป้อนข้อมูล − n =5, k =2

ผลผลิต − 7

คำอธิบาย −

elements till 5 is 1, 2, 3, 4, 5
Selecting all XOR pairs:
1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4
2^3 = 4, 2^4 = 6, 2^5 = 7
3^4 = 7, 3^5 = 6
4^5 = 1
The maximum here is 7.

ในการแก้ปัญหานี้ สามารถหาค่า XOR สูงสุดสำหรับชุดค่าผสมของตัวเลขใดๆ ก็ได้ เมื่อตั้งค่าบิตของตัวเลขทั้งหมดแล้ว

ดังนั้น หากตัวเลขคือ 5 เลขฐานสองของมันคือ 101 XOR สูงสุดจะเป็น 111 เช่น 7.

แต่ถ้าจำนวนองค์ประกอบที่จะใช้สำหรับ XOR สูงสุดคือ 1 ดังนั้น XOR สูงสุดจะเป็น 1 มิฉะนั้นจะพบ XOR สูงสุดโดยการตั้งค่าบิตทั้งหมด

ตัวอย่าง

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

#include <iostream>
using namespace std;
int maxXor(int n, int k) {
   if (k == 1)
      return n;
   int result = 1;
   while (result <= n)
      result <<= 1;
   return result - 1;
}
int main() {
   int n = 5, k = 2;
   cout<<"The maximum XOR of "<<k<<" numbers from 1 to"<<n<<" is "<<maxXor(n, k);
   return 0;
}

ผลลัพธ์

The maximum XOR of 2 numbers from 1 to 5 is 7