알고리즘 엔디안(C++)

간만에 알고리즘풀이. 

1419 : 엔디안

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 293 회    시도횟수: 746 회   

Lilliput의 사람들은 삶은 계란을 먹을 때 계란의 넓은 쪽부터 깨야 한다는 Big Endian파와 좁은 쪽부터 깨야 한다는 Little Endian 파로 나뉘어서 싸우고 있었다.

이 싸움은 삶은 계란 뿐만 아니라 생활 속의 다른 분야에까지 확대되었는데, 그 중 대표적인 것으로 컴퓨터에서 사용하는 데이터의 저장 방법이다.

Big Endian 파에서는 숫자를 저장할 때 위쪽 바이트부터 먼저 저장하는 방식이 옳다고 주장하였으며, Little Endian 파에서는 아래쪽 바이트부터 먼저 저장하는 방식이 옳다고 주장하였다.

예를 들어 32bit unsigned int 305,419,896 (0x12345678)을 Big Endian과 Little Endian으로 나타내면 다음과 같다. 
00010010 00110100 01010110 01111000 (Big Endian) 
01111000 01010110 00110100 00010010 (Little Endian)

이 들은 각자 자신이 주장하는 방식으로 컴퓨터를 만들어서 사용하였는데, 두 파의 사람들이 서로 데이터를 주고 받을 필요가 있을 경우 (항상 싸우기만 하는 것은 아니다.) Big Endian으로 저장된 데이터를 그대로 Little Endian 방식으로 읽었을 경우, 또는 반대의 경우에는 이상한 값이 되어버리기 때문에 Endian의 변환이 필요해진다. 예를 들어 위 예제의 Big Endian의 값을 그대로 Little Endian 방식으로 읽었을 경우 2,018,915,346 (0x78563412)이 된다.

이 들은 자신이 Endian을 변환해서 데이터를 보내주는 것을 원하지 않았기 때문에 일단 데이터를 받은 후에 자신들이 사용하는 Endian에 맞춰서 변환해야 한다. 당신은 이들을 도와 Endian을 변환하지 않고 받은 데이터를 원래의 데이터로 복원해주는 프로그램을 작성해야 한다.

 

입력은 하나의 숫자 (32bit unsigned int)로 이루어지며, 이는 Endian을 변환하지 않고 받아들인 데이터이다.

입력에 대한 원래 데이터를 출력한다.

[Copy] 2018915346

[Copy] 305419896

출처 : uva

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/**************************************************************     Problem: 1419     User: a132034     Language: C++     Result: Success     Time:1 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std; #define byte 256   int main() {     unsigned int input;     cin >> input;       int a = input % byte;     int b = (input >> 8) % byte;     int c = (input >> 16) % byte;     int d = (input >> 24) % byte;       cout << (unsigned int)(a << 24) + (b << 16) + (c << 8) + (d) << endl;     return 0; }

일단 int로 하면 32bit unsigned int이기 때문에 -값이 될 수도 있으므로 모든걸 unsigned int로 하면 편할 것 같다. 

풀고나니 왜 저렇게 a,b,c,d를 int로 하고 결과는 또 형변환을 하고 그랬는지 잘 모르겠다...

a,b,c,d는 각 바이트이다. 

input을 d c b a라고 할 때 a b c d로 변환하면 된다. 

비트연산을 활용하면 아주 간단한데 1byte는 8bit이기 때문에 8bit 단위로 a,b,c,d에 저장해 두고 

결과를 출력할 때 입력과 반대순서로 각 위치에 넣어주면 된다. 

간단하게 비트연산에 대해 위 문제의 예제를 들면

1. 00010010 00110100 01010110 01111000 (Big Endian) 
2. 01111000 01010110 00110100 00010010 (Little Endian)

이 있을 때 

1번을 >>8 연산을 하게 되면

00010010 00110100 01010110 01111000 => 00000000 00010010 00110100 01010110 

총 8개의 비트가 왼쪽에서 오른쪽 방향으로 추가되며 가장 오른쪽 8개 비트가 사라진다. 이는 256으로 나누는 효과가 있다. 

2번을 <<16 연산을 하게 되면 

01111000 01010110 00110100 00010010 => 00110100 00010010 00000000 00000000

총 16개의 비트가 오른쪽에서 왼쪽 방향으로 추가되며 가장 왼쪽의 16개 비트가 사라진다. 이는 2^16으로 곱한 효과가 있다(256*256)

byte는 왜 define했던지 기억이 잘 안난다... 초반에 고민하다가 했던것 같은데..

다른 연산들은 차근차근 손으로 쓰면 어렵지 않을 것 같다.