different Rightmost Bit

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.1110 = 101121310 = 11012, 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 21 = 2.
  • For n = 7 and m = 23, the output should be
    differentRightmostBit(n, m) = 16.710 = 11122310 = 101112, i.e.

    00111
    10111
    

    So the answer is 24 = 16.

int differentRightmostBit(int n, int m) {
  System.out.println(Integer.toBinaryString(n^m));
  System.out.println(Integer.toBinaryString((~(n^m))));

  return (~(n^m)+1)&(n^m);
}

this is a similar problem to the last bitwise problem I posted this week.

  • Turning all the different bits to 1 is straightforward with xor:
    n XOR m
  • Turning all the bits to 0 is also straightforward with AND and NOT:
    (n XOR m) AND (NOT(x XOR m))

if you n & ~n you get 0 but if you  n & ~n+1 you get the first value that was 1.

 

https://catonmat.net/low-level-bit-hacks

Author: enroblog

Computer science student at ITESM

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s