Different Rightmost Bit

koeyhoyh·2021년 12월 29일
0

Algorithm

목록 보기
8/16

Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.
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
solution(n, m) = 2.

1110 = 10112, 1310 = 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
solution(n, m) = 16.

710 = 1112, 2310 = 101112, i.e.

00111
10111
So the answer is 24 = 16.


Input/Output

[execution time limit] 4 seconds (py3)

[input] integer n

Guaranteed constraints:
0 ≤ n ≤ 230.

[input] integer m

Guaranteed constraints:
0 ≤ m ≤ 230,
n ≠ m.

[output] integer


오른쪽부터 시작해, 2 ** (비트가 다른 부분의 index) 를 return 해주면 되는 문제이다.


Solution

처음 생각:

myN = list("".join(reversed(format(n,'b').zfill(max(len(format(n,'b')), len(format(m,'b')))))))
myM = list("".join(reversed(format(m,'b').zfill(max(len(format(n,'b')), len(format(m,'b')))))))
    
    for i in range (max(len(myM), len(myN))):
        if myN[i] == myM[i]:
            pass
        else:
            return 2**i
def solution(n,m):
	return ...

이 형식을 지켜야 하기 때문에 최대한 축약해서 써 보았다.
이 방법으로는 코드를 submit 할 수 없기 때문에 다른 방법이 필요했다.

지금까지 binary bit 들을 &, |, ^ 등의 비트 연산자를 이용해 많이 풀었기 때문에 두 번째 방법으로는 비트 연산자를 이용해보았다.

먼저, XOR 연산을 하면 서로 다른 비트가 1로 표시되어 나타난다.
-> reverse, xor 연산, index 1을 찾으면 해결할 수 있을 것 같다.

def solution(n,m):
    return 2 ** "".join(reversed(format((n ^ m),'b'))).index('1')

비트 연산자를 알고 있는데, 직접 많이 사용하지 않다 보니 많이 낯설고 생각하는 것이 힘들다.
익숙해지도록 해야겠다.

참고 : https://qelifeblog.wordpress.com/2017/06/24/codefights-different-rightmost-bit/

profile
내가 만들어낸 것들로 세계에 많은 가치를 창출해내고 싶어요.

0개의 댓글