Решение Leetcode для расстояния Хэмминга


Сложный уровень Легко
Часто спрашивают в саман Амазонка Facebook
Битовые манипуляции Биты

Постановка задачи

В этой задаче нам даны два целых числа, A и B, и цель состоит в том, чтобы найти расстояние Хэмминга между заданными целыми числами. Целые числа больше / равны и меньше чем 231   

Пример

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

Решение Leetcode для расстояния Хэмминга

Подход (счет за битом)

Первое, что предельно ясно, это то, что, поскольку нам нужно найти количество биты где соответствующие битовые значения в данных двух числах различны, нам нужно выполнить побитовое исключающее ИЛИ для заданных целых чисел. Результатом XOR для отдельной битовой позиции будет '1', если биты в двух целых числах в этой позиции были разными. В противном случае XOR выдаст «0» в этой позиции.

Теперь, когда мы определили эту часть, единственное, что осталось сделать, - это эффективно определить количество битов, которые задавать (битовое значение = '1') в побитовой операции XOR заданных целых чисел. Чтобы подсчитать это значение, мы выполняем цикл для каждого бита (начиная с 0 в 30) и проверьте, установлено ли значение XOR или нет.

Алгоритм

  1. Сохраните побитовый XOR двух целых чисел в переменной - xor_
  2. инициализировать CNT = 0 для сохранения результата
  3. Для каждого я = 0 и я <31:
    • Еслий'бит установлен в xor_
      • инкремент cnt: cnt ++ 
    • инкремент i
  4. Возврат CNT

Реализация решения Leetcode с расстоянием Хэмминга

Программа 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;
}

Программа Java

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

Анализ сложности решения Leetcode с расстоянием Хэмминга

Сложность времени

O (1) поскольку мы выполняем постоянное количество операций независимо от ввода.

Пространство сложности

O (1) поскольку мы используем постоянное пространство памяти.

Подход (эффективный подсчет бит - алгоритм Кернигана)

Первые шаги остаются прежними, а именно - узнать побитовое исключающее ИЛИ для заданных чисел teo. Однако мы эффективно подсчитываем количество установленных битов в их 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 справа. Процесс не может быть продолжен, поскольку целое число N стало равным нулю.

Эта красивая идея оказалась очень полезной для счетчик набора битов в целое число, так как нам нужно только повторять столько раз, сколько есть установленные биты в данном целом числе.

Алгоритм

  1. Сохраните побитовый XOR двух целых чисел в переменной - xor_
  2. Инициализировать CNT = 0 для сохранения результата
  3. В то время как xor_ больше 0:
    1. инкремент cnt: cnt ++
    2. установить xor_ = xor_ & (xor_ - 1)
  4. Возврат CNT

Реализация решения Leetcode с расстоянием Хэмминга

Программа 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;
}

Программа Java

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

Анализ сложности решения Leetcode с расстоянием Хэмминга

Сложность времени

O (1) поскольку мы выполняем постоянное количество операций независимо от ввода.

Пространство сложности

O (1) поскольку мы используем постоянное пространство памяти.