Найти количество перекрывающихся 1 бит

Question

Я пытаюсь найти количество перекрывающихся 1 битов между двумя заданными числами.

Например, учитывая 5 и 6:

5 // 101
6 // 110

Существует 1перекрывающийся 1 бит (первый бит)

У меня следующий код

#include <iostream>
using namespace std;

int main() {
    int a,b;
    int count = 0;
    cin >> a >> b;
    while (a & b != 0) {
        count++;
        a >>= 1;
        b >>= 1;
    }
    cout << count << endl;

    return 0;
}

Но когда я ввел 335 и 123, он вернул 7, но я думаю, что это не правильно

Может кто-нибудь увидеть проблему с моим кодом?

Answer 1

Проблема заключается в том, что вы просто распечатываете количество раз любых совпадений битов, так как вы отбрасываете младший значащий бит для каждой итерации (который будет максимальным числом битов) установить для меньшего числа). Вы сравниваете все биты [a] BITWISE И [b] каждой итерации. Вы можете исправить это, маскируя с помощью 1: a & b & 1, так что, пока вы каждый раз сдвигаете биты вправо, вы только проверяете, проверяется ли младший значащий бит:

while (a && b){
    count += a & b & 1;
    a>>=1;
    b>>=1;
}

Answer 2

Ваш существующий алгоритм считает каждый бит до тех пор, пока любой бит в оставшихся битах для проверки совпадений; поскольку 123 и 335 имеют общий MSB, это верно, пока любое число ненулевое. 123 меньше с 7 битами, так что это правда 7 раз, пока это число не будет полностью обработано. В крайнем случае, 128 (10000000) и 255 (11111111) вернули бы 8 с вашим методом, хотя на самом деле это 1.

Вы хотите начать И с двух чисел, а затем посчитать число 1 с в этом результате

Answer 3

Вы хотите посчитать количество установленных бит.Вместо этого ваш код является своего рода вычислением двоичного логарифма.

Увеличивать счет только, если установлен бит порядка низший .

for (int c = a & b; c != 0; c >>= 1) {
  if (c & 1)
    ++count;
}

Answer 4

Немного короче форма:

int countCommonBits(int a,int b) {    
    int n = 0;
    for (unsigned v = (unsigned)(a & b); v; v >>= 1) {
        n += 1 & v;
    }
    return n;
}

Если вы знаете, что оба числа положительные, вы можете опустить использование типа без знака.Обратите внимание, что при использовании «int» расширение знака при сдвиге вправо отрицательного числа дает вам немного избыточного счета (т. Е. Бесконечный цикл).

Намного позже ... Просмотрстарый ответ, наткнулся на это.Текущий «принятый» ответ: 1) неэффективен и 2) бесконечный цикл, если числа отрицательны.FWIW.