리센룽 싱가포르 총리의 문제
10 May 2015
x & -x
얼마전에 리센룽 싱가포르 총리가 Founders Forum에 참석하여 스도쿠 프로그램을 만든 것을 보여주면서 ‘Here’s a question for those reading the source code: if x is an (binary) integer, what does (x & -x) compute?’ 질문을 던졌습니다.
무심코 보다가 결과가 x가 나올 것이다고 생각하고 넘겼는데 곰곰히 생각하다가 우선 코드를 돌려봤더니 전혀 다른 결과가 나왔습니다.
그래서 어라? 뭔가 잘못됬다라고 생각하여 다시금 돌아보게 되었습니다.
컴퓨터에서는 음수를 2의 보수로 처리합니다. 12(0_1100_2)라는 값은 음수로 변경시 1의 보수로 변경하고(1_0011_2) 1을 더하게 됩니다.(1_0100_2)
따라서 12는 0_1100_2, -12는 1_0100_2가 됩니다. 이를 And 연산을 통하면 0_0100_2가 됩니다.
이는 우측의 가장 끝자리 값을 취하게 됩니다.(rightmost 1-bit)
리센룽 총리는 이 문제를 it is an old programming trick.라고 하였지만 가장 기초적이고 원론적인 문제가 아닌가 싶습니다.