Hamming Distance

The Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different. If we take it in another way, then it is the minimum number of substitutions required to convert one string to another. For example:

sushant & samudra, hamming distance is 6.

roses & toned ,hamming distance is 3.

But my friend Vinit is interested in numbers, so he wants to apply this concept with numbers. He wants to calculate the minimum number of flips in bit representation of number that requires changing to another number. Can you please help him to solve this problem.

Input

Input will be two number m (0<=m<=4294967295) and n (0<=n<=4294967295). Input will be ended when m and n both become 0.

 

Output

Output is the minimum number of flip of bits required to change m to n and vice versa.

 

Sample Input

21 34

100 200

65 96

0 0

 

Sample Output

5

4

2

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Diagnostics;

using System.IO;

using System.Text.RegularExpressions;

 

namespace HammingDistance

{

    class Program

    {

        static void Main(string[] args)

        {

            try

            {

                Stopwatch watch = new Stopwatch();

                watch.Start();

                StreamReader sr = new StreamReader(@"C:\input.txt");

                Regex reg = new Regex(" ");

                for (string str = sr.ReadLine(); str != null; str = sr.ReadLine())

                {

                    double[] num = new double[2];

                    int count = -1;

                    foreach (string val in reg.Split(str))

                    {

                        num[++count] = double.Parse(val);

                    }

                    if (num[0] != 0 || num[1] != 0)

                    {

                        Console.WriteLine("Hamming Distance = " + HammingDistance(BinaryRepresentaion(num[0]), BinaryRepresentaion(num[1])));

                    }

                }

                sr.Close();

                watch.Stop();

                Console.WriteLine("Elapsed: {0}", watch.Elapsed);

            }

            catch (Exception e)

            {

                Console.WriteLine(e.Message);

            }

        }

        public static int HammingDistance(string str1, string str2)

        {

            int diffCount = 0;

            if (str1.Length > str2.Length)

            {

                do

                {

                    str2 = "0" + str2;

                } while (str1.Length != str2.Length);

            }

            else if (str1.Length < str2.Length)

            {

                do

                {

                    str1 = "0" + str1;

                } while (str1.Length != str2.Length);

            }

            for (int i = 0; i < str1.Length; i++)

            {

                if (str1[i] != str2[i])

                {

                    diffCount++;

                }

            }

            return diffCount;

        }

        public static string BinaryRepresentaion(double num)

        {

            string binary = "";

            do

            {

                int remainder = (int)(num % 2);

                double dividend = num / 2;

                binary = remainder.ToString() + binary;

                num = dividend;

            } while (num >= 1);

            return binary;

        }

    }

}

Output
===============================
Hamming Distance = 5
Hamming Distance = 4
Hamming Distance = 2
Elapsed: 00:00:00.0076140
Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s