[ 프로그래머스 [ 월간코드챌린지 ] 2개 이하로 다른 비트 ] (C++)

프로그래머스의 2개 이하로 다른비트(월간코드챌린지) 문제이다.

 

[ 문제풀이 ]

주어진 숫자보다 큰 숫자 중에서 비트가 1 ~2개 다른 수들 중 가장 작은 수를 구해야 하는 문제이다.

전체적인 접근과정부터 과정이 이루어지는 원리, 정답도출하는 과정까지 진행해보자.

 

#1. 아주 간단한 접근방법

먼저, 이 문제를 해결하기 가장 쉬운 방법에 대해서 이야기를 해보자.

주어진 숫자 x에 대한 f(x)의 값을 구하기 위해서, x + 1 부터 계속해서 숫자들을 증가시키면서 2진수로 바꿔보고, 바꾼 2진수와 x에 대한 2진수를 하나하나 비교하면서 다른 비트의 수가 1개 혹은 2개인 숫자를 찾으면 구할 수 있을 것이다.

하지만 이렇게 구했을 때 시간초과가 발생하게 된다.

모든 숫자들을 2진수로 바꾸는 과정에서도 많은 시간이 들게 되고, 숫자의 범위가 최대 10^15이다 보니까 큰 숫자일수록 이 과정에서 소비되는 시간이 많아진다.

따라서 이 방법이 아닌 다른 방법으로 접근을 해봐야 한다.

 

#2. 비트를 반드시 '1개'만 바꾸면 되는 Case

우리는 주어진 숫자와 비트가 1개 or 2개만 다른 주어진 숫자보다 큰 숫자 중에서 가장 작은 숫자를 찾아야 한다.

그런데 비트를 반드시 '1개'만 바꾸면 되는 경우가 존재한다. 2개를 바꿔야 되는지 아닌지를 확인할 필요조차 없는 경우가 존재하게 된다. 지금부터는 그 경우에 대해서 알아보자.

다음과 같은 숫자들의 f(x) 값을 한번 구해보자.

f(2) , f(4) , f(6) , f(8) , f(10) 의 f(x)값을 구해보자.

'2' = 0010 → f(2) = '3' = 0011

'4' = 0100 → f(4) = '5' = 0101

'6' = 0110 → f(6) = '7' = 0111

'8' = 1000 → f(8) = '9' = 1001

'10' = 1010 → f(10) = '11' = 1011

아마 위의 주어진 숫자들에 대한 f(x)를 구한다면 위와 같은 결과가 나올 것이다.

그럼 지금부터 위의 숫자들에서 특징을 한번 살펴보자.

먼저 가장 쉬운 특징 2가지부터 이야기를 해보자.

1. 주어진 숫자들이 모두 짝수였다.

2. 주어진 숫자들의 f(x) 값은 모두 x + 1 이였다.

이 2가지 특징은 딱 봐도 눈에 보일 것이다. 그럼 짝수는 무조건 + 1을 한 값이 정답이 될까 ??

결론부터 말하자면, 주어진 숫자 x가 짝수라면, 그 수의 f(x) 값은 x + 1 이 된다.

그렇다면 왜 반드시 x가 짝수일 때는 x + 1이 정답이 되는지를 알아보자.

위의 주어진 숫자인 '2' , '4' , '6' , '8' , '10' 의 2진수를 다시한번 적어보겠다.

2 = 0010

4 = 0100

6 = 0110

8 = 1000

10 = 1010

무슨 공통점이 있을까 ?? 바로 "최하위비트가 반드시 '0'이라는 것" 이다.

비트를 나타냈을 때, 가장 최하위비트는 '1'을 의미하게 된다. 그렇기 때문에 최하위비트가 '1'이 되면 전체 숫자가 이 '1'에 의해서 반드시 홀수가 된다. 왜 ?? 짝수 + 홀수는 반드시 홀수가 되어버리기 때문이다.

즉 ! 어떤 숫자에 홀수인 '1'을 더하는 순간 반드시 홀수가 되어버린다. 짝수가 짝수인채로 남아있기 위해서는 2진수로 바꿨을 때 숫자들의 합이 반드시 짝수 + 짝수 여야 한다는 것이다.

예를 들어서 '6'을 보게되면 '0110' 인데 이는 계산을 해보면 2^2 + 2^1 = 4 + 2 = 6 이 된다. 짝수 + 짝수 형태로 이루어져 있다는 것이다. 하지만 ! 최하위비트가 '1'이 되는 순간, 홀수가 더해지게 되고, 이 순간 짝수는 짝수가 아니게 된다.

말이 조금 이상한 것 같긴한데, 이런 이유 때문에 짝수들의 최하위비트는 반드시 '1'이 아닌 '0'이 된다는 것이다.

그럼 ! 이 숫자들보다 더 크면서 비트가 1개 or 2개 다른 숫자는 뭐가 있을까 ??

바로 '0'으로 존재하는 최하위 비트를 '1'로 바꿔줘버리면 될 것이다. 왜 이러면 될까 ?? 일단 주어진 숫자의 비트와 비교했을 때 최하위비트를 '0'에서 '1'로 바꿨으니 서로 다른 비트의 갯수가 '1'개가 될 것이다. 그리고 최하위비트를 '1'로 바꾸는 순간, 전체숫자가 바뀌는 형태를 보면 주어진 숫자에서 + 1을 한 형태가 될 것이다.

그렇다면 ! x보다 큰 숫자들 중에서, x + 1보다 작은 숫자는 존재할까 ?? 존재하지 않는다. x보다 큰 숫자들 중에서 x + 1은 가장 작은 숫자에 속하게 된다. 동시에 ! 최하위비트가 '0'에서 '1'로 바뀐 숫자들이기 때문에 f(x)의 조건에 완벽하게 부합하는 결과값이 되는 것이다.

즉 ! 주어진 x가 짝수라면, f(x)의 값은 x + 1이 된다.

# 짝수는 최하위비트가 반드시 '0'인 숫자들인데, 최하위비트를 '1'로 바꾸게 되면 전체 숫자가 x + 1이 되므로
   x보다는 크면서 가장 작은 숫자를 만족하는 동시에 서로 다른 비트의 갯수가 1개가 된다.
# 따라서 주어진 숫자 x가 짝수인 경우 f(x) = x + 1 이 된다.

 

#3 - 1. 나머지 Case.

이제부터는 #2에서 정답을 구할 수 있는 Case가 아닌 나머지 Case들에 대해서 계산을 해보자.

나머지 Case라고 한다면, 아마 주어진 숫자 x가 홀수인 경우에 대한 이야기일 것이다.

먼저 간단하게 하나의 예를 들어보면 '5' = '101' 인데, f(5) = 6 = '110' 이 된다.

이와 같이 홀수 중에서도 단순히 #2 처럼 + 1을 한 값이 정답이 되는 경우도 존재하지만, 모든 홀수에 대해서 이 원리가 적용되지 않기 때문에 #2처럼 간단하게 구할 수는 없다. 지금부터 이 Case들에 대해서 계산을 해보자.

간단하게 '7' , '9' , '11' 로 진행을 해보자. 어차피 주어진 숫자 x가 짝수라면 x + 1이 정답이라는 것을 #2에서 알았기 때문에 홀수인 x들에 대해서 진행해보자. 먼저, 직접하나하나 다 구해보자.

'7' = 0111 → f(7) = 11 = 1011

'9' = 1001 → f(9) = 10 = 1010

'11' = 1011 → f(11) = 13 = 1101

하나하나 직접 구해보면 위와 같이 결과가 나올 것이다.

그럼 이제부터 위의 숫자들을 보면서 특징을 한번 찾아보자. (사실... 별다른 특징이나 공통점은 잘 못찾겠다)

위의 숫자들을 보면, 주어진 숫자 x에서 '0'인 비트가 조금씩 바뀌었다? 라는 것 정도는 찾을 수 있을 것이다.

'7'인 0111에서 '0'이 f(7) = 1011로 '1'로 바뀌게 되었다.

'9'인 1001에서 두번째 '0'이 f(9) = 1010로 '1'로 바뀌게 되었다.

'11'인 1011에서 '0'이 f(11) = 1101로 '1'로 바뀌게 되었다.

파랑색으로 칠한 숫자들이 바뀌었다 정도는 찾아낼 수 있을 것이다.

그리고 한 가지 더 찾아보자.

0111 - 1011

1001 - 1010

1011 - 1101

위에서 빨강색 숫자들에 집중해보자. 모두 바뀐 숫자들이다. 그리고 이 빨강색 숫자들의 특징을 한번 살펴보면, 위에서 이야기한 바뀌게 된 파랑색으로 표시된 '0' 바로 다음 비트에 있는 '1'이라는 것이다. 무슨말인지 모르겠으니 정답부터 알아보고 가자.

주어진 숫자가 홀수인 경우에는 "'0'중에서 가장 최하위비트에 있는 '0'을 '1'로 바꾸고, 그 다음 비트를 '0'으로 바꾸게 되면 f(x)가 나오게 된다" 가 결론이다. 일단 원리, 이유 하나도 모른채로 위의 결론이 맞는지 확인부터 해보자.

7 = 0111 

여기서 0중에서 가장 최하위비트에 있는 0은 가장 앞에 있는 '0'이 된다. 이 '0'을 '1'로 바꾸고, 그 다음 비트를 '0'으로 바꾸게 되면 0111은 1011이 된다. 실제로 f(7)의 값은 11이 된다.

9 = 1001

여기서 0중에서 가장 최하위비트에 있는 0은 파랑색으로 표시한 '0'이 된다. 이 '0'을 '1'로 바꾸고, 그 다음 비트를 '0'으로 바꾸게 되면 1010이 된다. 실제로 f(9)의 값은 10이 된다.

11 = 1011

여기서 0중에서 가장 최하위비트에 있는 0은 가운데 있는 '0'이 된다. 이 '0'을 '1'로 바꾸고, 그 다음 비트를 '1'로 바꾸게 되면

1101이 된다. 실제로 f(11) 의 값은 13이 된다.

위의 결론은 맞아떨어진다. 그렇다면 지금부터 왜 이런 복잡하고도 말도 안되는 원리가 결론이 되는지를 알아보자. 그 이후에 코드로 구현하는 것 까지 이야기를 해보자.

 

#3 - 2. x가 홀수인 경우에 대한 원리

먼저, #3 - 1에서 구한 결론부터 한번 적어놓고 시작해보자.

"'0'중에서 가장 최하위비트에 있는 '0'을 '1'로 바꾸고, 그 다음 비트를 '0'으로 바꾸게 되면 f(x)가 나오게 된다"

먼저, 0중에서 가장 최하위비트에 있는 0을 건드리는 것일까 ?? 이 0이 가진 의미가 무엇인지에 대해서 부터 생각을 해보자.

우리는 주어진 숫자 x보다 큰 숫자들 중에서 비트가 1~2개만 다른 "가장 작은 수" 를 찾는 것이 목표이다.

즉 ! 우리는 가급적이면 작은 숫자를 찾는 것이 유리하다는 것을 의미한다. 그렇다면 ! 어떤 비트를 건드리는 것이 "나보다는 더 크면서 가장 작은 수"를 찾기에 유리할까 ?? '1'인 비트를 건드리는 것은 굉장히 좋지 않은 생각이다.

예를 한번 들어보자. 지금부터 잠시동안만, 비트가 1 ~ 2개 다른 숫자를 찾는 조건은 빼놓고 단순히 나보다 큰 숫자 중에서 가장 작은 숫자를 찾은 것에 포커싱을 맞춰서 이야기 해보겠다.

101 이라는 숫자가 있다. 여기서 '1'인 비트를 한번 바꿔보자.

101을 100으로 바꿧다고 가정해보자. 그럼, 주어진 숫자보다 더 작은 숫자이기 때문에 조건에 위배되어 진다.

101을 001로 바꿨다고 가정해보자. 마찬가지로 주어진 숫자보다 더 작은 숫자이기 때문에 조건에 위배되어 진다.

즉 ! 단.순.히 '1'을 '0'으로 바꾸는 순간, 주어진 숫자보다 더 작은 숫자가 나오게 될 것이다. 그렇기 때문에 '1'인 비트는 건드리지 않는 것이 좋다. 하지만, 우리가 #3 - 1에서는 '1'인 비트도 '0'으로 바꿔주는 과정이 있었다. 이 부분에 대한 구체적인 이야기는 아래에서 더 할 것이다.

그럼, 나보다는 더 큰 숫자를 찾아야 되는데, 가급적이면 그런 숫자들 중에서 가장 작은 숫자이면 좋겠다면 어떤 비트를 건드리는 것이 가장 좋을까 ?? 너무나 당연하게도 '0'중에서 가장 최하위비트에 있는 '0'을 건드리는 것이 가장 좋을 것이다.

예를 한번 들어보자.

1001 이라는 숫자가 있다. 여기서 '0'을 '1'로 바꿔서 나보다 크면서 가장 작은 숫자를 만든다고 생각을 해보자.

우리는 2가지 방법이 있다.

1101 로 바꾸던가, 1011로 바꾸던가. 무슨 숫자가 더 작을까 ? 1011이 더 작은 숫자가 된다.

즉 ! 상대적으로 더 하위에 있는 비트일 수록 그 비트가 가지는 값이 작기 때문에 나보다 크면서 가장 작은 숫자를 찾기 위해서는 주어진 숫자 x를 2진수로 나타낸 비트에서 '0'인 비트들 중에서 가장 최하위에 있는 '0'인 비트를 바꾸는 것이 가장 유리하다는 것이다.

만약에 문제에서의 조건이 "나랑 비트가 딱 1개만 다르면서 나보다 더 큰 숫자들 중에서 가장 작은 숫자를 찾으세요" 라고 했다면, 위의 원리가 답이 될 것이다. "주어진 비트에 존재하는 '0'들 중에서 가장 최하위비트에 있는 '0'을 '1'로 바꾸는 것".

하지만 ! 우리 문제는 비트를 1개 or 2개를 바꾸라고 했기 때문에 위의 원리가 정답이 될 수는 없다.

9 = 1001 인데, 여기서 '0'중에서의 최하위 비트를 '1'로 바꾸게 되면 1011로 '11'이 나오게 되는데, 사실 f(9)의 값은 1010으로 1011이 아니다.

즉 ! 0중에서 최하위 비트인 0을 1로 바꾸게 되면, 나랑 가장 가까우면서도 굉장히 작은편에 속하는 숫자가 나오긴 하지만, 이보다 더 작은 숫자를 만들 수 있다는 것이다. 어떻게 만들 수 있을까 ?? 특정 숫자를 빼버리면 된다.

이게 무슨말일까 ?? 우리는 0중에서 최하위에 존재하는 0을 1로 바꿔주었는데, 이를 다르게 보면 기존의 숫자에서 특정 값만큼을 + 시킨 것과 동일한 효과가 된다.

1001 에서 1011로 바꾸는 순간 기존의 숫자에서 '2'만큼을 더해버린 경우가 되는 것이다.

그런데 우리는 여기서 특정 숫자만큼을 빼더라도 기존의 숫자보다는 크면서도 더 작은 값을 만들어 낼 수 있다.

바로 0중에서 최하위에 존재하는 0을 1로 바꿔주고, 이 바꿔준 0뒤에 있는 '1'을 다시 '0'으로 바꿔주는 것이다.

무슨말일까 도대체 !!!!! 여기까지 내용을 다시한번 정리해보자.

1. 우리는 주어진 숫자 x보다 더 큰 숫자들 중에서 가급적이면 가장 작은 숫자를 찾고 싶다.

2. 그래서 생각해낸 방법이, 주어진 비트에 존재하는 0들 중에서 가장 최하위에 존재하는 0을 1로 바꿔주었다.

3. 하지만 ! 이 과정이 정답은 아니였다. 나보다 더 크면서 더 작은 숫자를 찾아낼 수 있다라는 것만 알고 있다.

우리는 주어진 비트에서 0을 1로 바꾸는 순간, 전체 결과값으로 본다면, 특정 숫자만큼 +한 효과를 가지게 된다고 이야기 했었다.

그렇다면 반대로 1을 0으로 바꾸게 되면 ? 전체 결과값으로 본다면, 특정 숫자만큼 -한 효과를 가지게 될 것이다.

즉 ! 우리는 이 - 효과를 통해서 더 작은 숫자를 찾아낼 것이다. - 효과를 어떻게 만들어 낼건데 ? 비트가 '1'인 값들 중에서 어느 하나를 0으로 바꿔버리면 된다. 그렇게 마음대로 바꿔도 될까 ? 된다. 우린 이미 '0'을 '1'로 하나 바꿔서 기존의 숫자와 다른 비트의 수가 1개가 되었고, 그리고 남은 비트들 중에서 '1'을 하나 선택해서 '0'으로 바꾼다고 해도 기존의 숫자와 다른 비트의 수가 2개가 되기 때문에 문제에 위배되는 상황이 발생하지 않는다.

즉 ! 우리는 주어진 비트 중에서 '1'을 하나 선택해서 '0'으로 바꿔줄 것이다.

그럼 어떤 비트를 선택하는게 가장 유리할까 ?? 우리는 최대한 큰 값을 빼줘야지 최대한 작은 값을 만들 수 있다.

그럼 1001로 해보자. 우리는 이미 1001을 1011로 바꾼 상태이다.

1011에서 '1'인 비트들 중에서 하나를 '0'으로 바꿀 것이다. 한번씩 다 바꿔보자. 그럼 다음과 같이 2가지 경우가 발생한다.

0011

1010

1011에서 1001로 바꾸지 않은 이유는 저 '1'은 어차피 0에서 바뀐 1이기 때문에 다시 0으로 바꾼다면 의미가 없기 때문에 이 경우는 제외하도록 하겠다.

그렇다면, 0011과 1010 2개의 결과값이 발생하게 된다.

그런데 ? 0011은 기존의 숫자인 1001보다 더 작은 숫자이다. 그렇기 때문에 이는 제대로 바꾼것이 아니다.

1010 은 ? 비트도 2개만 다르고, 1001보다 큰 숫자들 중에서 가장 작은 숫자가 된다.

그럼 저 '1'을 어떤 원리에 의해서 선택을 할 수 있을까 ??

원리는 간단하다. 우리가 위에서 '0'인 비트중 하나를 '1'로 바꿔주었다. 즉, 0을 1로 바꿔줌으로써 특정 값 A만큼 +된 효과를 보고 있는 상태이다. 그리고 이 상태에서 '1'인 비트중 하나를 '0'으로 바꿔줌으로써 특정 값 B만큼 -된 효과를 보고 싶은 것이다.

그런데 ! A < B 인 경우를 살펴보자. 주어진 숫자 x에서 'A'만큼을 더하고 'B'만큼 빼주었는데, B가 A보다 더 큰 상황이다.

그럼 당연히 기존의 숫자 x보다 더 작아질 것이다. 5(x) + 2(A) - 3(B) 하게 되면 당연히 5보다 작아지게 된다.

즉 ! 반드시 1을 0으로 바꿀 때에는 A > B 인 경우에만 바꿀 수 있다는 것이다. 그래야지 기존의 숫자보다는 큰 숫자가 유지된다는 것이다. 그럼 A > B를 만족하려면, 어떤 비트를 선택하면 될까 ??

우리가 '0'에서 '1'로 바꾼 '0'중에서 최하위비트에 존재하는 '0'보다 더 하위비트에 있어야만 이게 가능하다는 것이다.

예를 들어서 100111 이 있다. 여기서 우리는 0 중에서 최하위 비트인 0을 1로 바꿀 것이다.

그럼 101111이 될 것이다. 그리고 여기서 '1'인 비트 중에서 하나를 '0'으로 바꿔줄 것이다. 그런데 ! 모든 '1' 중에서 아무거나 선택해도 될까 ?? 안된다. 왜 ? A > B를 만족시켜야 하기 때문이다.

즉 ! 우리가 바꿀 수 있는 후보는 101111 과 같이 빨강색으로 색칠된 '1'들이 된다. 제일 앞에 있는 '1'을 바꾸게되면 A < B가 되어서 기존의 숫자보다도 더 작아지기 때문이다.

그럼 저 빨강색으로 표시된 '1'들 중에서 어떤 비트를 '0'으로 바꾸는게 제일 유리할까 ??

당연히 저 빨강색 1들 중에서 가장 상위비트에 속하는 '1'을 바꿔주는 것이 유리할 것이다. 왜 ?? 그래야지 더 많이 뺄 수 있으니까 !! 101011 이랑 101110 이랑 비교를 해보면 101110이 더 큰 숫자가 된다. 왜 ?? 상대적으로 더 작은 값을 빼줬기 때문이다. 이 복잡한것을 정말 간단하게 이야기하면 다음과 같이 이야기 할 수 있다.

"주어진 비트에서 존재하는 '0'들 중에서 최하위비트에 위치하는 '0'을 '1'로 바꾼 후에, 그 다음 비트를 '0'으로 바꾸기 !"

만약 0들 중에서 최하위비트에 위치하는 0을 1로 바꾸고 그 다음 비트를 0으로 바꾸려고 봤는데 그 다음 비트가 존재하지 않으면 ?? 이런 경우는 존재하지 않는다. 왜 ? 홀수이기 때문에.. #2에서도 이야기했듯이, 짝수는 최하위비트가 반드시 '0'인 반면에, 홀수는 최하위 비트가 '1'이 된다.

즉 ! 어떤 홀수를 가지고 와도 반드시 그 형태가 xxxxxxxxxx1 로 끝난다는 것이다. 따라서, 0들 중에서 최하위 비트에 위치하는 0을 1로 바꿀 때, 이 0의 위치를 생각해보면 아무리 빨라도 '2'의 값을 가지는 비트에 위치한다는 것이다.

"'0'중에서 가장 최하위비트에 있는 '0'을 '1'로 바꾸고, 그 다음 비트를 '0'으로 바꾸게 되면 f(x)가 나오게 된다" 라는 결론이 성립하게 되는 것이다.

# 우리는 주어진 숫자 x보다는 크면서 비트가 1 ~ 2개만 다른 가장 작은 숫자를 찾을 것이다.
# 일단, 주어진 숫자 x보다는 커야 하기 때문에 '0'인 비트 중 하나를 '1'로 바꿔줄 것이다.
# 하지만 ! 그 중에서도 가장 작은 숫자를 찾아야 하기 때문에 '0'인 비트 중에서 최하위비트에 존재하는 '0'을
   '1'로 바꿔줄 것이다.
# 이 상태에서 우리는 더 작은 값을 찾기 위해서, 우리가 바꾼 '0'보다 더 하위비트에 존재하는 '1'들 중에서
   가장 상위비트에 존재하는, 즉 ! 바꾼 0 바로 다음에 있는 비트 '1'을 '0'으로 바꿔줄 것이다.
# 위와 같이 계산을 하게 되면, 주어진 숫자 x와 2개의 비트가 다르고(0을 1로 바꾸고, 1을 0으로 바꿨으므로)
   x보다는 크면서 가장 작은 숫자를 찾아낼 수 있다.

 

#4. 구현

더 나아가서 우리는 이제 이거를 코드로 구현해야 한다.

가장 먼저 우리가 해야될 것이 뭐가 있을까 ?? 아마도 "주어진 비트에 존재하는 '0'들 중에서 가장 최하위비트에 존재하는 '0' 찾기" 가 될 것이다.

주어진 비트 중에서 가장 최하위 '1'인 비트를 찾는 과정은 다음과 같이 구할 수 있다.

Num & (-Num)

위의 식에 대해서 먼저 이야기 해보자.

주어진 숫자 Num이 1001이라고 가정해보자. -Num은 2의 보수를 취한 것과 같다.

2의 보수는 주어진 비트를 모두 반전시키고 + 1을 한 결과값과 똑같다.

1001 을 모두 반전시키면 0110, 0110에 +1을 하게되면 0111이 된다.

최종적으로 1001 과 0111을 &연산을 진행하게되면 0001로 비트 중 최하위에 존재하는 '1'인 비트를 찾아낼 수가 있다.

빨간색으로 표시한 것과 같이, 우리가 찾으려는 비트만 '1'로 표시되어 있다.

그럼 위와 같은 원리를 이용해서 0인 비트 중에서 최하위비트에 존재하는 0을 찾아보자.

위의 최하위 '1'비트를 찾는 과정에서 최종적인 연산 결과만 본다면 &연산을 진행해서, 둘다 '1'인 경우에만 '1'로 표시를 함으로써 1의 위치를 찾아내 주었다.

즉 ! 0인 비트 중에서 최하위비트에 존재하는 0을 찾기 위해서 위와 같은 원리를 적용하게 된다면, 가장 최종적인 단계인 &연산에서 제대로 된 위치를 찾을 수 없다는 것이 너무나도 자명하다. 왜냐하면 0인 비트가 어떤 비트와 &연산을 하더라도 0이 나올게 뻔하기 때문에 위와 같이 구할 수가 없다.

따라서 우리는 최하위 비트에 존재하는 0을 1로 바꿔주고 계산할 것이다. 그래야지 마지막에 &연산을 통해서 뭐라도 구해낼 수 있을 것이기 때문이다. 그럼 그걸 어떻게 할 수 있을까 ? 너무나도 간단하다. + 1을 해주면 된다.

1001 이라는 숫자가 있다. + 1을 하게되면 1010 으로 빨강색으로 표시된 최하위 0인 비트가 1이 되었다.

1000100 이라는 숫자가 있다. + 1을 하게되면 1000101 으로 빨강색으로 표시된 최하위 0인 비트가 1이 되었다.

1010111 이라는 숫자가 있다. + 1을 하게되면 1011000 으로 빨강색으로 표시된 최하위 0인 비트가 1이 되었다.

즉 ! 다음과 같은 수식으로 최하위 0인 비트의 위치를 찾아낼 수가 있다.

(Num + 1) & (-Num)

1001 로 한번 진행을 해보자.

1001 + 1 = 1010

2의 보수를 구하기 위해서 1001을 반전시키면 0110, 0110에서 + 1을 하게 되면 0111.

최종적으로 1010 & 0111을 진행하게 되면 0010 으로 우리가 찾고자 하는 최하위 0인 비트만 1로 표시가 되어 있음을 확인할 수 있다.

그럼 여기서 다시한번 되뇌어보자. 우리가 지금 뭘하고 있을까 ??

"주어진 비트에서 0인 비트들 중에서 최하위에 존재하는 0인 비트를 1로 바꾸고, 그 다음 비트를 0으로 바꿀 것이다"

우리는 이것을 진행하기 위해서 최하위에 존재하는 0인 비트를 찾고 있는 것이다.

그렇다면, 지금까지 우리에게 주어진 값은 원래의 x값인 '1001' 과 최하위 비트를 가르쳐주고 있는 '0010' 이 있다.

그럼 1001에서 최하위비트에 있는 0을 1로 바꾸게 되면 1011이 될텐데, 이걸 1001과 0010으로 어떻게 하면 될까 ?

OR 연산을 진행하면 된다.

1001 | 0010 = 1011 이 될 것이다. 여기까지만 한다면, 0인 비트들 중에서 최하위에 존재하는 0인 비트를 1로 바꾼것이 된다.

그 다음은 ?? 이제 그 다음 비트를 0으로 바꾸는 과정이 남아있다.

즉 ! 지금까지 계산한 1011을 1010으로 바꿔야 하는 상황이다. 어떻게 할 수 있을까 ??

우리가 구해놓은 최하위비트를 가르쳐주는 0010을 통해서 진행할 수 있다.

우리는 바꿔야 하는 비트의 위치를 알고 있다. 우리가 구한 최하위비트를 >> 1 한 곳에 위치한 비트를 바꿔줄 것이다.

최하위비트 >> 1 을 한 비트가 우리가 0에서 1로 바꾼 비트 그 다음 비트일 것이기 때문이다.

이를 바꿔줌과 동시에 나머지 비트들은 자신의 원래 비트를 유지해야 한다.

1011 & 1110 을 진행한다면 1010 이 나오게 될 것이다.

그런데 1110은 어디서 튀어나왔을까 ?? 우리가 구한 최하위비트인 0010을 >> 1 을 한 후에 반전 시킨 것이다.

0010 을 >>1 을 하게되면 0001이 되고 이를 반전시키면 1110이 된다.

이 1110과 우리가 구해놓은 1011을 & 연산을 진행하게 되면, 원래 '1'이 였던 비트와 '0'이 였던 비트들은 모두 그대로 살아남게 되고, 우리가 바꾸고자 하는 '1'인 비트만 '0'으로 바뀌어서 나오게 될 것이다.

최종적으로 코드를 보면 다음과 같다.

			long long LastZero = (Num + 1) & (-Num);
			long long Result = (Num | LastZero) & (~(LastZero >> 1));

 

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
vector<long long> solution(vector<long long> numbers) 
{
    vector<long long> answer;
    for (int i = 0; i < numbers.size(); i++)
    {
        long long Num = numbers[i];
        if (Num % 2 == 0) answer.push_back(Num + 1);
        else
        {
            long long LastZero = (Num + 1) & (-Num);
            long long Result = (Num | LastZero) & (~(LastZero >> 1));
            answer.push_back(Result);
        }
    }
    return answer;
}