資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢最小的數字 n，使得 n XOR n+1 等於給定的 k
假設我們有一個正數 k。我們需要找到一個正數 n，使得 n 和 n+1 的異或結果等於 k。因此，如果 k = 7 (111)，則輸出將為 3。因為 3 (011) 和 3 + 1 = 4 (100)，所以 011 XOR 100 = 111 (7)
有兩種可能的情況。考慮 n 是偶數。n 的最後一位為 0。那麼 n + 1 的最後一位為 1。其餘位相同。因此，當 n 為奇數時，異或結果為 1，最後一位為 1，而 n + 1 的最後一位為 0。但在這種情況下，由於進位，更多位會發生差異。進位會一直向左傳播，直到我們得到第一個為 0 的位。因此，n XOR n + 1 將為 2^i -1，其中 i 是從左起 n 中第一個 0 位的位置。因此，我們可以說，如果 k 的形式為 2^i – 1，則答案將為 k/2。
示例
#include<iostream>
using namespace std;
int findNValue(int k) {
if (k == 1)
return 2;
if (((k + 1) & k) == 0)
return k / 2;
return -1;
}
int main() {
int k = 15;
cout << "The value of n is: " << findNValue(k);
}輸出
The value of n is: 7
更新於: 2019年12月18日
215 次檢視
廣告