How shifting operator works in finding number of different bit in two integer?

Question

i was trying to find out number of different bit in two number. i find a solution here but couldn't understand how it works.it right shifting with i and and doing and with 1. actually what is happening behind it? and why do loop through 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; 
}

ggorlen · Answer 1 · 2019-09-29T19:15:56.100

The loop runs from 0 up to and including 31 (not through 32) because these are all of the possible bits that comprise a 32-bit integer and we need to check them all.

Inside the loop, the code

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

works by shifting each of the two integers rightward by i (cutting off bits if i > 0), extracting the rightmost bit after the shift (& 1) and checking that they're the same (i.e. both 0 or both 1).

Let's walk through an example: solve(243, 2182). In binary:

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

The indices of i that yield differences are 0, 2, 4, 5, 6 and 11 (we check from the right to the left--in the first iteration, i = 0 and nothing gets shifted, so & 1 gives us the rightmost bit, etc). The padding to the left of each number is all 0s in the above example.

Also, note that there are better ways to do this without a loop: take the XOR of the two numbers and run a popcount on them (count the bits that are set):

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

Or, more portably:

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

Another note: best to avoid using namespace std;, return a value instead of producing a print side effect and give the method a clearer name than solve, for example bit_diff (I realize this is from geeksforgeeks).

In addition to the gcc builtin `__builtin_popcount`, I believe `std::bitset` would be a more portable solution. `std::bitset(243 ^ 2182).count()` would do the trick. Unfortunately it's not `constexpr` (but can be implemented easily as `constexpr`). — ph3rin, Sep 29 '19 at 19:11

How shifting operator works in finding number of different bit in two integer?

1 Answers1