Tuesday, 31 January 2017

Count number of Bits to be flipped to convert A to B

Count number of bits to be flipped to convert A to B. OR
Find number of Bit swaps required to convert one integer to another OR
Given two integers A & B. Determine how many bits required to convert A to B.


Given two number A and B, Write an algorithm to count the number of bit flips required to convert A to B
Let's see what is the input and expected output for better understanding,

Case 1:
Input A: 6 (Binary equivalent of 6:   0 1 1 0 )
Input B: 8 (Binary equivalent of 8:   1 0 0 0 )
Output: Number of bits that need to be changed in A to convert it to B is :  3

Explanation: (From Right, For number 6, 

Bit at position 0 is 0, which is same in both number,
Bit at position 1 is 1, which needs to be unset to match it to number B,
Bit at position 2 is 1, which needs to be unset to match it to number B, 
Bit at position 3 is 0, which needs to be set to match it to number B)

 Case 2: 
Input A: 9 (Binary equivalent of 9:   0 1 0 0 )
Input B: 2 (Binary equivalent of 2:   0 0 1 0 )
Output: Number of bits that need to be changed in A to convert it to B is : 2

Explanation: (From Right, For number 9, 
Bit at position 0 is 0, which is same in both number,
Bit at position 1 is 0, which needs to be set to match it to number B,
Bit at position 2 is 1, which needs to be unset to match it to number B, 
Bit at position 3 is 0, which is same in both number)

Sunday, 29 January 2017

Count number of Set Bits in Integer

Count set bits in Integer OR
Count number bits set in an Integer OR
Count number of ones in Binary.


We need to write an algorithm to determine the number of set bits in integer.
In other words, count the number of 1's present in binary representation of number.

Let's see what is the input and expected output for better understanding,

Case 1:
Input: 6 Binary equivalent of 6:   0 1 1 0
Number of bits set(1's) :  2
Output: 2

Case 2: 
Input:14
Binary equivalent of 14:   1 1 1 0
Number of bits set(1's) :  3
Output: 3

Case 3: 
Input: 8
Binary equivalent of 8:   1 0 0 0
Number of bits set(1's) :  1
Output: 1