C Program to find the Number of bits to change so as to convert one number to another - Bit Manipulation

 

// Program by Akash Tripathi (@proakash256) 

 

// Example : Let a = 10110 and b = 11011

// As we can see, we need to change 3

// bits so as to convert a to b.

#include <stdio.h>

void binary(int n)

{

    // Prints the Binary Representation

    // of a Decimal Number upto 11 bits.

    for(int i = 10; i >= 0; i = i - 1)

    {

        printf("%d" , ((n >> i) & 1));

    }

    printf("\n");

    return;

}

int main()

{

    int a, b, c = 0, x;

    printf("Enter the first number : ");

    scanf("%d", &a);

    printf("Binary Representation of %d is : ", a);

    binary(a);

    printf("\nEnter the second number : ");

    scanf("%d", &b);

    printf("Binary Representation of %d is : ", b);

    binary(b);

    // In this method,

    // we do (a ^ b) and

    // find the number of 1's,

    // which is the answer.

    x = (a ^ b);

    int temp = x;

    // Now to find 1's,

    // we have two methods.

    // Method 1:

    // Find (x & 1)

    // if((x & 1) == 1) then counter++

    // if((x & 1) == 0) then continue

    // x >> 1

    // Repeat till x == 0

    // Time Complexity = (log n)

    while(temp != 0)

    {

        if((temp & 1) == 1)

            c = c + 1;

       temp = temp >> 1;

    }

    printf("\nBy First Method :\n");

    printf("\nTo Change %d to %d,

            we need to change %d

            bits.\n\n" , a , b , c);

    temp = x;

    c = 0;

    // Method 2:

    // Find x & (x - 1)

    // It removes the last significant bit

    // keep increasing the counter by 1

    // till it is equal to 0

    while(temp != 0)

    {

        temp = (temp & (temp - 1));

        c = c + 1;

    }

    printf("\nBy Second Method :\n");

    printf("\nTo Change %d to %d,

            we need to change %d

            bits.\n\n" , a , b , c);

    return 0;

}