Как работает оператор сдвига при поиске числа разных бит в двух целых числах? - PullRequest
Новая
       71

Как работает оператор сдвига при поиске числа разных бит в двух целых числах?

0 голосов
/ 29 сентября 2019

Я пытался узнать количество разных бит в двух числах. Я нахожу здесь решение, но не могу понять, как оно работает. Оно сдвигается вправо с i и делает и с 1 . на самом деле, что происходит за этим? и зачем делать цикл через 32 ? 

void solve(int A, int B) 
{ 
    int count = 0; 

    // since, the numbers are less than 2^31 
    // run the loop from '0' to '31' only 
    for (int i = 0; i < 32; i++) { 

        // right shift both the numbers by 'i' and 
        // check if the bit at the 0th position is different 
        if (((A >> i) & 1) != ((B >> i) & 1)) { 
            count++; 
        } 
    } 

    cout << "Number of different bits : " << count << endl; 
}

1 Ответ

4 голосов
/ 29 сентября 2019

Цикл работает от 0 до 31 включительно (не через 32), потому что это все возможные биты, которые составляют 32-разрядное целое число , и нам нужно проверить их все.

Внутри цикла код 

    if (((A >> i) & 1) != ((B >> i) & 1)) { 
        count++; 
    }

работает, сдвигая каждое из двух целых чисел вправо на i (обрезая биты, если i > 0), извлекая самый правый бит после сдвига (& 1) и проверяем, что они одинаковы (т. Е. Оба 0 или оба 1).

Давайте рассмотрим пример: solve(243, 2182). В двоичном виде: 

243 =                              11110011
2182 =                         100010000110
diff bits =                    ^    ^^^ ^ ^
int bits = 00000000000000000000000000000000
i =       31                              0 
                  <-- loop direction

Индексы i, которые дают различия, равны 0, 2, 4, 5, 6 и 11 (мы проверяем справа налево - в первой итерации, i = 0 и ничего не сдвигается, поэтому & 1 дает нам самый правильный бит и т. Д.). Все отступы слева от каждого числа в приведенном выше примере равны нулю.

Также обратите внимание, что существуют лучшие способы сделать это без цикла: возьмите XOR двух чисел и выполните popcountна них (считайте установленные биты): 

__builtin_popcount(243 ^ 2182); // => 6

Или, более точно: 

std::bitset<CHAR_BIT * sizeof(int)>(243 ^ 2182).count()

Еще одно примечание: лучше всего избегать using namespace std;,верните значение вместо создания отпечатка с побочным эффектом и дайте методу более ясное имя, чем solve, например bit_diff (я понимаю, что это от geeksforgeeks ).

...