මිටීමේ දුර ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් ෆේස්බුක්
බිට් හැසිරවීම බිටු

ගැටළු ප්රකාශය

මෙම ගැටළුවේදී අපට A සහ ​​B යන පූර්ණ සංඛ්‍යා දෙකක් ලබා දී ඇති අතර ඉලක්කය සොයා ගැනීමයි මිටිය දුර දී ඇති පූර්ණ සංඛ්‍යා අතර. නිඛිල විශාල / සමාන වේ සහ අඩු 231   

උදාහරණයක්

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

මිටීමේ දුර ලීට්කෝඩ් විසඳුම

ප්‍රවේශය (බිට් මගින් බිට් ගණන් කිරීම)

ඉතා පැහැදිලිව පෙනෙන පළමු දෙය නම් අප සංඛ්‍යාව සොයා ගත යුතු බැවිනි ටිකක් දී ඇති සංඛ්‍යා දෙකෙහි අනුරූප බිට් අගයන් වෙනස් වන විට, අප විසින් ලබා දී ඇති පූර්ණ සංඛ්‍යා වල bitwise-XOR කළ යුතුය. XOR තනි බිට් ස්ථානයක නිපදවන ප්‍රති results ල '1' නම් එම ස්ථානයේ ඇති පූර්ණ සංඛ්‍යා දෙකේ බිටු වෙනස් විය. එසේ නොමැතිනම්, XOR විසින් එම ස්ථානයේ '0' නිපදවනු ඇත.

දැන් අපි මෙම කොටස අඩු කර ඇති අතර, පසු විපරම් කිරීම සඳහා ඉතිරිව ඇත්තේ බිටු ගණන කාර්යක්ෂමව සොයා ගැනීමයි. කට්ටලයක් (bit value = '1') දී ඇති පූර්ණ සංඛ්‍යා වල බිට්වේස් XOR හි. මෙම අගය ගණනය කිරීම සඳහා, අපි සෑම බිට් එකකටම (සිට 0 දක්වා 30) සහ XOR අගයෙන් සකසා තිබේද නැද්ද යන්න පරීක්ෂා කරන්න.

ඇල්ගොරිතම

  1. පූර්ණ සංඛ්‍යා දෙකේ බිට්වේස් XOR විචල්‍යයක ගබඩා කරන්න - xor_
  2. ආරම්භ කරන්න cnt ප්‍රති 0 ලය ගබඩා කිරීමට = XNUMX
  3. සෑම කෙනෙකුටම i = 0 සහ i <31:
    • නම් 'බිට් එක සකසා ඇත xor_
      • වැඩි කිරීම cnt: cnt ++ 
    • වැඩි කිරීම i
  4. ආපසු cnt

හැමිං දුර ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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 සොයා ගැනීමයි. කෙසේ වෙතත්, අදහස මත පදනම් වූ කර්නිගන්ගේ ඇල්ගොරිතම භාවිතා කරමින් අපි ඔවුන්ගේ XOR හි ඇති කට්ටල ගණන කාර්යක්ෂමව ගණනය කරමු:

අපි රඟපාන විට 'bitwise &පූර්ණ සංඛ්‍යාවක් අතර ක්‍රියාකාරිත්වය 'මම' සහ 'i - 1', එහි නිවැරදිම කට්ටලය වේ සකසා නැත.

උදාහරණයකින් ඉහත අදහස අනුගමනය කරමු. N = 36 (100100) සලකා බලන්න. දැන් අපි එය N - 1 සමඟ '&' කළහොත්, අපට ලැබෙනුයේ:

N & (N - 1) = (36 & 35) = (100100 & 100011) = (100000) පැහැදිලිව සැකසුම් දකුණු කෙළවරේ (දකුණේ 2 ස්ථානයේ) ඒ හා සමානව, අපට තවදුරටත් ලිවිය හැකිය:

N & (N - 1) = (32 & 31) = (100000 & 011111) = 000000 එය නැවත දකුණේ සිට 5 වන ස්ථානයේ ඇති නිවැරදිම කට්ටලය නැවත සකසයි. පූර්ණ සංඛ්‍යා N ශුන්‍ය බවට පත්ව ඇති බැවින් ක්‍රියාවලිය තවදුරටත් කරගෙන යා නොහැක.

මෙම සුන්දර අදහස ඉතා ප්රයෝජනවත් බව ඔප්පු කරයි කට්ටල බිටු ගණන් කරන්න පූර්ණ සංඛ්‍යාවක් තුළ, අපට අවශ්‍ය වන්නේ සාධාරණ ලෙස පමණි iterate තරම් වාරයක් කට්ටල බිටු ඇත දී ඇති පූර්ණ සංඛ්‍යාවක් තුළ.

ඇල්ගොරිතම

  1. පූර්ණ සංඛ්‍යා දෙකේ බිට්වේස් XOR විචල්‍යයක ගබඩා කරන්න - xor_
  2. ආරම්භ කරන්න cnt ප්‍රති 0 ලය ගබඩා කිරීමට = XNUMX
  3. අතර xor_ වඩා විශාලයි 0:
    1. වැඩි කිරීම cnt: cnt ++
    2. xor_ = xor_ & (xor_ - 1) සකසන්න
  4. ආපසු cnt

හැමිං දුර ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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) අපි නිරන්තර මතක අවකාශය භාවිතා කරන නිසා.