Количество различных битов

Учитывая два целых числа подсчитывают количество позиций, где их битовое представление отличается. Простой подход – использовать их двоичное представление и сравнить их. Они также можно сравнить на лету.

Подход: XOR.

Давайте посмотрим на таблицу правды Операции XOR:

0	0	0
0	1	1
1	0	1
1	1	1

Очевидно, что операция XOR дает 1, если два бита разные (см. Строку 2 и 3). Таким образом, установленные биты в ^ b будут те, где двоичное представление A и B отличаются.

Например,

A = 19 => 10011
B = 10 => 01010
--------------------
A ^ B => 11001

Таким образом, количество установленных битов в ^ b даст желаемый ответ. Мы можем использовать Метод Брайана-Кернеган подсчитать количество установленных битов.

C ++ код:

#include
using namespace std;

int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1); // clear the right-most bit
        ++count;
    }
    return count;
}

int countDifferntBits(int a, int b) {
    return countSetBits(a ^ b);
}

int main() {
    cout << "Number of different bits of " << 19 << " and " << 10 << " is " << countDifferntBits(19, 10) << "\n";
    return 0;
}

Код Python:

def count_set_bits(n):
    count = 0
    while n > 0:
        n = n & (n - 1) # clear the right most bit
        count += 1
    return count

def count_different_bits(a, b):
    return count_set_bits(a ^ b)

if __name__ == ' __main__':
    print('Number of different bits of', 19, 'and', 10, 'is', count_different_bits(19, 10))

Сложность времени: O (log (min (a, b))) Космическая сложность: O (1)

Упражнение : Код наивный раствор.

Оригинал: “https://dev.to/ayanb/number-of-differing-bits-3g1a”