Решење са шифром Хамминг Дистанце


Ниво тешкоће Лако
Често питани у адобе амазонка фацебоок
Бит манипулација Битс

Изјава о проблему

У овом проблему добили смо две целобројне вредности, А и Б, а циљ је пронаћи растојање хамминга између датих целих бројева. Цели бројеви су већи од / једнаки и мање од 231   

Пример

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

Решење са шифром Хамминг Дистанце

Приступ (Бројање по бит)

Прва ствар која је врло јасна је да пошто морамо да пронађемо број бита где су одговарајуће вредности битова у дата два броја различите, треба да урадимо бит-КСОР датих целих бројева. Резултати које ће КСОР произвести у појединачном положају бита били би '1' ако је битови у две целобројне вредности на том положају били су различити. У супротном, КСОР ће на тој позицији произвести '0'.

Сад кад смо извели овај део, преостало је само ефикасно проналажење броја битова који су сет (вредност бита = '1') у битном КСОР датог целог броја. Да бисмо израчунали ову вредност, вршимо петљу за сваки бит (од 0 до 30) и проверите да ли је постављено у КСОР вредност или није.

Алгоритам

  1. Спремите битни КСОР два цела броја у променљиву - кор_
  2. Инитиализе цнт = 0 за чување резултата
  3. За сваки И = КСНУМКС   и <31:
    • Ако јеИТХ'бит је постављен кор_
      • Повећање цнт: цнт ++ 
    • Повећање i
  4. повратак цнт

Примена решења Хамет Дистанце Леетцоде решења

Програм Ц ++

#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) како користимо стални меморијски простор.

Приступ (ефикасно бројање битова - Керниганов алгоритам)

Први кораци остају исти, а то је да се сазна битни КСОР тео задатих бројева. Међутим, број постављених битова у њиховом КСОР-у рачунамо ефикасно користећи Кернигхан-ов алгоритам, који је заснован на идеји:

Када наступамо 'у битовима &'операција између целог броја 'ја' 'и - 1', његов најтачнији десни бит је унсет.

Пратимо горњу идеју кроз пример. Размотримо Н = 36 (100100). Сада, ако '&' то направимо са Н - 1, добили бисмо:

Н & (Н - 1) = (36 & 35) = (100100 & 100011) = (100000) што јасно поништава најдеснији бит (на положају 2 с десне стране). Слично томе, можемо даље написати:

Н & (Н - 1) = (32 & 31) = (100000 & 011111) = 000000 што поново поништава крајњи десни постављени бит на положају 5 с десне стране. Процес се не може наставити даље јер је цео број Н постао нула.

Ова лепа идеја показала се веома корисном за бројати постављене битове у целом броју, јер само треба само изводити колико пута постоје постављени битови у датом целом броју.

Алгоритам

  1. Спремите битни КСОР два цела броја у променљиву - кор_
  2. Инитиалисе цнт = 0 за чување резултата
  3. Док кор_ је већи од 0:
    1. Повећање цнт: цнт ++
    2. сет кор_ = кор_ & (кор_ - 1)
  4. повратак цнт

Примена решења Хамет Дистанце Леетцоде решења

Програм Ц ++

#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) како користимо стални меморијски простор.