[programmers][월간 코드 챌린지 시즌2] 2개 이하로 다른 비트

문제 : https://programmers.co.kr/learn/courses/30/lessons/77885

---

xxxx0 -> xxxx1

만약 마지막 비트가 위와 같이 0 이라면 마지막 비트만 1로 바꾸면 정답을 구할 수 있다.

마지막 비트가 0인경우는 짝수인 수이므로 numbers[i]가 짝수인 경우 + 1이 정답이된다.

 

문제는 마지막 비트가 1인 홀수인 경우이다.

1000111 를 예로 들어보자.

홀수인경우는 0인 비트 중 최하위 비트를 찾는다.

위 경우엔 8에 해당하는 오른쪽에서 4번째 비트가 이에 속한다.

정답이 되는 비트는 1001011 이다. 즉, 0인 비트중 최하위비트는 1로 바꾸고 그 다음 비트는 0으로 바꿔주면 정답을 구할 수 있다. numbers[i]보다는 커야하고(조건 1) 최대 2개 비트를 바꾸면서(조건 2) 가장 작은 수를 구해야(조건3)하므로 0비트중 최하위비트를 1로 바꾸는게 (조건1)을 충족시키고 (조건 2, 3)을 충족시키기 위해 그 다음 비트를 0으로 바꿔주는 것이다.

 

아이디어는 위와 같고, 0 비트의 최하위 비트를 어떻게 구하는지 생각해보자.

 

1, 2년 전쯤 알고리즘 스터디할 때 정리한 것. (상세 내용은 종만북 2권 16챕터 참고)

이 중 최하위 비트 구하는 공식을 쓰면 된다. A & -A

왜 이게 최하위 비트를 구하는지 예시로 살펴보면, let, A = 101100 이라 하면, -A(A의 2의 보수) = 010100이고 이를 & 연산하면 000100 이다. 2의 보수가 A를 Not한 다음 + 1을 한 결과이므로 최하위 비트를 알 수 있다.

 

위 공식은 1비트의 최하위 비트를 구하는것이기때문에, 위 공식을 쓰기위해 NOT연산한 결과를 A라 보고 공식을 적용하면 최하위 0비트를 구할 수 있다. (A = ~numbers[i]) 이를 lastBit라 하자.(1000(2)). lastBit를 1로 만들어줘야 하므로 numbers[i]에 OR 연산해준다.

그 다음 비트는 lastBit를 오른쪽으로 한 칸 옮긴게 되고 이는 lastBit >> 1 이다.(100(2)) 해당 비트를 0으로 만들어야 하기 때문에 NOT연산을 한 결과를 AND 연산해준다. & (~(lastBit >> 1))

 

unsigned long long lastBit = ~number & (number + 1); 
answer[i] = (number | lastBit) & ~(lastBit >> 1);

주요 코드 참고.

 

비트 연산은 O(1)로 해결되기 때문에 총 시간복잡도는 O(|numbers|).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C2/2%EA%B0%9C%20%EC%9D%B4%ED%95%98%EB%A1%9C%20%EB%8B%A4%EB%A5%B8%20%EB%B9%84%ED%8A%B8.cpp

---

비트 문제 재밌다.