የሃሚንግ ርቀት ሌትኮድ መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፌስቡክ
ቢት ማባከን ቢት

የችግሩ መግለጫ

በዚህ ችግር ውስጥ ሁለት እና ሁለገብ ቁጥሮች ይሰጠናል ፣ ሀ እና ቢ ፣ ግቡ ደግሞ መፈለግ ነው የመዶሻ ርቀት በተሰጡት ቁጥሮች መካከል። ኢንቲጀርስ የበለጠ / እኩል ነው እና ያነሰ 231   

ለምሳሌ

First Integer = 5 , Second Integer = 2
3
First Integer = 4 , Second Integer = 5
1

የሃሚንግ ርቀት ሌትኮድ መፍትሔ

አቀራረብ (ቢትን በቢት በመቁጠር)

በጣም ግልፅ የሆነው የመጀመሪያው ነገር ቁጥሮችን መፈለግ ስላለብን ነው ቢት በተጠቀሱት ሁለት ቁጥሮች ውስጥ ያሉት ተጓዳኝ ጥቃቅን እሴቶች የተለያዩ ሲሆኑ ፣ የተሰጡትን ኢንቲጀሮች በጥቂቱ- XOR ማድረግ ያስፈልገናል ፡፡ XOR በግለሰብ ደረጃ አቀማመጥ ውስጥ የሚያወጣው ውጤት ‹1› ይሆናል በዚያ ቦታ ላይ በሁለት ቁጥሮች ውስጥ ያሉ ቢቶች የተለያዩ ነበሩ. ያለበለዚያ XOR በዚያ ቦታ ‹0› ን ያወጣል ፡፡

አሁን ይህንን ክፍል ካወቅን በኋላ የቀረው ብቸኛው ክትትል ቢት ቁጥሮችን በብቃት መፈለግ ብቻ ነው ስብስብ ከተሰጡት ኢንቲጀሮች በትንሹ (ቢት እሴት = '1') ፡፡ ይህንን እሴት ለመቁጠር ለእያንዳንዱ ትንሽ ቀለበት እናደርጋለን (ከ 0 ወደ 30) እና በ XOR እሴት ውስጥ እንደተዘጋጀ ወይም እንዳልሆነ ያረጋግጡ።

አልጎሪዝም

  1. የሁለቱን ኢንቲጀሮች ጥቃቅን በሆነ መልኩ XOR ን በተለዋጭ ውስጥ ያከማቹ - ነፃ_
  2. ያስጀምሩ cnt = 0 ውጤቱን ለማከማቸት
  3. ለያንዳንዱ i = 0 ና i <31:
    • ከሆነ እ.ኤ.አ.ithቢት ገብቷል ነፃ_
      • ጭማሪ cnt: cnt ++ 
    • ጭማሪ i
  4. ተመለስ cnt

የሃሚንግ ርቀት ሌትኮድ መፍትሄ ተግባራዊነት

C ++ ፕሮግራም

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    for(int i = 0 ; i < 31 ; i++){
        if((1 << i) & xor_)
            cnt++;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

የጃቫ ፕሮግራም

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y , cnt = 0;
        for(int i = 0 ; i < 31 ; i++){
            if(((1 << i) & xor_) > 0)
                cnt++;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

የሃሚንግ ርቀት ሌትኮድ መፍትሔ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (1) ግብዓቱ ምንም ይሁን ምን የማያቋርጥ የሥራ ክንዋኔዎችን ስናከናውን ፡፡

የቦታ ውስብስብነት

ኦ (1) የማያቋርጥ የማስታወሻ ቦታ እንደምንጠቀም ፡፡

አቀራረብ (ቢቶችን በብቃት በመቁጠር - የከርኒገን ስልተ-ቀመር)

የመጀመሪያዎቹ እርምጃዎች ተመሳሳይ እንደሆኑ ይቆያሉ ፣ ይህም በቴዎ የተሰጡትን ቁጥሮች በትንሹ XOR ን ለማወቅ ነው። ሆኖም ፣ በሀሳቡ ላይ የተመሠረተውን የ Kernighan አልጎሪዝም በመጠቀም በብቃት በ ‹XOR› ውስጥ የተቀመጡ ቢት ቁጥሮችን እንቆጥራለን-

ስናከናውን 'ትንሽበኢንቲጀር መካከል የሚሰራ 'እኔ''እኔ - 1'፣ ትክክለኛው በጣም የተቀመጠው ትንሽ ነው እንዳልተስተካከለ.

እስቲ ከላይ ያለውን ሀሳብ በምሳሌ እንከተል ፡፡ N = 36 (100100) ን ያስቡ ፡፡ አሁን በ N - 1 ካደረግነው እናገኛለን

N & (N - 1) = (36 & 35) = (100100 & 100011) = (100000) በግልጽ ያልተስተካከለ ትክክለኛው በጣም ትንሽ (ከቀኝ በኩል ባለው አቀማመጥ 2)። በተመሳሳይ ፣ እኛ ተጨማሪ መጻፍ እንችላለን

N & (N - 1) = (32 & 31) = (100000 & 011111) = 000000 ከቀኝ በኩል በአቀማመጥ 5 ላይ በጣም ትክክለኛውን ስብስብ ትንሽ እንደገና ያወጣል ፡፡ ቁጥሩ ኤን ቁጥር ዜሮ ስለ ሆነ ሂደቱ የበለጠ ሊቀጥል አይችልም።

ይህ ቆንጆ ሀሳብ በጣም ጠቃሚ መሆኑን ያረጋግጣል የቁጥር ስብስቦችን ይቁጠሩ በቃ (ኢንቲጀር) ውስጥ ብቻ ያስፈልገናል አሳንስ እንደ ብዙ ጊዜ የተቀመጡ ቢቶች አሉ በተሰጠው ኢንቲጀር

አልጎሪዝም

  1. የሁለቱን ኢንቲጀሮች ጥቃቅን በሆነ መልኩ XOR ን በተለዋጭ ውስጥ ያከማቹ - ነፃ_
  2. የመጀመሪያ ስም cnt = 0 ውጤቱን ለማከማቸት
  3. ቢሆንም ነፃ_ ይበልጣል 0:
    1. ጭማሪ cnt: cnt ++
    2. አዘጋጅ xor_ = xor_ & (xor_ - 1)
  4. ተመለስ cnt

የሃሚንግ ርቀት ሌትኮድ መፍትሄ ተግባራዊነት

C ++ ፕሮግራም

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    while(xor_ > 0){
        xor_ = (xor_ & (xor_ - 1));
        ++cnt;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

የጃቫ ፕሮግራም

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y;
        int cnt = 0;
        while(xor_ > 0){
            xor_ = (xor_ & (xor_ - 1));
            ++cnt;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

የሃሚንግ ርቀት ሌትኮድ መፍትሔ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (1) ግብዓቱ ምንም ይሁን ምን የማያቋርጥ የሥራ ክንዋኔዎችን ስናከናውን ፡፡

የቦታ ውስብስብነት

ኦ (1) የማያቋርጥ የማስታወሻ ቦታ እንደምንጠቀም ፡፡