Number of mismatching bits in the binary representation of two integers
Given two integers(less than 2^31) A and B. The task is to find the number of bits that are different in their binary representation.
Examples:
Input : A = 12, B = 15 Output : Number of different bits : 2 Explanation: The binary representation of 12 is 1100 and 15 is 1111. So, the number of different bits are 2. Input : A = 3, B = 16 Output : Number of different bits : 3
Approach:
- Run a loop from ‘0’ to ’31’ and right shift the bits of A and B by ‘i’ places, then check whether the bit at the ‘0th’ position is different.
- If the bit is different then increase the count.
- As the numbers are less than 2^31, we only have to run the loop ’32’ times i.e. from ‘0’ to ’31’.
- We can get the 1st bit if we bitwise AND the number by 1.
- At the end of the loop display the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // compute number of different bits 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; } // Driver code int main() { int A = 12, B = 15; // find number of different bits solve(A, B); return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { // compute number of different bits static 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++; } } System.out.println( "Number of different bits : " + count); } // Driver code public static void main (String[] args) { int A = 12 , B = 15 ; // find number of different bits solve(A, B); } } // this code is contributed by anuj_67.. |
Python3
# Python3 implementation of the approach # compute number of different bits def solve( A, B): count = 0 # since, the numbers are less than 2^31 # run the loop from '0' to '31' only for i in range ( 0 , 32 ): # 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 = count + 1 print ( "Number of different bits :" ,count) # Driver code A = 12 B = 15 # find number of different bits solve( A, B) # This code is contributed by ihritik |
C#
// C# implementation of the approach using System; class GFG { // compute number of different bits static 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++; } } Console.WriteLine( "Number of different bits : " + count); } // Driver code public static void Main() { int A = 12, B = 15; // find number of different bits solve(A, B); } } // This code is contributed by ihritik |
PHP
<?php // PHP implementation of the approach // compute number of different bits function solve( $A , $B ) { $count = 0; // since, the numbers are less than 2^31 // run the loop from '0' to '31' only for ( $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 ++; } } echo "Number of different bits : $count" ; } // Driver code $A = 12; $B = 15; // find number of different bits solve( $A , $B ); // This code is contributed by ihritik ?> |
Javascript
<script> // Javascript implementation of the approach // Compute number of different bits function solve(A, B) { var count = 0; // Since, the numbers are less than 2^31 // run the loop from '0' to '31' only for (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++; } } document.write( "Number of different bits : " + count); } // Driver code var A = 12, B = 15; // Find number of different bits solve(A, B); // This code is contributed by Rajput-Ji </script> |
Output
Number of different bits : 2
Time Complexity: O(32)
Auxiliary Space: O(1)
A different approach using xor(^):
- Find XOR (^) of two number, say A and B.
- And let their result of XOR(^) of A & B be C;
- Count number of set bits (1’s ) in the binary representation of C;
- Return the count;
Example:
- Let A = 10 (01010) and B = 20 (10100)
- After xor of A and B, we get XOR = 11110. ( Check XOR table if necessary).
- Counting the number of 1’s in XOR gives the count of bit differences in A and B. (using Brian Kernighan’s Algorithm)
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // compute number of different bits int solve( int A, int B) { int XOR = A ^ B; // Check for 1's in the binary form using // Brian Kernighan's Algorithm int count = 0; while (XOR) { XOR = XOR & (XOR - 1); count++; } return count; } // Driver code int main() { int A = 12, B = 15; // 12 = 1100 & 15 = 1111 int result = solve(A, B); cout << "Number of different bits : " << result; return 0; } // the code is by Samarpan Chakraborty |
Java
/*package whatever //do not write package name here */ // Java implementation of the approach import java.io.*; class GFG { // compute number of different bits static int solve( int A, int B) { int XOR = A ^ B; // Check for 1's in the binary form using // Brian Kerninghan's Algorithm int count = 0 ; while (XOR > 0 ) { XOR = XOR & (XOR - 1 ); count++; } // return the count of different bits return count; } public static void main(String[] args) { int A = 12 , B = 15 ; // find number of different bits int result = solve(A, B); System.out.println( "Number of different bits : " + result); } } // the code is by Samarpan Chakraborty |
Python3
# code def solve(A, B): XOR = A ^ B count = 0 # Check for 1's in the binary form using # Brian Kernighan's Algorithm while (XOR): XOR = XOR & (XOR - 1 ) count + = 1 return count result = solve( 3 , 16 ) # 3 = 00011 & 16 = 10000 print ( "Number of different bits : " , result) # the code is by Samarpan Chakraborty |
C#
// C# program for the above approach using System; class GFG { // compute number of different bits static int solve( int A, int B) { int XOR = A ^ B; // Check for 1's in the binary form using // Brian Kerninghan's Algorithm int count = 0; while (XOR > 0) { XOR = XOR & (XOR - 1); count++; } // return the count of different bits return count; } // Driver code public static void Main() { int A = 12, B = 15; // find number of different bits int result = solve(A, B); Console.WriteLine( "Number of different bits : " + result); } } // This code is contributed by target_2. |
Javascript
<script> /*package whatever //do not write package name here */ // JavaScript implementation of the approach // compute number of different bits function solve(A, B) { var XOR = A ^ B; // Check for 1's in the binary form using // Brian Kerninghan's Algorithm var count = 0; while (XOR > 0) { XOR = XOR & (XOR - 1); count++; } // return the count of different bits return count; } var A = 12, B = 15; // find number of different bits var result = solve(A, B); document.write( "Number of different bits : " + result); // This code is contributed by shivanisinghss2110 </script> |
Output
Number of different bits : 2
Time Complexity: O(log (A^B))
Auxiliary Space: O(1)