How to check if two numbers differ at one bit position only
Problem statement
Given two numbers x and y, check whether the two numbers differ at one bit position only.
Example 1:
- Input: x=7, y=5
- Output: 7 and 5 differ by one bit
The binary representation of 7 is 0111 and of 5 is 0101. Here, only the second rightmost bit differs, while other bits remain the same.
Example 2:
- Input: x=5, y=15
- Output: 5 and 15 don’t differ by one bit
The binary representation of 15 is 1111 and of 5 is 0101. Here, only the second and fourth rightmost bit differs, so the output is No.
Solution
The solution is simple and is as follows:
- Find the bitwise XOR of
xandy. - If the result of step 1 is a power of two, then the two numbers differ by one bit. Otherwise, the two numbers don’t differ by one bit.
Refer to Check if a number is a power of two for different ways to implement step 2.
Code example
Let’s look at the code below:
public class Main {static boolean isPowerOfTwo(int n){return n != 0 && ((n & (n-1)) == 0);}static boolean oneBitPosDiffer(int x, int y){return isPowerOfTwo(x ^ y);}public static void main(String[] args) {int x = 5;int y = 15;boolean res = oneBitPosDiffer(x, y);if(res) System.out.println(x + " and " + y + " differ only by one bit");else System.out.println(x + " and " + y + " don't differ only by one bit");}}
Code explanation
- Lines 3 to 5: We define a function called
isPowerOfTwowhich checks if the given number is a power of two or not. - Lines 7 to 9: We define a function called
oneBitPosDifferwhich performs the bitwise XOR on the input numbersxandy. The result of the XOR operation is passed as an input to theisPowerOfTwofunction. - Line 12: We define the first number
x. - Line 13: We define the second number
y. - Line 14: We invoke
oneBitPosDiffer()withxandyas parameters. - Lines 16 and 17: We print the output based on the result of line 14.