이번 문제에서는 32bits 정수 n과 m이 주어지고 n의 인덱스 i, j가 주어진다. n의 i번째에서 j번째 사이의 bit들을 m의 bit들로 바꾸는 것이다. 예를 들어 n=11010이고 m=11인데, i=2이고 j=3이면 1[11]10이 된다. 물론 인덱스는 0에서 부터 시작하고 2^0을 나타내는 bit 위치가 index=0이다. (이런게 least significant bit인가?) 참고로 j>=i이다.
대략 알고렝이(알고리즘)를 보면 (a) n에서 m이 들어갈 위치를 0으로 만들어주고 (1[00]10), (b) m을 해당 위치만큼 좌측으로 shift해주고 ([11]00), 두 값을 or 연산 해주면 된다. 전자 (a)의 경우는 0이 되어야 할 자리에 1만 있는 값 ([11]00)을 만들고, 이를 모든 binary값으로 모든 자리가 1인 (~0) 값과 xor 연산을 해주고 (111~~11[00]11), 이를 다시 n 값과 and 연산을 하면 원하는 값이 나온다. (1[00]10).
정말 이런 쪽으로 머리가 나쁜 것 같단 생각이 든다. 예전부터 recursion이 머리로 이해가 안되고, dynamic programming이 이해가 안되던게 이런 쪽으로 머리가 너무너무 나빠서 그런가보다. 뭐, 다른 분야에 재능이 있을지도 모르겠지만, 내가 잘 해야하는/했으면 부분에서 이렇게 고생하며 자학(?)하게 되니 참 난감하다.
대략 알고렝이(알고리즘)를 보면 (a) n에서 m이 들어갈 위치를 0으로 만들어주고 (1[00]10), (b) m을 해당 위치만큼 좌측으로 shift해주고 ([11]00), 두 값을 or 연산 해주면 된다. 전자 (a)의 경우는 0이 되어야 할 자리에 1만 있는 값 ([11]00)을 만들고, 이를 모든 binary값으로 모든 자리가 1인 (~0) 값과 xor 연산을 해주고 (111~~11[00]11), 이를 다시 n 값과 and 연산을 하면 원하는 값이 나온다. (1[00]10).
#include <iostream>
using namespace std;
int insertMiddle(int n, int m, int i, int j) {
int n1 = (((1 << (j - i + 1)) - 1) << i);
int n2 = (n & (~0 ^ n1));
int n3 = n2 | (m << i);
return n3;
}
int main() {
cout << insertMiddle(26, 3, 2, 3) << endl;
cout << insertMiddle(1024, 21, 2, 6) << endl;
}원리도 간단하고 소스도 간단한데, 원리를 파악하고도 단지 이 3줄의 핵심 코드를 짜는데 (물론 한 줄로도 되겠지만) 1시간이 넘게 걸렸다. 예제 binary 값을 십진수로 바꿔서 함수의 인자로 넣는데 그 십진수를 잘못 계산해서 삽질하는 등등. 이 정도는 5분이면 짜내야 하는 것 아닌가 싶은데 정말 머리에 방법이 떠오르더라도 그걸 코드 한 줄로 옮기는 데 오류가 너무 많다. 정말 이런 쪽으로 머리가 나쁜 것 같단 생각이 든다. 예전부터 recursion이 머리로 이해가 안되고, dynamic programming이 이해가 안되던게 이런 쪽으로 머리가 너무너무 나빠서 그런가보다. 뭐, 다른 분야에 재능이 있을지도 모르겠지만, 내가 잘 해야하는/했으면 부분에서 이렇게 고생하며 자학(?)하게 되니 참 난감하다.
'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글
| [CS] 연결 리스트 뒤집기 (Reverse Linked List) (6) | 2010/02/28 |
|---|---|
| [CS] 퀵 정렬 (Quick Sort) (2) | 2010/02/22 |
| [CS] 비트 매스크(Bit Mask) (2) | 2010/02/21 |
| [CS] 반복되지 않는 첫번째 문자를 찾아라 (3) | 2010/02/19 |
| [CS] 16진수를 10진수로 바꾸어보자 (0) | 2010/02/18 |
