[Programmers - 2017 팁스타운] 예상 대진표 (cpp / python)

예상 대진표

프로그래머스

문제 설명

N 은 2의 지수승으로 주어지기 때문에 2진수와 관련이 있지 않을까 생각했다.

8팀이 주어졌을때 2번과 7번이 만나기 위해서는 총 3번의 경기를 진행해야한다.

1 2 3 4 5 6 7 8 (8팀)
2 x y 7 (4팀)
2 7 (2팀)

문제 풀이

소스코드 : C++

2로 나눌때마다 answer++을 해주고, ( 로직을 2진수로 접근해서 시프트 연산자를 썼다.), a와 b가 같아질 때까지 반복한다.

1 2 3 4 5 6 7 8 (8팀) - 2로 나누고 answer +1
1 x y 4 (4팀) - 2로 나누고 answer + 1
0 2 (2팀) - 2로 나누고 answer + 1
0 1 - 2로 나누고 answer +1
0 0 = answer = 4
2진수는 0부터 생각해야하므로 처음 시작하기 전에 a--, b--를 해주고 시작해야 올바른 결과를 얻을 수 있다.

#include <iostream>

using namespace std;

int solution(int n, int a, int b){
    int answer =0;
    a--,b--;
    while(a!=b){
        a = a>>1;
        b = b>>1;
        answer++;
    }
    return answer;
}
int main(){
    cout<<solution(8,4,7);
    return 0;
}

소스코드 : Python

다른 사람 풀이를 참고했는데 이게 무슨 뜻이지..

그냥 코드 그대로 읽으면 a-1과 b-1을 xor 비트연산을 한 그 길이 이다.
  

$$
a-1 =2 \, and \,b-1 = 7 \\
a-1 = 0010_2 \,\, b-1 = 0111_2 \\
　\\ 
\begin{array} 
{c|r}& 0010_2\\ 
xor & 0111_2\\ 
\hline 
　&0101_2 
\end{array}\\ bit\_length = 3 (101_2) 
 \\ 
a-1 = 5 \, and \, b-1 = 11 \\ 
a-1 = 0101_2 \,\, b-1 = 1011_2 
　\\ 
\begin{array} 
{c|r}& 0101_2\\ 
xor & 1011_2\\ 
\hline 
　&1110_2 
\end{array} \\bit\_length = 4 (1110_2)
$$

어림 짐작은 가는데... 정확히 이해가 되질 않는다. 왜 xor연산을 사용했으며, 그 결과의 비트 길이가 되는지...

설명해주실분 계시면 댓글로 부탁드리겠습니다.

def solution(n,a,b):
    return ((a-1)^(b-1)).bit_length()