http://www.algospot.com/judge/problem/read/ENDIANS
위 문제를 풀기 위해서 기본 사항들에 대해서 공부를 해보기로 했다.
이런 공부를 해본지 벌써 10여년 이상이 흘러버린 것이 좀 슬프게 느껴진다.
어휘들은 낯이 익지만 그 의미는 가물가물한 단계를 넘어 다른 사람에게 설명을 할 수가 없는 지경이...
□ Little-Endian, Big-Endian
- 메모리에 저장된 바이트들의 순서에 대한 용어
▷ Big-Endian
* 바이트 열에서 가장 큰 값이 먼저 저장
* RISC 기반 프로세서, 모토로라 프로세서
* 확장 축소에 효율적
* 수의 값을 증가시킬 때 왼편에 자릿수 추가 가능
▷ Little-Endian
* 바이트 열에서 가장 작은 값이 먼저 저장
* 인텔 프로세서, DEC의 알파 프로세서
* 오른쪽에서 왼쪽으로 읽는 언어를 사용하는 사람에게 자연스러운 방식
| Type |
Name |
Size |
Value |
Big-Endian |
Little-Endian |
| BYTE |
b |
1 |
0x12 |
[12] |
[12] |
| WORD |
w |
2 |
0x1234 |
[12][34] |
[34][12] |
| DWORD |
dw |
4 |
0x12345678 |
[12][34][56][78] |
[78][56][34][12] |
| char [] |
str |
6 |
"abcde" |
[61][62][63][64][65][00] |
[61][62][63][64][65][00] |
▷ 위키피디아에 너무나 좋은 그림이 있어서 이것도 추가해본다.
*
http://en.wikipedia.org/wiki/Endianness
- 당연히 모두 알고있겠지만, char []의 경우에는 제일 끝에 null이 들어가게 되고, 순서의 바뀜이 없다.
- MSB, LSB
▷ MSB (Most Significant Bit) : 최상위 비트. 이진수 숫자 중에서 제일 큰 자리수
▷ LSB (Least Significant Bit) : 최하위 비트. 이진수 숫자 중에서 마지막 자리수
(MSB) 0x12345678 (LSB)
▷ MSB First System → 12 34 56 78
▷ LSB First System → 78 56 34 12
- 용어만 다를 뿐이지, 결국은 같은 이야기이다.
▷ Little Endian = LSB First
▷ Big Endian = MSB First
- 이 단어들은 걸리버 여행기에서 나오는 이야기에서 유래가 되었다고 한다.
▷ 삶은 계란을 깰 땨애 뾰족한 쪽(Little-endian)으로 깨야한다는 릴리풋(Lilliput) 국과
둥근 쪽(Big-endian)으로 깨야한다는 비에푸스쿠(Biefuscu) 국이 전쟁을 일으켰다는...
- 또, 당연한 이야기이지만 Big-endian, Little-endian 모두 같은 값을 표한하기 위한 다른 방법일 뿐이다.
□ 시프트 연산 (Shift Operations)
- 앞서 살펴본 Big-endian, Little-endian을 프로그램으로 구현할 때에 주로 사용하는 것이 바로 시프트 연산 !
- 우선은 C/C++ 언어에서의 시프트 연산을 기준으로 해서 알아보자.
▷ 기본적인 문법은 다음과 같다.
* 데이터 << 이동할 비트 수
* 데이터 >> 이동할 비트 수
▷ 하나 샘플로 해보자.
* int number = 5;
* int result = number << 3;
* 5를 2진수로 하면... 101
* 왼쪽으로 3번 시프트 연산을 하면... 101000
* 그러므로... result 결과는 40
* result = result >> 1;
* 101000 ... 이걸 오른쪽으로 1번 시프트하면... 10100
* 이건... 결과로 20
▷ 시프트 연산을 하다보면 두 가지 상황에 대해서 잘 생각해보아야 한다.
▷ 제일 왼쪽의 비트가 부호 비트인데, 부호 비트까지 왼쪽 시프트가 이루어지는 경우와
▷ 오른쪽 시프트가 이루어지다가 버림이 벌어지는 경우가 그것인데...
▷ 왼쪽 시프트
* 값이 2배씩 증가를 한다.
* 음수여서 부호비트가 1인 경우 바로 0으로 바뀌어서 양수로 되기도 하고,
양수의 값이 시프트 되다가 갑자기 음수로 바뀔 수도 있다.
* 제일 오른쪽은 "0"으로 채워진다.
▷ 오른쪽 시프트
* 값을 2의 제곱으로 나누기를 한다.
* 제일 왼쪽은 부호비트로 채워진다. 음수이면 계속 1이 들어온다.
* 제일 오른쪽으로 넘어오는 값들은 그냥 그대로 버려진다.
- 시프트 연산에 있어서는 Python에서도 기본적인 문법은 동일하다.
□ 비트 연산 (Bit Operations)
- 본래 시프트 연산 역시도 비트 연산에 포함이 된다.
- 시프트 연산 외에 지금 살펴볼 비트 연산자는 "and", "or", "xor" 3가지 이다.
- 여기에서 일일이 하나씩 설명하지는 않겠다.
- 비트 단위로 연산이 이루어지는 것이며, 문법은 다음과 같다.
* and : &
* or : |
* xor : ^
□ 함수 구현
- 일단은 문제를 검증하기 위한 코드 작성
#include <stdio.h>
#include <stdint.h>
uint32_t to_little(uint32_t bits32)
{
unsigned char bytes[4];
uint32_t ret;
bytes[0] = (unsigned char)((bits32 >> 0) & 0xff);
bytes[1] = (unsigned char)((bits32 >> 8) & 0xff);
bytes[2] = (unsigned char)((bits32 >> 16) & 0xff);
bytes[3] = (unsigned char)((bits32 >> 24) & 0xff);
ret = ( (uint32_t)bytes[0] << 0 ) |
( (uint32_t)bytes[1] << 8 ) |
( (uint32_t)bytes[2] << 16 ) |
( (uint32_t)bytes[3] << 24 );
return ret;
}
uint32_t to_big(uint32_t bits32)
{
unsigned char bytes[4];
uint32_t ret;
bytes[0] = (unsigned char)((bits32 >> 0) & 0xff);
bytes[1] = (unsigned char)((bits32 >> 8) & 0xff);
bytes[2] = (unsigned char)((bits32 >> 16) & 0xff);
bytes[3] = (unsigned char)((bits32 >> 24) & 0xff);
ret = ( (uint32_t)bytes[0] << 24 ) |
( (uint32_t)bytes[1] << 16 ) |
( (uint32_t)bytes[2] << 8 ) |
( (uint32_t)bytes[3] << 0 );
return ret;
}
int main()
{
uint32_t i = 2018915346;
printf("[ %u ]\n", i);
printf(" %u\n", to_little(i));
printf(" %u\n", to_big(i));
i = 1;
printf("[ %u ]\n", i);
printf(" %u\n", to_little(i));
printf(" %u\n", to_big(i));
i = 100000;
printf("[ %u ]\n", i);
printf(" %u\n", to_little(i));
printf(" %u\n", to_big(i));
i = 4294967295u;
printf("[ %u ]\n", i);
printf(" %u\n", to_little(i));
printf(" %u\n", to_big(i));
return 0;
}
