양수 k가 있다고 가정합니다. n과 n+1의 XOR이 k와 같도록 양수 n을 찾아야 합니다. 따라서 k =7(111)이면 출력은 3이 됩니다. 3(011) 및 3 + 1 =4(100)이므로 011 XOR 100 =111(7)
두 가지 가능한 경우가 있습니다. n이 짝수임을 고려하십시오. n의 마지막 비트 =0. 그런 다음 n의 마지막 비트 + 1 =1. 나머지 비트는 동일합니다. 따라서 XOR은 1이 됩니다. n이 홀수일 때 마지막 비트는 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