資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中滿足(n XOR x) = (n – x)條件的x的值的數量(x <= n)
給定一個輸入數字n。目標是找到滿足條件(n xor x)=(n-x)的x值。並且x的範圍在[0,n]之間。
讓我們透過例子來理解
輸入 − n=10
輸出 − 滿足(n XOR x) = (n – x)條件的x的值的數量(x <= n)為4
解釋 − 滿足10 xor x = 10-x的x值為0, 2, 8和10。
輸入 − n=15
輸出 − 滿足(n XOR x) = (n – x)條件的x的值的數量(x <= n)為16
解釋 − 滿足15 xor x = 15-x的x值為0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14和15。
下面程式中使用的方法如下
我們將使用兩種方法。第一種是使用for迴圈的樸素方法。從i=0遍歷到i<=n，將i作為可能的x值。現在檢查(n - i == (n ^ i) //xor)是否成立。如果成立，則計數器加1。
將整數變數n作為輸入。
函式unique_pair(int arr[], int size)接受陣列及其長度並返回滿足條件(arr[i],arr[j])(其中i
將計數器的初始值設定為0。
建立一個包含整數對的集合'se'。(set<pair<int, int>> se)
使用兩個for迴圈遍歷arr[]。從i=0到i
對於每一對(總是i
在兩個for迴圈結束後，更新count=se.size()。
現在count包含'se'中對的數量。(所有都是唯一的)。
返回count作為結果。
高效方法
在這種方法中，我們將首先將n轉換為其二進位制等價形式。我們知道：
1 xor 0 = 1-0
1 xor 1 = 1-1
但是
0 xor 0 ≠ 0-1
0 xor 1 ≠ 0-1
因此，對於n的二進位制表示中的每一個1，都有2種情況。對於n的二進位制表示中p個1，將有2p個值滿足條件。
索引i。然後將這些單獨的計數相加以得到總的唯一對數。
將整數變數n作為輸入。
函式unique_pair(int arr[], int size)接受陣列及其長度並返回滿足條件(arr[i],arr[j])(其中i
將計數器的初始值設定為0。
使用number=bitset<8>(n).to_string();將n轉換為字串。
令length=number.length()。
使用for迴圈從索引i=0遍歷到i
將count=pow(2,count)設定為最終的x值。
返回count作為結果。
示例（樸素方法）
#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
int count = 0;
for (int i = 0; i <= n; i++){
if (n - i == (n ^ i)){
count++;
}
}
return count;
}
int main(){
int n = 25;
cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of values of x <= n for which (n XOR x) = (n – x) are: 8
示例（高效方法）
#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
int count = 0;
string number = bitset<8>(n).to_string();
int length = number.length();
for (int i = 0; i < length; i++){
if (number.at(i) == '1')
{ count++; }
}
count = (int)pow(2, count);
return count;
}
int main(){
int n = 25;
cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of values of x <= n for which (n XOR x) = (n – x) are: 8
298 次瀏覽
