Programming world

#define SWAP(x, y) {(x)^=(y)^=(x)^=(y);}

위와같은 SWAP 매크로가 있다.

이제 이 매크로를 한번 풀어 보겠다.

int main()
{

int x = 10;
int y = 20;

printf("X = %d, Y = %d", x, y);

x ^= y ^= x ^= y;  //SWAP(x, y);

printf("X = %d, Y = %d", x, y);

return 0;

}

위과 같이 매크로가 풀릴것인데... 이것을 하나씩 뜯어보면

제일 뒤에것 부터 x ^= y;

이걸 다시 풀어쓰면 x = x^y;

자 그럼 x와 y를 2진수로 풀어 보겠다.

x : 00001010 (10진수 : 10)
y : 00010100 (10진수 : 20)

^모양은 XOR하란 말이므로 위의 두 2진수를 XOR 시키면

x^y = 00011110

그럼 이 값이 x에 들어갔을 것이다.

그럼 다음인 y ^= x;

이것도 다시 풀어쓰면 y = y^x;

x : 00011110
y : 00010100

XOR 시키겠다.

y^x = 00001010

이 값 또한 y에 들어가게 된다.

이제 마지막으로 x ^= y;

풀어보면 x = x^y;

x : 00011110
y : 00001010

XOR 시키겠다.

x^y = 00010100

x에 마지막으로 값이 들어 갔다.

그럼 최종적인 값을 확인해 보겠다.

x : 00010100 (10진수 : 20)
y : 00001010 (10진수 : 10)

자 어떤가...

추가적인 변수 없이 비트연산만으로 SWAP구현이 가능하다.

보기쉽게 코드화 하면

x = x ^ y;
y = y ^ x;
x = x ^ y;

과 같이 쓸 수 있다.


또하나의 방법을 보겠다.

x = x + y;
y = x - y;
x = x - y;

이정도는 +, - 만 할줄 안다면 풀이가 가능하니

풀이는 하지 않겠다...

이처럼 여러가지 방법으로 추가적인 변수 없이 SWAP 구현이 가능하다.

1. 임시 변수 없는 SWAP 매크로

#define SWAP(a, b) {(a)^=(b)^=(a)^=(b);} 


2. 주어진 수가 2의 제곱수(1, 2, 4, 8, 16 등등)인지 검사(출처: flipCode)

inline bool IsPow2(int v)
{
    return (!(v & (v - 1)));
}


3. 0이 아닌 비트들의 개수 세기...(예를 들어 0xf0는 4개..)(출처: flipCode)

8비트용:
v = (v & 0x55) + ((v >> 1) & 0x55);
v = (v & 0x33) + ((v >> 2) & 0x33);
return (v & 0x0f) + ((v >> 4) & 0x0f);

32비트용:
#define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001
#define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111


v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);
v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);
return (v + (v >> 9) + (v >> 1 + (v >> 27)) & 0x3f;