Competive Programing part 01-BitFlip
Question: You are given two numbers A and B. Write a program to count number of bits needed to be flipped to convert A to B.
Solution:
1. Calculate XOR of A and B. a_xor_b = A ^ B
2. Count the set bits in the above calculated XOR result. countSetBits(a_xor_b)
Example
A = 1001001 B = 0010101
a_xor_b = 1011100
No of bits need to flipped = set bit count in a_xor_b i.e. 4(set Bit=1 and unset bit=0)
Below is implementation of code using java
import java.util.Stack; public class BitFlip { public int findbinary(int val) { int res=0; Stack<Integer>st=new Stack<>(); //to store binary element
while(val!=0) { st.push(val%2); val=val/2; } while(!st.isEmpty()) if(st.pop()==1) res++; //if set bit is found in stack increment it System.out.println(res); return res; }
public void findsetBit(int a, int b) { int c=a^b; //xor of and b is stored in c System.out.println("No of bit to flip "+ findbinary(c)); }
public static void main(String[] args) { BitFlip btBitFlip=new BitFlip(); btBitFlip.findsetBit(7, 9); } }
Above is our's implementation please feel free to post more optimized solution and help us