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 , finds the positions where the corresponding bits are different. x y 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 time complexity. We shift the bits to left or right and then check if the bit is one or not. O(1) 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 you can check if a number does not equal 0 by the operator. Hint: ^ #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 . For a integer, the algorithm would take at most 32 iterations. Time complexity: O(1) 32-bit . Memory is constant irrespective of the input. Space complexity: O(1) 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 and , the rightmost bit of one in the original number would be cleared. n (n-1) n 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 . The input size of the is fixed, we have a constant time complexity. Time complexity: O(1) integer . Memory is constant irrespective of the input. Space complexity: O(1) First Published here

Google

A Closer Look into Different Programming Styles and Paradigms

ggorantala.dev

My Portfolio

Buy My Course: Grokking Bit Manipulation For Coding Interviews.

Buy Me a Coffee

10% off educative.io

The Complete Junior to Senior Web Developer Roadmap (2022)

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Functional Programming

Too Long; Didn't Read

Make resilience your competitive advantage

How to Solve the Hamming Distance Problem in C++, A Google Interview Question

How to Solve the Hamming Distance Problem in C++, A Google Interview Question

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

SOLID: Learn About the Single Responsibility Principle With Examples

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

SOLID: Learn About the Single Responsibility Principle With Examples

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps