Tổng bằng nhau và XOR trong C ++

Trong bài toán này, chúng ta được cung cấp một số nguyên n. Nhiệm vụ của chúng ta là tạo một chương trình để tìm số lượng các số nguyên từ i =0 đến n, trong đó tổng bằng XOR tức là (n + i) =(n ^ i).

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: n =4

Đầu ra: 4

Giải thích:

Xem xét tất cả các giá trị của i từ 0 đến n,

i =0, 4 + 0 =4, 4 ^ 0 =4
i =1, 4 + 1 =5, 4 ^ 1 =5
i =2, 4 + 2 =6, 4 ^ 2 =6
i =3, 4 + 3 =7, 4 ^ 3 =7
i =4, 4 + 4 =8, 4 ^ 4 =0
Đếm =4

Phương pháp tiếp cận giải pháp:

Một giải pháp đơn giản là tìm các giá trị của tổng n và i và x hoặc của n và i. So sánh cả hai giá trị này và sau đó đếm các giá trị mà chúng bằng nhau.

Thuật toán:

Bước 1: Vòng lặp cho tất cả các giá trị từ i =0 đến n.

Bước 1.1: Tìm giá trị của (n + i).

Bước 1.2: Tìm giá trị của (n ^ i).

Bước 1.3: so sánh các giá trị được tìm thấy trong bước 1.1 và 1.2.
Bước 1.4: Nếu chúng bằng nhau, hãy tăng số lượng.

Bước 2: In số lượng giá trị.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra -

The count of integers with equal sum and XOR is 2

Phương pháp này tốt nhưng chúng có thể là một giải pháp tốt hơn cho vấn đề, đó là sử dụng thực tế là

Nếu n ^ i =n + i , sau đó n &i =0 .

Nếu giá trị của n &i =0, thì chúng ta cần hai số có các bit đặt và không đặt đối nhau. Và chúng ta cần đếm các giá trị như vậy. Đây là một chương trình để làm điều đó,

Ví dụ

#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;
}

Đầu ra -

The count of integers with equal sum and XOR is 2