[c++] 알고리즘 개념공부 :: 비트조작 (비트마스크, 연산, 코드 구현)

비트 조작

개념

비트(bit)란 0과 1의 값을 가질 수 있는 데이터의 단위이다. 4bit를 모은 단위를 니블(nibble)이라 부르고, 8bit를 모은 단위를 바이트(byte)라고 부른다. 2byte를 모은 단위는 일부 전자통신기기에서 워드(word)라고 한다.

 

구현

C++에서는 비트를 다루기 위해서 <bitset>이라는 헤더를 포함해서 사용한다.

 

연산

 C++에서 비트연산들은 위에서 언급한 라이브러리로 쉽게 가져다 쓸 수 있지만, 개념 공부 측면에서 그냥 구현도 하고 라이브러리 사용법도 익혀두려한다.

 

 메모리 상에 변수를 저장하는 것이 1byte 단위로 가능하기 때문에, bit 단위의 자료형은 없다. 다만 bool 형은 메모리 상에서 1byte를 차지하지만 가능한 값이 true 혹은 false 밖에 없으므로 이를 이용해서 0과 1을 표현하기로 하자.

(자료형 정리)

 

기본 개념

2의 보수, 음수

컴퓨터가 정수를 저장할 때는 대부분 2의 보수 형태로 저장한다. 그 외에도 부호화 절댓값으로 저장할 수도 있고 1의 보수 형태로 저장할 수도 있다.

표현방식	+5	-5
부호화 절댓값	0101	1101
1의 보수	0101	1010
2의 보수	0101	1011

 

 

 가장 왼쪽의 MSB(최상위 비트)는 수의 부호를 나타내고 MSB를 제외한 나머지 비트들로 수를 나타낸다. MSB가 0이면 양수이고 1이면 음수이다. 따라서 n비트, 2의 보수 형태로 정수를 나타낼 때, 정수의 범위는 -2^(n-1)~2^(n-1)-1이다. 나머지 두 방식과는 다르게 +0와 -0이 아닌 하나의 0으로 표현하기 때문에, 표현 범위가 더 크다.

 

 

 음수를 나타내기 위해서는 기존의 수에서 비트를 뒤집은 다음(1의 보수) 1을 더해주면 되는데, 이는 기존의 수를 2의 보수표현을 이용해서 음수로 나타낸 것이다. 기존의 수와 해당 수의 보수를 합하면 진수가 나오는데, 위의 예제에서는 기존의 수가 5이고 마지막 수가 -3으로 표시된 데에서 보수의 성질을 만족한다고 볼 수 있다.

 

 컴퓨터 내부에서는 사칙연산 시 가산기(Adder)만 이용하기 때문에, 이렇게 2의 보수 표현법을 이용해서 덧셈을 계산하며 뺄셈도 마찬가지로 음수를 만들어서 덧셈을 계산한다.

(실수 표현)

 

산술 시프트, 논리 시프트

 시프트 연산은 비트를 1bit씩 밀면서 생긴 빈자리에 새로운 bit를 채워주는 연산이다.

 

 

 산술 시프트 연산은 부호비트를 그대로 채워준다. 기본적으로 2로 나누거나 곱한 결과와 같다고 보면 되기 때문에 산술 시프트 연산이라고 불린다.

 논리 시프트 연산은 부호비트에 0을 채워준다. 따라서 논리적으로 비트를 제어하는 연산으로 산술적으로는 거의 관계가 없는 것처럼 숫자가 변화한다.

 

기본 연산

• NOT [~] : 1이면 0, 0이면 1

• OR [|] : 두 값 중 1이 하나라도 있다면 1, 아니면 0

  합집합 개념과 유사하다.

• XOR [^] : 두 값이 다르면 1, 같으면 0

  실제로는 XOR에 들어가는 값 중 1의 갯수가 홀수개이면 1

• AND [&] : 두 값 모두 1이라면 1, 아니면 0

  교집합 개념과 유사하다.

• SHIFT [<< >>] : 비트 단위로 한 칸씩 미는 연산

 

함수 구현

1. Get : 특정 위치의 비트 값을 가져온다.
2. Set : 특정 위치의 비트 값을 세팅한다.
3. Count : 세팅된 비트 값이 몇 개인지 반환한다.
4. Clear : 비트를 0으로 초기화 한다.
5. Toggle : 비트를 반전시킨다.
6. MSB : 최상위 비트를 찾는다.
7. LSB : 최하위 비트를 찾는다.

 

<bitset> 라이브러리 이용

#include <bitset>
#include <iostream>

using namespace std;

int main() {
    bitset<5> num;
    cout << num << endl; // 00000

    // set
    num.set(2, 1);
    num[3] = 1;
    cout << num << endl; // 01100 

    // get
    // pos를 앞에서부터 세야함
    cout << num[2] << endl; // 1
    cout << num.test(2) << endl; // 1

    // count
    cout << num.count() << endl; // 1이 몇개? 2
    cout << num.size() - num.count() << endl; // 0이 몇개? 3

    // clear
    num.reset(2);
    cout << num << endl; // 01000

    // toggle
    // 여기서부터 pos를 뒤에서부터 세야함
    num.flip(1); 
    cout << num << endl; // 01010
    num.flip();
    cout << num << endl; // 10101


    // MSB, LSB x
}

 

직접 구현

#include <iostream>
#include <string>
#define BITNUM 8*sizeof(char)

using namespace std;

string GetString(char num) {
    string tmp(BITNUM,'0');
    for (int i = 0; i < BITNUM; i++) {
        if ((char)((char)(num << (BITNUM - 1-i)) >> BITNUM) == 0)
            tmp[BITNUM - i - 1] = '0';
        else
            tmp[BITNUM - i - 1] = '1';
    }
    return tmp;
}

bool Get(char num, int pos) {
    char tmp = 1 << (BITNUM - pos -1);
    return (tmp & num);
}

void Set(char& num, int pos) {
    char tmp = 1 << (BITNUM - pos -1);
    num = (tmp | num);
}

int Count(char num) {
    int cnt = 0;
    for (int i = 0; i < BITNUM; i++) {
        char tmp = pow(2, i);
        if ((num & tmp) != 0)
            cnt++;
    }
    return cnt;
}

void Toggle(char& num) {
    num = ~num;
}

void Toggle(char& num, int pos) {
    char tmp = pow(2, pos);
    num ^= tmp;
}

void Clear(char& num, int pos) {
    char tmp = ~((char)pow(2, BITNUM- pos-1));
    num &= tmp;
}

bool MSB(char& num) {
    if (num >> (BITNUM - 1))
        return true;
    else
        return false;
}

bool LSB(char& num) {
    char tmp = num << (BITNUM - 1);
    tmp >> (BITNUM - 1);

    if (tmp)
        return true;
    else
        return false;
}


int main() {
    char num = 0;

    // set
    Set(num, 2); Set(num, 5); Set(num, 6);
    cout << GetString(num) << endl;// 00100110

    // get
    cout << Get(num, 2) << endl; // 1

    // count
    cout << Count(num) << endl;

    // clear
    Clear(num, 5);
    cout << GetString(num) << endl;// 00100010

    // toggle
    Toggle(num); //
    cout << GetString(num) << endl;// 11011101
    Toggle(num,1); Toggle(num, 7);
    cout << GetString(num) << endl;// 01011111

    // MSB
    cout << MSB(num) << endl; // 0
    // LSB
    cout << LSB(num) << endl; // 1

}

 

비트마스크(BitMask)

여러 표현 시 비트를 이용하여 메모리 사용을 줄이고 효율적으로 표현할 수 있다. 이를 bitmask라고 하는데, 예를 들어 집합 {1,2,3,5}가 있을 때 11101로 나타낼 수 있고 저장할 때는 10진수로 29를 저장하면 된다. 따라서 배열을 이용할 필요없이 정수 하나만으로 저장이 가능하므로 메모리 사용을 줄일 수 있다. 비트마스크를 다루기 위해서는 위에서 언급했던 비트연산을 사용해야한다.

 

참고

https://iamsjy17.github.io/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B8%B0%EC%B4%88/2019/05/09/bitop.html