எண் நிரப்பு லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது ஆப்பிள்
பிட் கையாளுதல் பிட்ஸ் கிளவுட்ரா

சிக்கல் அறிக்கை

இந்த சிக்கலில், எங்களுக்கு ஒரு தசம எண் வழங்கப்படுகிறது. அதைக் கண்டுபிடிப்பதே குறிக்கோள் நிறைவுடன்.

உதாரணமாக

N = 15
0
N = 5
2

எண் நிரப்பு லீட்கோட் தீர்வு

அணுகுமுறை (பிட் பிட் புரட்டுகிறது)

நாம் ஒவ்வொன்றையும் புரட்டலாம் பிட் அதன் நிரப்பு பெற முழு எண் 'N' இல். முக்கியமான பகுதி, நாங்கள் முடியாது அதன் 32 பிட்கள் அனைத்தையும் புரட்டவும். அது அதன் பைனரி 1 இன் நிரப்புக்கு வழிவகுக்கும். எல்.எஸ்.பியிலிருந்து தொடங்கி எண்ணில் இடதுபுறம் அமைக்கப்பட்ட பிட் வரை மட்டுமே நாம் புரட்ட வேண்டும். கொடுக்கப்பட்ட எண்ணை N ஐ 2 ஆல் வகுப்பதன் மூலம் பூஜ்ஜியமாகிவிடும் வரை நாம் அதை அடைய முடியும். ஒவ்வொரு மறு செய்கையிலும், நாம் தொடர்புடைய பிட்டை புரட்டலாம்.

எண் நிரப்பு லீட்கோட் தீர்வை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int todo = num , i = 0;
    while(todo > 0) {
        num ^= (1 << i);
        todo >>= 1;
        ++i;
    }
    return num;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

ஜாவா திட்டம்

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int todo = num , i = 0;
        while(todo > 0) {
            num ^= (1 << i);
            todo >>= 1;
            ++i;
        }
        return num;
    }
}
0

எண் நிரப்பு லீட்கோட் தீர்வின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (log2N), அங்கு N = கொடுக்கப்பட்ட முழு எண். கொடுக்கப்பட்ட எண்ணிக்கையில் உள்ள பிட்களின் எண்ணிக்கையை விட பல மடங்கு மீண்டும் செய்கிறோம்.

விண்வெளி சிக்கலானது 

ஓ (1), நாம் நிலையான நினைவகத்தை மட்டுமே பயன்படுத்துகிறோம்.

அணுகுமுறை (உகந்ததாக)

உகந்த அணுகுமுறை எதையும் பயன்படுத்தக்கூடாது கிளைத்தல் குறியீட்டில். அதாவது, எந்த சுழல்களும் இல்லாமல் குறியீட்டை தீர்க்க, அல்லது அடிப்படையில், எந்தவொரு கிளை அறிவுறுத்தலும் இல்லாமல். இந்த அணுகுமுறையில், முதலில் ஒரு பைனரி முகமூடியைக் காணலாம் அனைத்து பிட்களும் அமைக்கப்பட்டன, தொடங்கி '0 வது' பிட் செய்ய இடதுபுறம் அமைக்கப்பட்ட பிட் கொடுக்கப்பட்ட எண்ணில், பின்னர் அதை XOR செய்யுங்கள். இது எங்களுக்கு தேவையான நிரப்புதலை வழங்கும்.

N க்கு தேவையான பைனரி முகமூடியைக் கண்டுபிடிக்க, நாம் பிட்வைஸ் அல்லது கொடுக்கப்பட்ட எண்ணை N >> 1, N >> 2, N >> 4,… N >> 16, எங்கே N >> k = வலதுபுறம் N ஆல் k இடங்கள். இந்த முறையால், மிக முக்கியமான பிட் (இடதுபுற பிட்) க்குப் பிறகு அனைத்து பிட்களையும் அமைத்து தேவையான முகமூடியை உருவாக்குவோம்.

எண் நிரப்பு லீட்கோட் தீர்வை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

ஜாவா திட்டம்

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        return num ^ mask;
    }
}
0

எண் நிரப்பு லீட்கோட் தீர்வின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (1), பிட்வைஸ் பைனரி செயல்பாடுகள் மிக வேகமாக இருப்பதால், செயல்பாடுகள் எடுக்கும் ஓ (log2N), 32-பிட் முழு எண்களுக்கு நேர சிக்கலானது நிலையானது.

விண்வெளி சிக்கலானது 

ஓ (1), நாம் நிலையான நினைவக இடத்தை மட்டுமே பயன்படுத்துகிறோம்.