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

मान लीजिए हमारे पास एक धनात्मक संख्या 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 है। लेकिन इस मामले में, कैरी के कारण अधिक बिट्स भिन्न होते हैं। कैरी तब तक बाएं की ओर प्रसारित होती है जब तक हमें बाएं से n में पहला 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