सबसे छोटी संख्या n ज्ञात कीजिए कि n XOR n+1 C++ में दिए गए k के बराबर है

मान लीजिए कि हमारे पास एक सकारात्मक संख्या k है। हमें धनात्मक संख्या n ज्ञात करनी है, ताकि n और n+1 का XOR, k के समान हो। तो अगर 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