Bit difference

You are given two numbers A and B. The task is to count the number of bits needed to be flipped to convert A to B.

Example 1:

Input: A = 10, B = 20
Output: 4
Explanation:
A = 01010
B = 10100
As we can see, the bits of A that need
to be flipped are 01010. If we flip
these bits, we get 10100, which is B.

So this a basic question just for some understanding.
I think every question is important as in each question we learn some or the other thing.

To solve this question click here:(https://practice.geeksforgeeks.org/problems/bit-difference-1587115620/1#)

As in this question you may learn about Brian Kernighans Algorithm.

Brian Kernighans Algorithm: It is used to count the set bits of an integer. The idea is to only consider the set bits of an integer by turning off its rightmost set bit (after counting it), so the next iteration of the loop considers the next rightmost bit.(eg: if n=9 (1001) then total number of set bit in this case is 2)

The expression n & (n-1) can be used to turn off the rightmost set bit of a number n.

Step by step working:
For example, consider number 9, which is 1001 in binary, and has a total 2 bits set.

1st iteration of the loop: n = 9

1001 (n)
&1000 (n-1)
~~~~
1000 (in 1st iteration n became 8)

2nd iteration of the loop: n = 8

1000 (n)
&0111 (n-1)
~~~~
0000 (in 2nd iteration n became 0 so we'll
stop
the loop)

JAVA CODE

 public static int countBitsFlip(int a, int b){

        // Your code here
         int n=a^b; //taking the XOR to see how many bits are changed
        int c=0;
        while(n!=0)
        {
            n=n&(n-1); //counting the set bits
               c++;
        }
        return c;

    }

Comments

[lionel-rowe]

JS one-liner version:

const countBitsFlip = (a, b) => [...(a ^ b).toString(2)].filter(x => x === '1').length

Using toString is a bit of a filthy hack though 😂 plus perf is much worse

[Alex Lohr]

In JS, we can use

const countBitsFlip = (a, b) => {
  let c = 0;
  for (let n = a ^ b; n !== 0; c++) {
    n = n & (n - 1);
  }
  return c;
}