algorithm - कहत - व्हाट इस बाइट




1 बिट की समान संख्या के साथ अगले छोटी संख्या को खोजने के लिए कुशल तरीके से (4)

मैं इस प्रश्न पर काम कर रहा हूं और एक समाधान के साथ आया हूं (एक या दो शर्त हो सकती है), लेकिन यह सुनिश्चित नहीं है कि यह सही तरीके से किया जाए और दो छोरों का उपयोग करने के लिए इसे बोझिल हो और सुनिश्चित न हो कि यह यह करने का कारगर तरीका है यह महान होगा अगर किसी को भी यह करने के लिए कुछ अच्छी चाल है या किसी भी बेहतर दृष्टिकोण का स्वागत किया जाएगा :)। (भाषा बाधा नहीं है)

मेरा एल्गोरिदम:

  • सबसे पहले नंबर में '0' एलएसबी बिट मिला
  • फिर अगले सेट बिट का पता लगाएं जो कि '0' बिट के बगल में है
  • '0' बिट को 1 और '1' बिट को '0' में ढूंढने वाले को बदलें
  • जो संख्या आपको मिलेगी वह अगले छोटी है
  • यदि सभी बिट सेट हो गए हैं तो आपके पास कोई भी संख्या नहीं है जो कि '1' बिट्स की एक ही संख्या के साथ अगले छोटी है
void nextSmaller(int number) {
    int firstZeroBitHelper = 1, nextOneBitHelper;
    while (firstZeroBitHelper < number) {
        // when we find first lsb zero bit we'll stop
        bool bit = number & firstZeroBitHelper;
        if (bit == false)
            break;
        firstZeroBitHelper = firstZeroBitHelper << 1;
    }

    if (firstZeroBitHelper >= number) {
        cout << "No minimum number exists" << endl;
        return;
    }

    nextOneBitHelper = firstZeroBitHelper;
    nextOneBitHelper = nextOneBitHelper << 1;

    while (nextOneBitHelper < number) {
        // when we get '1' after the previous zero we stop
        bool bit = number & nextOneBitHelper;
        if (bit == true)
            break;
        nextOneBitHelper = nextOneBitHelper << 1;
    }

    // change the first zero to 1
    number = number | firstZeroBitHelper;
    // change the next set bit to zero
    number = number & ~nextOneBitHelper;

    cout << number << endl;
}

आपके द्वारा वर्णित एल्गोरिदम बिल्कुल सही नहीं है; यह सब कुछ ठीक एक विस्तार के अलावा करता है आपके एल्गोरिथम के बीच में पाया गया कोई भी द्विआधारी संख्या निम्न रूप है:

xxxxx...10000...1111...
         ---n---// f // 

यहाँ xxx... मनमानी बिट्स हैं, और लगातार शून्य और संख्याओं की संख्या पहले firstZeroBitHelper और nextOneBitHelper ( f एंड n ) द्वारा निर्धारित की जाती है।

अब आपको इस नंबर को सेट बिट्स की एक ही संख्या में छोड़ना होगा, जो जरूरी है कि 1 से 0 तक का सबसे महत्वपूर्ण मुड़ता है:

xxxxx...0????...????...
         -----n+f------ 

ध्यान दें कि बिट्स के लिए कोई भी मान ??? मूल संख्या की तुलना में नया नंबर कम करता है, और आप वास्तव में इन बिट्स को चुनना चाहते हैं, जिसके फलस्वरूप संख्या में अधिकतम मूल्य है:

xxxxx...011111...0000...
         ---f+1--//n-1// 

तो आपको सिर्फ 2 बिट्स को फ्लिप नहीं करना है, लेकिन f+2 बिट्स ( 1 से 0 से एक बिट और 0 से f+1 अन्य के लिए f+1 अन्य)।

ऐसा करने का एक तरीका निम्नानुसार है

पहले सभी प्रासंगिक बिट बंद करें:

number &= ~nextOneBitHelper;
number &= ~(nextOneBitHelper - 1);

अब आवश्यक बिट्स को चालू करें, एमएसबी से शुरू करें:

nextOneBitHelper >>= 1;
while (firstZeroBitHelper != 0)
{
    number |= nextOneBitHelper;
    nextOneBitHelper >>= 1;
    firstZeroBitHelper >>= 1;
}

लूप के बिना ऊपर वर्णित बिट टिमडलिंग को लागू करना संभव है; इसके लिए आपको n और f गणना करने की आवश्यकता होगी ऐसा करने के बाद:

unsigned mask = (1 << (f + 1)) - 1; // has f+1 bits set to 1
mask <<= n - 1; // now has these bits at correct positions
number |= mask; // now the number has these bits set

ऊपर जा रहे हैं:

  • संख्या में "01" के सबसे ऊपरी भाग की खोज करें और इसे "10" बनाएं
  • सभी निम्नलिखित 1-बिट को जितना संभव हो उतना सही समझाओ।

नीचे जा रहे हैं:

  • नंबर में "10" की सबसे ऊपरी आर्टिकल खोजें और इसे "01" बनाएं
  • सभी निम्नलिखित 1-बिट्स को वाम-औचित्य दें (यानी कुछ भी मत करें यदि आप अभी सेट किए गए बिट पहले से ही 1 के बाद से चल रहे हैं)

नीचे के मामले को स्पष्ट करने के लिए एक उदाहरण:

  • 225 = 0 बी 11 10 0001
  • स्वैप: 0b11 01 000 1
  • वाम-औचित्य: 0b1101 1 000 = 216

मैं ऊपर की ओर ऊपर जाने के मामले की व्याख्या करता हूं, क्योंकि यह मेरे लिए कम मुश्किल लगता है हम कम से कम-महत्वपूर्ण स्थिति खोजना चाहते हैं, जहां हम एक 1-बिट एक स्थान को छोड़ सकते हैं (दूसरे शब्दों में, सहीतम 0 जो उसके दाहिनी ओर 1 है)। यह स्पष्ट होना चाहिए कि यह सहीतम बिट है जिसे हम संभवत: सेट कर सकते हैं, क्योंकि हमें प्रत्येक सेट के लिए कहीं और थोड़ा साफ़ करने की आवश्यकता है, और हमें सेट की गई बिट के दावों को कहीं और थोड़ा साफ़ करना होगा , अन्यथा संख्या बड़ा होने के बजाय छोटे हो जाएगी

अब जब हमने इसे थोड़ा सेट किया है, हम एक बिट (सेट बिट्स की कुल संख्या को पुनर्स्थापित करने के लिए) को साफ़ करना चाहते हैं, और शेष बिट्स को फिर से फेर लेना ताकि संख्या जितनी छोटा हो सके (यह इससे अगले सबसे बड़ी संख्या को बनाता है सेट बिट्स की इसी संख्या) हम जिसको हम सेट करते हैं, उसके दाएं हिस्से को थोड़ा साफ़ कर सकते हैं, और हम किसी भी शेष 1-बिट को संभवतः यथासंभव धक्का बिना हमारी मूल संख्या से नीचे जाने के डर के ऊपर धक्का दे सकते हैं, क्योंकि सभी कम महत्त्वपूर्ण बिट्स एक साथ अभी भी जोड़ते हैं एक बिट से कम हम सिर्फ सेट

अगले उच्चतर के बजाय अगले कम संख्या का पता लगाना मूल रूप से वही है, सिवाय इसके कि हम सहीतम स्थिति की तलाश कर रहे हैं जहां हम एक सेट बिट को एक स्थान पर स्थानांतरित कर सकते हैं, और ऐसा करने के बाद हम सभी कम महत्त्वपूर्ण बिट्स को स्थानांतरित करना चाहते हैं जितना संभव हो उतना छोड़ा नहीं

ऐसा लगता है कि दूसरों को इस अच्छी तरह के बिट-ट्विडिंग संस्करण मिल गए हैं, लेकिन मैं देखना चाहता हूं कि क्या मैं एल्गोरिदम के तार्किक / गणितीय पक्ष का एक अच्छा स्पष्टीकरण दे सकता हूं।


#include <iostream>

bool AlmostdivBy2(int num) {
    return (-~num & (num)) == 0;
}

void toggleright(int &num) {
    int t;
    for (t = -1; num & 1; t++)
        num >>= 1;
    ++num = (num << t) | ~-(1 << t);
}

void toggleleft(int &num) {
    while (~num & 1)
        num >>= 1; //Simply keep chopping off zeros
    //~num & 1 checks if the number is even
    //Even numbers have a zero at bit at the rightmost spot
}

int main() {

    int value;
    std::cin >> value;
    if (!AlmostdivBy2(value)) {
        (~value & 1) ? toggleleft(value) : toggleright(value);
    }
    std::cout << value << "\n";
    return 0;
}

मुझे लगता है कि मुझे इस पर सोचा होगा, लेकिन यह मेरा स्पष्टीकरण है:

  • अगर संख्या 2, 2, 1, 3, 7, 15, 31, जैसे मूल्यों की शक्ति होने के करीब है ..., तो उसके तुलना में कोई भी मूल्य छोटा नहीं है जो उनके द्विआधारी प्रतिनिधित्व में समान संख्या में हो सकता है। इसलिए हम इन नंबरों के बारे में चिंता नहीं करते।

  • यदि संख्या भी है, तो यह एक और आसान फिक्स है, हम सिर्फ शून्य से अंक निकालते रहेंगे जब तक कि संख्या अजीब न हो

  • विषम संख्याएं सबसे अधिक चुनौती प्रस्तुत करती हैं, यही वजह है कि यह रिकर्सिव है। सबसे पहले आपको नंबर के दायरे से शुरू होने वाला पहला शून्य बिट मिलना पड़ा। जब यह पाया जाता है, तो आप उस नंबर पर एक जोड़ते हैं जो कि आखिरी बिट 1 को बदल देगा। जैसा कि पुनरावर्तन खोलता है आप बिट्स को बाईं ओर स्थानांतरित करते हैं और एक जोड़ते हैं। जब यह किया जाता है, तो आपके पास अगले छोटी से छोटी है

आशा है कि मैं आपको भ्रमित नहीं करता था

संपादित करें

इसके बारे में और अधिक काम किया है और यह toggleright का एक गैर पुनरावर्ती संस्करण है

void toggleright(int &num) {    
    int t = 1;
    while ( (num >>= 1) & 1 && t++ );
    num = (-~num << ~-t) | ~-(1 << t);    
}

एनाटॉलीज ने आपके एल्गोरिदम को बहुत अच्छी तरह से कवर किया है, लेकिन एक अधिक कुशल समाधान है।

आप गोस्पर के हैक का एक चतुर अनुभव के साथ उपयोग कर सकते हैं कि यदि आप बिट्स को चारों ओर फ्लिप करते हैं, तो गोस्पर मूल्यों को अवरोही क्रम में उत्पन्न करता है

इस छद्म कोशिका की तरह कुछ काम करेगा:

let k := number
let n := num bits in k (log base 2)
k = k ^ ((1 << n) - 1)
k = gosper(k)
k = k ^ ((1 << n) - 1)
return k

यह आपको एक अच्छा ओ (1) देता है (या ओ (लॉग एन) अगर आप एक्सरे को रैखिक समय मानते हैं) एल्गोरिथम। :)

कुछ मामलों में आपको विचार करना होगा, जैसे कि कुछ x लिए k=2^x-1 , लेकिन यह पकड़ने में काफी आसान है।





binary