nlogn's log :: 천천히 달리기

비트 연산자

비트 연산자는 비트 중심으로 연산할 때 사용하는 연산자입니다. 비트(bit)란 정보를 저장하는 가장 작은 단위로 그 값은 0이나 1입니다. 비트 조작은 가장 낮은 단계에서 시스템을 조작해야 할 경우에 필요하기 때문에 그런 부분까지 제어할 필요가 없다면 이 부분은 가볍게 읽거나 건너뛰어도 됩니다. 자바스크립트에서는 시스템 제어보다는 주로 암호나 인코딩을 위해 사용합니다.

여덟개의 비트가 연달아 있는 것을 바이트(byte)라고 합니다. 즉 1바이트는 8비트입니다. 8비트로 표현할 수 있는 수의 종류는 256(2⁸)가지입니다. C나 C++, 파스칼처럼 문자 유형을 지원하는 프로그래밍 언어에서는 한 바이트가 한 글자를 나타냅니다. 
(여기에서의 한글자는 영문 한글자를 가리킵니다. 한글 한 글자를 표시하기 위해서는 2바이트가 필요합니다)

16진수는 각 자리가 4개의 이진 비트로 구성되기 때문에 이진 데이터를 표현할 때는 16진법이 가장 적당합니다. 아래 표는 0에서 F까지의 16진수 값과 그에 해당하는 2진수 값을 정리한 것입니다.

비트 연산자를 사용하면 데이터 비트별로 작업할 수 있습니다. 비트 연산자는 다음과 같습니다.

비트 AND

비트 AND 연산자는 두 개의 비트를 비교하는 것인데, 두 개의 비트가 모두 1일 경우에만 결과값이 1이 됩니다. 

예를 들어 16진수 23과 72에 비트 AND 연산자를 사용하면 다음과 같습니다.

비트 AND 연산자는 어떤 숫자가 짝수인지 홀수인지 테스트할 때 많이 사용합니다. 2진수로 표현했을 때 홀수의 맨 마지막 비트는 1이고 짝수의 맨마지막 비트는 0입니다. 따라서 맨 마지막 비트의 값과 1을 비트 AND 연산했을 때 결과값이 1이면 홀수이고 0이면 짝수가 될 것입니다. 간단히 함수로 표현하면 다음과 같습니다.

function checkEven(myNumber) { // 짝수 체크 함수
    return (myNumber & 1 == 0) // 1과 비트 AND 연산했을 때 0이면 반환
}

비트 OR

OR 연산자는 배타적 OR 연산자라고도 하는데, 두 피연산자를 비교해서 최소한 하나만 1이면 결과값은 1이 됩니다.

다음은 연산  예입니다.

비트 XOR

비트 XOR는 (XOR를 읽을 때는 익스클루시브 OR로 읽음) 연산자는 피연산자 중 한 비트가 1이면 1을 반환하고 두 피연산자가 같으면(즉, 0과 0이거나 1과 1일때) 결과값이 0이 됩니다.

아래 연산은 비트 XOR 연산의 예입니다.

비트 XOR 연산자는 XORing이라고 하는 간단한 암호 기법에서 사용합니다.

비트 NOT

비트 NOT 연산자는 피연산자 값의 반대값을 반환합니다. 그래서 이 연산자를 비트 플립 연산자(bit flip operator)라고도 부릅니다. 1은 0으로, 0은 1로 바꿉니다.

예를 들어볼까요?

~ 00000000000000000000000001000110₍₂₎  ☜ 70

    11111111111111111111111110111001₂  ☜ -71

주의 : 이 연산자는 모든 피연산자를 32비트로 사용합니다. 32비트가 아닌 정수를 사용한다면 자동으로 32비트로 만들어진 후 연산합니다.

시프트 연산자

시프트 연산자에는 두 가지 피연산자가 있습니다.

• 이동시킬 값

• 첫번째 피연산자를 이동시킬 비트 위치(숫자)

시프트 연산자는 피연산자를 32비트 정수로 바꾼 후 같은 유형의 결과값을 반환합니다. 시프트 연산자는 세 가지 종류가 있습니다.

• 왼쪽 시프트 (<<)

• 오른쪽 시프트 (>>)

• Zero-fill right shift (>>>)

① Left shift

왼쪽 시프트 연산자는 왼쪽에 있는 피연산자1을 피연산자2에서 지정한 비트수만큼 왼쪽으로 이동합니다. 모든 비트가 하나씩 왼쪽으로 이동하고 나면 오른쪽 맨 끝에 한자리가 비는데 이 자리는 0으로 채워집니다.

이제 179를 왼쪽으로 2비트만큼 이동시키면 716이 된다는 것을 알게 되었습니다. 일반적으로 x << n(x를 왼쪽으로 n비트만큼 이동)를 계산하면 x * 2ⁿ와 같습니다. 위에서 살펴본 179 << 2의 경우에도 179 * 2² = 716입니다. 이 규칙은 음수의 경우에도 똑같이 적용됩니다.

오른쪽 시프트

오른쪽 시피트 연산자는 피연산자의 부호를 그대로 유지합니다. 왼쪽 시프트 연산자와 마찬가지로 첫번째 피연산자를 두번째 피연산자크기만큼 오른쪽으로 이동시킵니다. 오른쪽으로 이동하면서 넘어간 숫자들은 무시됩니다. 정수의 부호는 첫번째 부호에 저장되는데 부호를 그대로 유지하려면 첫번째 비트는 그냥 두어야겠죠? 그리고 나머지 31개의 비트만 오른쪽으로 이동시키면 됩니다. 오른쪽으로 이동시킨 후 왼쪽에 새로 생기는 비트들은 부호 비트에 따라 0이나 1이 저장됩니다. 부호 비트가 0이면 새로운 비트들을 모두 0으로 채우고, 부호 비트가 1이면 새로운 비트를 1로 채웁니다.

음수일 경우에는 어떻게 될까요?

※ 참고1 : -17을 이진수로 표현하려면 일단 17을 2진수로 표현한 후(10001) 각 비트마다 2의 보수 값을 구하고 그 결과에 1을 더하면 됩니다.

① 17에 대한 2진수 구함 : 10001
② 2의 보수로 바꿈 : 01110
③ 1을 더함 : 01110+1 → 01111
④ 따라서 -17은 11...101111

※ 참고2 : 11....1101을 10진수로 표현하려면...

① 맨 앞 비트가 1이므로 음수임을 알 수 있다
② 10진수로 바꾸기 위해 2의 보수로 변환 : 000..0010
③ 1을 더함 : 0010 + 1 → 0011 → 3
④ 원래 음수였으므로 -3

오른쪽 이동 후 0으로 채우기

이 연산자는 오른쪽 시피트 연산자와 똑같이 동작하는데 단, 오른쪽으로 이동한 후 새로 생기는 왼쪽의 빈 비트를 0으로 채운다는 점만 다르답니다. 따라서 양수일 경우 오른쪽 시프트했을 경우와 결과값이 같지만 음수일 경우 전혀 다른 값이 나오게 됩니다.

시리니 님의 글을 읽고 필 받아서 확인했습니다. 무슨 글이냐고요? 입력된 수가 소수인지 아닌지를 판별하는 알고리즘에 관한 글이었습니다. 시리니 님의 글에 의하면,

입력한 수 n 이 n 이외의 정수로 나눠서 떨어지면 그 수는 소수가 아닙니다.

수학자들의 증명에 의해, n 대신에 root n 부터 위 1의 과정을 거쳐도 결과는 동일합니다.

루프를 돌면서 어떤 수에 나눠떨어지면 루프를 탈출해 소수가 아님을 알 수 있습니다.

이런 규칙에 의해 소수인지 아닌지를 알 수 있다고 합니다. 1번과 3번은 제 글에 쓰인 알고리즘과 동일하죠. 그런데 2번이 유독 눈에 띄더군요. 생각도 못한 사실입니다. root 값이라뇨? 와우! 대단합니다.

그래서 두 알고리즘의 연산 속도를 비교했습니다. time(NULL) 함수를 이용하였습니다. 아래는 이번 비교에 쓰인 코드입니다.

#include <stdio.h>
#include <math.h>
#include <time.h>

int CheckByDiv(unsigned int);
int CheckByRoot(unsigned int);

int main(void)
{
    unsigned int number = 1;
    long firstTime = 0;
    long secondTime = 0;

    printf("양의 정수를 입력하면 소수인지 알려줄게. : ");
    scanf("%d", &number);
    printf("\n");

    firstTime = time(NULL);
    if(CheckByDiv(number)) printf("이 수는 소수입니다. \n");
    else printf("이 수는 소수가 아닙니다. \n");
    secondTime = time(NULL);
    printf("CheckByDiv() 함수에 의해 걸린 시간은 %ld초입니다. \n\n", secondTime - firstTime);

    firstTime = time(NULL);
    if(CheckByRoot(number)) printf("이 수는 소수입니다. \n");
    else printf("이 수는 소수가 아닙니다. \n");
    secondTime = time(NULL);
    printf("CheckByRoot() 함수에 의해 걸린 시간은 %ld초입니다. \n", secondTime - firstTime);

    return 0;
}

int CheckByDiv(unsigned int num)
{
    register unsigned int div;
    int value = 0;

    for(div = 2; num % div; div++);

    if(div == num) value = 1;
    else value = 0;

    return value;
}

int CheckByRoot(unsigned int num)
{
    unsigned rootNum = (unsigned) sqrt(num);
    register unsigned div = 0;
    int value = 0;

    for(div = rootNum; num % div; div--);

    if(div == 1) value = 1;
    else value = 0;

    return value;
}

CheckByDiv() 함수가 제 글의 알고리즘입니다. 일반적으로 쓰이는 거죠. 그리고 CheckByRoot() 함수가 시리니 님의 글에 소개된 알고리즘입니다. 두 함수의 차이는 sqrt() 함수로 rootNum을 이용하는가 아닌가입니다. 단 한 줄 차이입니다. 이 한 줄이 어느 정도의 차이를 보여줄까요?

아, 그리고 변수 div를 register로 선언하였습니다. 이것은 값을 메모리가 아닌 레지스터에 저장하라는 키워드입니다. 메모리보다 레지스터가 속도가 더 빠르다는 건 아시죠? 보통 반복문의 첨자로 쓰이며, 연산 속도의 향상에 도움이 됩니다. 두 함수 모두 div를 반복문의 첨자로 쓰이기 때문에 register로 선언한 것입니다.

그럼, 이제 결과를 보겠습니다.

에? 저거 정말인가요? 예, 정말입니다. CheckByRoot() 함수를 이용했을 경우 1초도 안 걸렸으므로 단순 배수 비교도 힘들게 되었습니다. 워메...

root 값을 이용하면 연산속도에서 큰 향상을 보일 수 있다는 걸 확인했습니다. 공돌이도 수학을 잘 해야 살아 남습니다. 응?

참고 문헌

알고리즘 :: 입력된 수가 소수인지 확인하자. :: http://hisjournal.net/blog/122

[뻘쭘한 알고리즘] 나는 네가 소수인지 아닌지 알 수 있다 (1) :: http://sirini.net/blog/737