Xor and bit manipulation


  • 0
    A
     * main.c
     *
     *  Created on: Sep 2, 2017
     *      Author: prakhar avasthi
     */
    
    /*
     * This question requires the knowledge of bitwise operation.
     * We will get two numbers, say a and b.
     * then, we need to find number of bits which are different in a and b.
     * if we xor a and b, then different bits in a and b will become 1
     * and same bits in a and b will become 0.
     * num a = 9 bits 1 0 0 1
     * num b = 6 bits 0 1 1 0
     * c = a^b = bits 1 1 1 1
     * now we need to calculate total number of bits which are 1 in a^b
     * To calculate that, we have to perform & operation with 1
     * c & 1, if last bit is 1 then result will be 1.
     * so in a loop we need to perform c&1 and interate with c>>1(right shift)
     * so that we get new bit to compare in each loop until c > 0
     *
     *
     * */
    
    #include<stdio.h>
    
    int hamming_distance(int x, int y)
    {
    	int result = 0;
    	int c = x^y;	//C1: xor operation to make different bits 1
    	printf("c: %d\n", c);
    	for(int i=c; i>0; i = i>>1)		//C2: loop with right shift operator
    	{								//    so that we can compare new bit each time
    		//printf("i: %d\n", i);		//    as bit will shift to right
    		//printf("i&1: %d\n", i&1);
    		if((i&1) == 1)				//C3: & with 1, so that we can check if bit is 1
    		{							//    which means bits are different before xor
    			result++;
    		}
    	}
    	return result;
    }
    
    int main()
    {
    	int test_case;
    	int numA, numB;
    
    	setbuf(stdout, NULL);
    	scanf("%d", &test_case);
    
    	while(test_case--)
    	{
    		scanf("%d %d", &numA, &numB);
    		printf("Result: %d\n", hamming_distance(numA, numB));
    	}
    	return 0;
    }```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.