Как решить проблему расстояния Хэмминга в C++, вопрос интервью Google
7 марта 2022 г.В этом уроке мы найдем количество позиций, в которых биты различны для данного ввода.
Введение
В этом вопросе мы найдем количество позиций, в которых соответствующие биты различны.
Постановка задачи
По заданным целым числам x, y находит позиции, в которых соответствующие биты различны.
Пример 01:
```java
Вход: х = 1, у = 8
Выход: 2
Объяснение:
1 (0 0 0 1)
8 (1 0 0 0)
↑ ↑
Пример 02:
```java
Вход: х = 12, у = 15
Выход: 2
Объяснение:
12 (1 1 0 0)
15 (1 1 1 1)
Решение
Мы решаем это с помощью операции сдвига, а затем переходим к решению более оптимальным способом.
Битовый сдвиг
Этот подход лучше, так как требует временной сложности O(1). Мы сдвигаем биты влево или вправо, а затем проверяем, является ли бит единицей или нет.
Алгоритм
Мы используем операцию сдвига вправо, где каждый бит должен быть сдвинут в крайнее правое положение.
После сдвига мы используем либо % по модулю (т. е. i % 2), либо операцию & (т. е. i & 1).
Код
Подсказка: вы можете проверить, не равно ли число 0, с помощью оператора ^.
нажмите лайк
include <иопоток>
использование пространства имен std;
пустота hammingDistance (int a, int b) {
интервал xorVal = а ^ б;
расстояние = 0;
в то время как (xorVal ^ 0) {
если(xorVal% 2 == 1){
расстояние += 1;
xorVal >>= 1;
cout << "Расстояние Хэмминга между двумя целыми числами равно" << Distance << endl;
интервал основной () {
инт а = 1;
интервал б = 8;
расстояние Хэмминга(а, б);
вернуть 0;
Анализ сложности
Временная сложность: O(1). Для «32-битного» целого числа алгоритм потребовал бы не более 32 итераций.
Пространственная сложность: O(1). Память постоянна независимо от ввода.
Алгоритм Брайана Кернигана
В приведенном выше подходе мы сдвигали каждый бит один за другим. Итак, есть ли лучший подход к нахождению расстояния Хэмминга? да.
Алгоритм
Когда мы выполняем & битовую операцию между числами n и (n-1), самый правый бит единицы в исходном числе n будет очищен.
нажмите лайк
п = 40 => 00101000
п - 1 = 39 => 00100111
(n & (n - 1)) = 32 => 00100000
Код
Основываясь на приведенной выше идее, мы можем посчитать расстояние за 2 итерации, а не за все итерации смещения, которые мы делали ранее. Давайте посмотрим код в действии.
нажмите лайк
include <иопоток>
использование пространства имен std;
int hammingDistance(int a, int b){
интервал xorVal = а ^ б;
расстояние = 0;
в то время как (xorVal != 0) {
расстояние += 1;
xorVal &= ( xorVal - 1); // равно xorVal = xorVal & ( xorVal - 1);
обратное расстояние;
интервал основной () {
инт а = 1;
интервал б = 8;
cout << "Расстояние Хэмминга между двумя целыми числами равно" << hammingDistance(a, b);
вернуть 0;
Анализ сложности
Временная сложность: O(1). Размер ввода «целого числа» фиксирован, у нас постоянная временная сложность.
Пространственная сложность: O(1). Память постоянна независимо от ввода.
- Впервые опубликовано [здесь] (https://dev.to/ggorantala/hamming-distance-kcm)*
Оригинал