Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Cover image for Hamming Distance - JavaScript Solution
Gopi Gorantala
Gopi Gorantala

Posted on • Edited on

     

Hamming Distance - JavaScript Solution

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 integersx,y finds the positions where the corresponding bits are different.

Example 01:

Input:x=1,y=8Output:2Explanation:1(0001)8(1000)
Enter fullscreen modeExit fullscreen mode

Example 02:

Input:x=12,y=15Output:2Explanation:12(1100)15(1111)
Enter fullscreen modeExit fullscreen mode

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 takesO(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.

functionHammingDistance(a,b){letxor=a^b;letdistance=0;while(xor^0){if(xor%2==1){distance+=1;}xor>>=1;}returndistance;}leta=1;letb=8;console.log("Hamming Distance between two integers is",HammingDistance(a,b));
Enter fullscreen modeExit fullscreen mode

Complexity Analysis

Time complexity:O(1). For a32-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 numbern and(n-1), the rightmost bit of one in the original numbern would be cleared.

n=40=>00101000n-1=39=>00100111----------------------------------(n&(n-1))=32=>00100000----------------------------------
Enter fullscreen modeExit fullscreen mode

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.

functionHammingDistance(a,b){letxor=a^b;letdistance=0;while(xor!=0){distance+=1;xor&=(xor-1);// equals to `xor = xor & ( xor - 1);`}returndistance;}leta=1;letb=8;console.log("Hamming Distance between two integers is",HammingDistance(a,b));
Enter fullscreen modeExit fullscreen mode

Complexity Analysis

Time complexity:O(1). The input size of theinteger 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 inO(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.

Top comments(0)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

Gopi is a Developer evangelist with over 14 years of experience. He specializes in Java-based technology stacks and has worked for various startups, the European government, as well as tech giants.
  • Location
    Brussels, Belgium
  • Education
    Woolf University
  • Pronouns
    He/Him
  • Work
    Working on my startup idea. A nomad!! https://www.ggorantala.dev/all-courses/
  • Joined

More fromGopi Gorantala

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp