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;
}


반응형

+ Recent posts