Count number of bits to be flipped to convert A to B
Given two numbers A and B. Write a program to count the number of bits needed to be flipped to convert A to B.
Examples:
Input: A = 10, B = 20
Output: 4
Explanation: Binary representation of A is 00001010
Binary representation of B is 00010100
We need to flip highlighted four bits in A to make it B.Input: A = 7, B = 10
Output: 3
Explanation: Binary representation of A is 00000111
Binary representation of B is 00001010
We need to flip highlighted three bits in A to make it B.
Count the number of bits to be flipped to convert A to B using the XOR operator:
To solve the problem follow the below idea:
Calculate (A XOR B), since 0 XOR 1 and 1 XOR 0 is equal to 1. So calculating the number of set bits in A XOR B will give us the count of the number of unmatching bits in A and B, which needs to be flipped
Follow the given steps to solve the problem:
- Calculate the XOR of A and B
- Count the set bits in the above-calculated XOR result
- Return the count
Below is the implementation of the above approach:
C
// C program for the above approach #include <stdio.h> // Function that count set bits int countSetBits( int n) { int count = 0; while (n > 0) { count++; n &= (n - 1); } return count; } // Function that return count of flipped number int FlippedCount( int a, int b) { // Return count of set bits in a XOR b return countSetBits(a ^ b); } // Driver code int main() { int a = 10; int b = 20; // Function call printf ( "%d\n" , FlippedCount(a, b)); return 0; } // This code is contributed by Sania Kumari Gupta // (kriSania804) |
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that count set bits int countSetBits( int n) { int count = 0; while (n > 0) { count++; n &= (n - 1); } return count; } // Function that return count of // flipped number int FlippedCount( int a, int b) { // Return count of set bits in // a XOR b return countSetBits(a ^ b); } // Driver code int main() { int a = 10; int b = 20; // Function call cout << FlippedCount(a, b) << endl; return 0; } // This code is contributed by Sania Kumari Gupta // (kriSania804) |
Java
// Java program for the above approach import java.util.*; class Count { // Function that count set bits public static int countSetBits( int n) { int count = 0 ; while (n != 0 ) { count++; n &= (n - 1 ); } return count; } // Function that return count of // flipped number public static int FlippedCount( int a, int b) { // Return count of set bits in // a XOR b return countSetBits(a ^ b); } // Driver code public static void main(String[] args) { int a = 10 ; int b = 20 ; // Function call System.out.print(FlippedCount(a, b)); } } // This code is contributed by rishabh_jain |
Python3
# Python3 program for the above approach # Function that count set bits def countSetBits(n): count = 0 while n: count + = 1 n & = (n - 1 ) return count # Function that return count of # flipped number def FlippedCount(a, b): # Return count of set bits in # a XOR b return countSetBits(a ^ b) # Driver code if __name__ = = "__main__" : a = 10 b = 20 # Function call print (FlippedCount(a, b)) # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program for the above approach using System; class Count { // Function that count set bits public static int countSetBits( int n) { int count = 0; while (n != 0) { count++; n &= (n - 1); } return count; } // Function that return // count of flipped number public static int FlippedCount( int a, int b) { // Return count of set // bits in a XOR b return countSetBits(a ^ b); } // Driver code public static void Main() { int a = 10; int b = 20; // Function call Console.WriteLine(FlippedCount(a, b)); } } // This code is contributed by vt_m. |
PHP
<?php // php program for the above approach // Function that count set bits function countSetBits( $n ) { $count = 0; while ( $n ) { $count += 1; $n &= (n-1); } return $count ; } // Function that return // count of flipped number function FlippedCount( $a , $b ) { // Return count of set // bits in a XOR b return countSetBits( $a ^ $b ); } // Driver code $a = 10; $b = 20; // Function call echo FlippedCount( $a , $b ); // This code is contributed by mits ?> |
Javascript
// Count number of bits to be flipped // to convert A into Bclass Count { // Function that count set bits function countSetBits(n) { var count = 0; while (n != 0) { count++; n &= (n - 1); } return count; } // Function that return count of // flipped number function FlippedCount(a , b) { // Return count of set bits in // a XOR b return countSetBits(a ^ b); } // Driver code var a = 10; var b = 20; document.write(FlippedCount(a, b)); // This code is contributed by shikhasingrajput |
4
Time Complexity: O(K) where K is the number of bits
Auxiliary Space: O(1)
Note: Set bits in (a XOR b) can also be computer using built in function __builtin_popcount() in C/C++
Below is the implementation of the above approach:
C++
// C++ program to Count number of bits to be flipped // to convert A into B #include <iostream> using namespace std; // Driver code int main() { int a = 10; int b = 20; // Function call cout <<__builtin_popcount(a^b) << endl; return 0; } // This code is contributed by Suruchi Kumari |
C
//C program to Count number of bits to be flipped // to convert A into B #include <stdio.h> // Driver code int main() { int a = 10; int b = 20; // Function call printf ( "%d\n" ,__builtin_popcount(a^b)); return 0; } // This code is contributed by Suruchi Kumari |
Java
//java code public class Main { public static void main(String[] args) { int a = 10 ; int b = 20 ; // Function call System.out.println(Integer.bitCount(a ^ b)); } } //code by ksam24000 |
Python3
# Python program to Count number of bits to be flipped # to convert A into B # Driver code if __name__ = = '__main__' : a = 10 b = 20 # Function call # Converting int to binary and counting number of bits result = bin (a ^ b).count( "1" ) print (result) |
C#
using System; class Program { static void Main( string [] args) { int a = 10; int b = 20; // Function call Console.WriteLine(BitCount(a ^ b)); } static int BitCount( int value) { int count = 0; while (value != 0) { count += value & 1; value >>= 1; } return count; } } |
Javascript
// Function to count number of bits to be flipped // to convert A into B function countBits(a, b) { return (a ^ b).toString(2).split( '1' ).length-1; } // Driver code let a = 10; let b = 20; console.log(countBits(a, b)); // This code is contributed by Potta Lokesh |
4
Time Complexity: O(K) where K is the number of bits
Auxiliary Space: O(1)
Count the number of bits to be flipped to convert A to B using the AND operator:
To solve the problem follow the below idea:
Start comparing the bits in A and B, starting from the least significant bit and if (A & 1) is not equal to (B & 1) then the current bit needs to be flipped, as the value of bits is different at this position in both the numbers
Follow the given steps to solve the problem:
- Declare variable flips equal to zero
- Run a loop, while a is greater than zero and b is also greater than zero
- Calculate values of (A AND 1) and (B AND 1)
- If these values are not equal then increase the flip value by 1
- Right shift a and b by 1
- Return flips
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; int countFlips( int a, int b) { // initially flips is equal to 0 int flips = 0; // & each bits of a && b with 1 // and store them if t1 and t2 // if t1 != t2 then we will flip that bit while (a > 0 || b > 0) { int t1 = (a & 1); int t2 = (b & 1); if (t1 != t2) { flips++; } // right shifting a and b a >>= 1; b >>= 1; } return flips; } int main() { int a = 10; int b = 20; cout << countFlips(a, b); } // this code is contributed by shivanisinghss2110 |
Java
// Java program for the above approach // CONTRIBUTED BY PRAVEEN VISHWAKARMA import java.io.*; class GFG { public static int countFlips( int a, int b) { // initially flips is equal to 0 int flips = 0 ; // & each bits of a && b with 1 // and store them if t1 and t2 // if t1 != t2 then we will flip that bit while (a > 0 || b > 0 ) { int t1 = (a & 1 ); int t2 = (b & 1 ); if (t1 != t2) { flips++; } // right shifting a and b a >>>= 1 ; b >>>= 1 ; } return flips; } // Driver code public static void main(String[] args) { int a = 10 ; int b = 20 ; // Function call System.out.println(countFlips(a, b)); } } |
Python3
# Python3 program for the above approach def countFlips(a, b): # initially flips is equal to 0 flips = 0 # & each bits of a && b with 1 # and store them if t1 and t2 # if t1 != t2 then we will flip that bit while (a > 0 or b > 0 ): t1 = (a & 1 ) t2 = (b & 1 ) if (t1 ! = t2): flips + = 1 # right shifting a and b a >> = 1 b >> = 1 return flips # Driver code if __name__ = = "__main__" : a = 10 b = 20 # Function call print (countFlips(a, b)) # This code is contributed by shivanisinghss2110 |
C#
// C# program for the above approach using System; class GFG { public static int countFlips( int a, int b) { // initially flips is equal to 0 int flips = 0; // & each bits of a && b with 1 // and store them if t1 and t2 // if t1 != t2 then we will flip that bit while (a > 0 || b > 0) { int t1 = (a & 1); int t2 = (b & 1); if (t1 != t2) { flips++; } // right shifting a and b a >>= 1; b >>= 1; } return flips; } // Driver code public static void Main(String[] args) { int a = 10; int b = 20; // Function call Console.Write(countFlips(a, b)); } } // This code is contributed by shivanisinghss2110 |
Javascript
/*package whatever //do not write package name here */ function countFlips(a, b){ // initially flips is equal to 0 var flips = 0; // & each bits of a && b with 1 // and store them if t1 and t2 // if t1 != t2 then we will flip that bit while (a>0 || b>0){ var t1 = (a&1); var t2 = (b&1); if (t1!=t2){ flips++; } // right shifting a and b a>>>=1; b>>>=1; } return flips; } var a = 10; var b = 20; document.write(countFlips(a, b)); // This code is contributed by shivanisinghss2110 |
4
Time Complexity: O(K) where K is the number of bits
Auxiliary Space: O(1)
Count the number of bits to be flipped to convert A to B:-
To solve this we just need to do a few simple steps. To know more follow the below steps:-
Approach:
- Convert A and B to binary numbers.
- Compare using ‘equal to’ operator if equal then return 0 otherwise iterate and
- compare the ith of A to ith of B and count the operations
- print the count.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; string binary( int num) { string str = "" ; while (num) { if (num & 1) // 1 str += '1' ; else // 0 str += '0' ; num >>= 1; // Right Shift by 1 } reverse(str.begin(), str.end()); return str; } int main() { int a = 10; int b = 20; string astr = binary(a); string bstr = binary(b); // size of the binary strings. int na = astr.size(), nb = bstr.size(); int cnt = 0; // difference between the size of the both a and b // string // int maxi = max(na, nb); int diff = abs (na - nb); // if a size is greater then check it has 1 upto diff // then cnt++; if (na > nb) { for ( int i = 0; i < diff; i++) { if (astr[i] == '1' ) { cnt++; } } } // do the same as above else if (na < nb) { for ( int i = 0; i < diff; i++) { if (bstr[i] == '1' ) { cnt++; } } } na = na - 1; nb = nb - 1; // check from the last if has not equal characters and // cnt++; while (na >= 0 and nb >= 0) { if (astr[na] != bstr[nb]) { cnt++; } na--; nb--; } // print the cnt cout << cnt << endl; return 0; } // this code is contributed by ksam24000 |
Java
import java.util.*; public class Main { public static String binary( int num) { String str = "" ; while (num > 0 ) { if ((num & 1 ) == 1 ) // 1 str += '1' ; else // 0 str += '0' ; num >>= 1 ; // Right Shift by 1 } return new StringBuilder(str).reverse().toString(); } public static void main(String[] args) { int a = 10 ; int b = 20 ; String astr = binary(a); String bstr = binary(b); // size of the binary strings. int na = astr.length(), nb = bstr.length(); int cnt = 0 ; // difference between the size of the both a and b int diff = Math.abs(na - nb); // if a size is greater then check it has 1 upto diff // then cnt++; if (na > nb) { for ( int i = 0 ; i < diff; i++) { if (astr.charAt(i) == '1' ) { cnt++; } } } // do the same as above else if (na < nb) { for ( int i = 0 ; i < diff; i++) { if (bstr.charAt(i) == '1' ) { cnt++; } } } na = na - 1 ; nb = nb - 1 ; // check from the last if has not equal characters and // cnt++; while (na >= 0 && nb >= 0 ) { if (astr.charAt(na) != bstr.charAt(nb)) { cnt++; } na--; nb--; } // print the cnt System.out.println(cnt); } } // This code is contributed by divyansh2212 |
Python3
def binary(num): str = "" while num: if num & 1 : # 1 str + = '1' else : # 0 str + = '0' num >> = 1 # Right Shift by 1 return str [:: - 1 ] a = 10 b = 20 astr = binary(a) bstr = binary(b) # size of the binary strings. na, nb = len (astr), len (bstr) cnt = 0 # difference between the size of the both a and b string diff = abs (na - nb) # if a size is greater then check it has 1 upto diff then cnt++ if na > nb: for i in range (diff): if astr[i] = = '1' : cnt + = 1 # do the same as above elif na < nb: for i in range (diff): if bstr[i] = = '1' : cnt + = 1 na - = 1 nb - = 1 # check from the last if has not equal characters and cnt++ while na > = 0 and nb > = 0 : if astr[na] ! = bstr[nb]: cnt + = 1 na - = 1 nb - = 1 # print the cnt print (cnt) |
C#
using System; public class Program { static string Binary( int num) { string str = "" ; while (num != 0) { if ((num & 1) == 1) // 1 str += '1' ; else // 0 str += '0' ; num >>= 1; // Right Shift by 1 } char [] charArray = str.ToCharArray(); Array.Reverse(charArray); return new string (charArray); } public static void Main() { int a = 10; int b = 20; string astr = Binary(a); string bstr = Binary(b); // size of the binary strings. int na = astr.Length, nb = bstr.Length; int cnt = 0; // difference between the size of the both a and b // string int diff = Math.Abs(na - nb); // if a size is greater then check it has 1 upto diff // then cnt++; if (na > nb) { for ( int i = 0; i < diff; i++) { if (astr[i] == '1' ) { cnt++; } } } // do the same as above else if (na < nb) { for ( int i = 0; i < diff; i++) { if (bstr[i] == '1' ) { cnt++; } } } na = na - 1; nb = nb - 1; // check from the last if has not equal characters and // cnt++; while (na >= 0 && nb >= 0) { if (astr[na] != bstr[nb]) { cnt++; } na--; nb--; } // print the cnt Console.WriteLine(cnt); } } // ksam24000 |
Javascript
function binary(num) { let str = '' ; while (num) { if (num & 1) str += '1' ; else str += '0' ; num >>= 1; } return str.split( '' ).reverse().join( '' ); } let a = 10; let b = 20; let astr = binary(a); let bstr = binary(b); let na = astr.length; let nb = bstr.length; let cnt = 0; let diff = Math.abs(na - nb); if (na > nb) { for (let i = 0; i < diff; i++) { if (astr[i] === '1' ) cnt++; } } else if (na < nb) { for (let i = 0; i < diff; i++) { if (bstr[i] === '1' ) cnt++; } } na--; nb--; while (na >= 0 && nb >= 0) { if (astr[na] !== bstr[nb]) cnt++; na--; nb--; } console.log(cnt); // THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL |
4
Time complexity- O(log N)
Auxiliary Space – O(N)
Thanks to Sahil Rajput for providing the above implementation.