입력

1. 32비트 정수, 예: 147 혹은 -932 혹은 680


출력

1. 각 숫자를 뒤집음. 예: 741 혹은 -239 혹은 86 (086인데 0을 없애고 걍 86만 찍힘)


조건

1. 32비트 정수이므로, 표현할 수 있는 값의 범위가 [-2^31, 2^31 - 1]인데, 만일 뒤집은 수가 이 범위 안에 있지 않으면 overflow 이므로 0을 출력.




가장 쉬운 방법은 양수일 경우 10으로 나눈 나머지와 몫을 구해서 나머지를 제일 앞에 놓고, 몫은 다시 10으로 나눠서 나머지를 계산하고, 이를 반복. 음수면 양수로 바꾼 후 위 알고리즘을 쓰고, 나중에 음수로 전환만 하면 됨.


overflow는 원래 숫자의 자릿수와 MAX, MIN값만 알고 있으면 overflow 처리는 쉬울테고...




이거 말고 다른 쌈박한 알고리즘이 있을까 잠깐 생각해봤는데, 쉽지가 않음. 당장 4~6비트 unsigned integer만 생각해봤는데도 숫자를 나열해보면 규칙성 같은게 안보임.


그래서 좀 더 생각을 해본게, 그럼 어떤 양수가 주어졌을 때 10으로 나눈 나머지를 구하는 알고리즘은 쉬울까? 였음. (이게 쉬워야 위 계산을 빠르게 할 수 있을 것 같으니..) 일반적인 나머지 계산은 나눗셈 계산과 같이 움직이므로 시간이 오래 걸리는데 (정수 나눗셈 계산에 걸리는게 64비트의 경우 대략 7~13 클럭 사이클로 알고 있음), 10이란 특정 숫자로 나누는 경우엔 특별한 알고리즘이 있을까? 에 대한 질문이 들었음.


그런데 생각을 해보면, 주어진 32비트 숫자의 각 자리에 대한 weight는 LSB부터 시작하면 1, 2, 4, 8, 16, .... 이고, 우리는 10으로 나누는 것에만 관심이 있으니까 결국 1 2 4 8 6 2 4 8 6 2 4 8 6 이게 계속 반복임. 즉, 10으로 나누는 나머지 계산만 하려고 해도, 모든 비트들이 다 계산으로 들어오고, 첫번째 비트 (1에 해당하는..)만 빼고 보면 2486 2486 이렇게 반복되니까, 비트4~1, 비트8~5 이렇게 묶어보면

0000 -> 10으로 나눈 나머지는 0

0001 -> 10으로 나눈 나머지는 2

0010 -> 4

0011 -> 6

0100 -> 8

0101 -> 0

0110 -> 2

0111 -> 4

1000 -> 6

1001 -> 8

1010 -> 0

1011 -> 2

1100 -> 4

1101 -> 6

1110 -> 8

1111 -> 0


이렇게 됨. 따라서 비트를 (30-29), (28-25), (24-21), (20-17), (16-13), (12-9), (8-5), (4-1), (0) 이렇게 쪼갠후, 위의 Lookup table을 이용하여 각 4자리씩에 대한 1의 자리의 수를 알아낼 수가 있음 (31번째 비트는 0이라고 가정 = 양수). 예를 들어, 주어진 수가


011 1011 1110 0000 1100 0000 1101 0101 1 이라고 가정하면

(30-29) = (00)11 => 6

(28-25) = 1011 => 2

(24-21) = 1110 => 8

(20-17) = 0000 => 0

(16-13) = 1100 => 4

(12-9) = 0000 => 0

(8-5) = 1101 => 6

(4-1) = 0101 => 0

(0) = 1 => 1

그러므로 이 1의 자리의 수를 다 더하면 27 (=1101 1)이 나오고, 똑같은 논리를 적용하면

1101 => 6

1 => 1

더하면 7

따라서 나머지는 7이 나옴. (저 값을 10진수로 변환해보면 2,009,170,347 이므로 확인.)


즉, 각 4자리를 00...011110...0 으로 bit masking 하고, shift 하여 LSB 4비트로 만든후, 위의 lookup table을 이용해서 그들의 1의 자리의 수를 알아낸 후, 이를 다 더하고 (이의 최대값은 65 = 1000001), 이를 한 번 더 적용하면 (이의 최대값은 9), 바로 10으로 나눈 나머지를 알 수 있음. bit masking이랑 shifting도 시간이 걸리니까 이게 일반적인 나눗셈보다 빠르다고 볼 수는 없을지라도, 하드웨어로 만들게 되면 이거 1~2사이클에 계산 가능함.


근데 이거 한다고 10으로 나눈 몫을 계산하는건 또 다른 문제 같고..


결과적으로 걍 무식하게 10으로 계속 나누고, 나머지를 구해서 reverse하는게 가장 속편하면서도 쉬운듯? ..