CODEWITHSUNDEEP
xorbit
brewersfan1976
brewersfan1976

Reputation: 141

find the different rightmost bit

I am stuck on this problem. Thanks for your assistance.

You're given two integers, n and m. Find position of the rightmost bit in which they differ in their binary representations (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2position_of_the_found_bit (0-based).

Example

For n = 11 and m = 13, the output should be differentRightmostBit(n, m) = 2.

11 (subscript 10) = 1011 (subscript 2), 13 (subscript) 10 = 1101 (subscript 2), the rightmost bit in which they differ is the bit at position 1 (0-based) from the right in the binary representations. So the answer is 2 to the 1st power = 2.

Upvotes: 2

Views: 3590

Answers (6)

Anurag Tiwari
Anurag Tiwari

Reputation: 1

One solution to this problem is to perform xor operation on the two inputs. After xor operation the same bits will be set to zero and the different bits will be set(==1) (as 1 ^ 0 == 1 and 1 ^ 1 == 0). Then find the position of the rightmost set bit.

int posOfRightMostDiffBit(int m, int n)

{

if(m == n){ return -1; }

int xor_val = m ^ n;
int pos = 1;
while(xor_val > 0)
{
    if(xor_val & 1)
    {
        return pos;
    }
    pos++;
    xor_val = xor_val >> 1;
}
return -1;

}

Upvotes: 0

Ahamed Ali Riyaz
Ahamed Ali Riyaz

Reputation: 31

int main()
{
    int a,b,i=0, tempa,tempb;
    printf("enter values for elements a and b\n");
    scanf("%d %d", &a,&b);
    while(i<=31)
    {
        tempa= a&(1<<i);
        tempb= b&(1<<i);
        if((tempa^tempb))
        {
          printf("pos of different bit is %d\n",i);
          break;
        }
        i++;
    }
    return 0;
}

Upvotes: 0

DevCplusplus
DevCplusplus

Reputation: 39

One More way:

int RightMostDiffBit(int M,int N){
    int count = 1;
    for(int i=0;i<32;i++){
       if((M & (count << i)) ^ (N & (count << i)))
         return i+1;
    }
    return -1;
}

Upvotes: 0

sourabh agrawal
sourabh agrawal

Reputation: 1

The answer of your question is the below code written in java.The input of this code is in following format:

Input: First line of input contains a single integer T which denotes the number of test cases. T test cases follows. First line of each test case contains two space separated integers M and N.

Example:

Input:
2
11 9
52 4
Output:
2
5

In binary "11" is "1011" and "9" is "1001" and as you can see the 2nd bit(from R.H.S) is different and that should be our answer. 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//sourabh agrawal
class GFG {
    public static void main(String[] args)throws IOException{
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();

        while(t-->0){
            StringTokenizer st = new StringTokenizer(br.readLine().trim());

            int a = Integer.parseInt(st.nextToken().trim());
            int b = Integer.parseInt(st.nextToken().trim());

            int c = (a^b)&-(a^b);   //this is the key to solve the question

            String ans = Integer.toBinaryString(c);
            int size = ans.length();
            int position = 1;

            while(size-->0){
                if(ans.charAt(size)=='0'){
                    position++;
                }else{
                    break;
                }
            }

            sb.append(position).append("\n");
        }
        System.out.println(sb);
    }
}

Upvotes: 0

Rahul Singh
Rahul Singh

Reputation: 21

Since all integers are stored in a 32 bit register hence we need to check value in all these 32 registers now since at 32th register we require 1 from right so 33-32=1 hence at last 33-a[k-1] for the answer. Here i just stored the positions where the binary value is unequal in array 'a' and printed the last element in the array would even work for -ve integers.

    #include <iostream>
    using namespace std;
    int main()
    {
         int n,m,k=0,y=0;
         cin>>n>>m;
         int a[32];
         for(int i=31;i>=0;i--)
         {
             y=y+1;
             if(n & (1<<i)) 
             {if( !(m & (1<<i)) )
                 {
                     a[k]=y;
                     k++;
                 }
             }else
             if ( !(n & (1<<i)) )  
             {if (m & (1<<i))
               {
                  a[k]=y;
                  k++;
               }
             }
        }
        cout<<33-a[k-1];
        return 0;
    }

Upvotes: 0

brewersfan1976
brewersfan1976

Reputation: 141

After playing around with the bitwise operators I got it !! the answer is (n ^ m) & -(n ^ m)

I could have easily done this in ruby without using the bitwise operators by converting them to a binary string and finding the first non - match starting on the right side and returning (2 ** position) but it was required to be a one liner using the bitwise operators that was the tricky part.

I give credit to Ryan for pointing me in the right direction. Thanks Ryan !!

Upvotes: 12

Related Questions