C++ में बिट्स को पुनर्व्यवस्थित करके संख्या को अधिकतम करना

समस्या कथन

एक अनसाइन्ड संख्या दी गई है, दी गई अनसाइन्ड संख्या के बिट्स का उपयोग करके बनाई जा सकने वाली अधिकतम संख्या ढूंढें।

यदि इनपुट संख्या 8 है तो इसका बाइनरी प्रतिनिधित्व है:

00000000000000000000000000001000

इसे अधिकतम करने के लिए MSB को 1 पर सेट करें। तब संख्या 2147483648 बन जाती है जिसका बाइनरी प्रतिनिधित्व है:

10000000000000000000000000000000

एल्गोरिदम

1. दी गई संख्या के बाइनरी प्रतिनिधित्व में सेट बिट्स की संख्या गिनें।
2. n कम से कम सार्थक सेट बिट्स वाली संख्या ढूंढें।
3. संख्या को (32 - n) से बाएं शिफ्ट करें।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

unsigned getMaxNumber(unsigned num) {
    int n = __builtin_popcount(num);
    if (n == 32) {
        return num;
    }
    unsigned result = (1 << n) - 1;
    return (result << (32 - n));
}

int main() {
    unsigned n = 8;
    cout << "Maximum number = " << getMaxNumber(n) << endl;
    return 0;
}

आउटपुट

Maximum number = 2147483648