In this lesson, we find the number of positions where the bits are different for the given input.
Introduction
In this question, we will find the number of positions at which the corresponding bits are different.
Problem Statement
Given integers x, y finds the positions where the corresponding bits are different.
Example 01:
Input: x = 1, y = 8
Output: 2
Explanation:
1 (0 0 0 1)
8 (1 0 0 0)
↑ ↑
Example 02:
Input: x = 12, y = 15
Output: 2
Explanation:
12 (1 1 0 0)
15 (1 1 1 1)
↑ ↑
Solution
We solve this using shifting operation and then we move to solve it in a more optimal way.
Bit Shifting
This approach is better as it takes O(1) time complexity. We shift the bits to left or right and then check if the bit is one or not.
Algorithm
We use the right shift operation, where each bit would have its turn to be shifted to the rightmost position.
Once shifted we use either modulo % (i.e., i % 2) or & operation (i.e., i & 1).
Code
Hint: you can check if a number does not equal 0 by the ^ operator.
#include <iostream>
using namespace std;
void hammingDistance(int a, int b){
int xorVal = a ^ b;
int distance = 0;
while(xorVal ^ 0){
if(xorVal % 2 == 1){
distance += 1;
}
xorVal >>= 1;
}
cout << "Hamming Distance between two integers is " << distance << endl;
}
int main() {
int a = 1;
int b = 8;
hammingDistance(a, b);
return 0;
}
Complexity Analysis
Time complexity: O(1). For a 32-bit integer, the algorithm would take at most 32 iterations.
Space complexity: O(1). Memory is constant irrespective of the input.
Brian Kernighan’s Algorithm
In the above approach, we shifted each bit one by one. So, is there a better approach in finding the hamming distance? Yes.
Algorithm
When we do & bit operation between number n and (n-1), the rightmost bit of one in the original number n would be cleared.
n = 40 => 00101000
n - 1 = 39 => 00100111
----------------------------------
(n & (n - 1)) = 32 => 00100000
----------------------------------
Code
Based on the above idea, we can count the distance in 2 iterations rather than all the shifting iterations we did earlier. Let’s see the code in action.
#include <iostream>
using namespace std;
int hammingDistance(int a, int b){
int xorVal = a ^ b;
int distance = 0;
while (xorVal != 0) {
distance += 1;
xorVal &= ( xorVal - 1); // equals to `xorVal = xorVal & ( xorVal - 1);`
}
return distance;
}
int main() {
int a = 1;
int b = 8;
cout << "Hamming Distance between two integers is " << hammingDistance(a, b);
return 0;
}
Complexity Analysis
Time complexity: O(1). The input size of the integer is fixed, we have a constant time complexity.
Space complexity: O(1). Memory is constant irrespective of the input.
Extras
If you are interested in mastering bit tricks, I've got a course that are loved by more than 100k+ programmers.
In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. The course has simple explanation with sketches, detailed step-by-step drawings, and various ways to solve it using bitwise operators.
These bit-tricks could help in competitive programming and coding interviews in running algorithms mostly in O(1) time.
This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG(Facebook, Amazon, Apple, Netflix, and Google) companies.
To kick things off, you’ll start by learning about the number system and how it’s represented. Then you’ll move on to learn about the six different bitwise operators: AND, OR, NOT, XOR, and bit shifting. Throughout, you will get tons of hands-on experience working through practice problems to help sharpen your understanding.
By the time you’ve completed this course, you will be able to solve problems faster with greater efficiency!! 🤩
Link to my course: Master Bit Manipulation for Coding Interviews.