[C++] 비트단위의 데이터 저장방법

대부분의 PS 문제를 해결할 때에는 보통 메모리 제한보다는 성능을 더 고려한다. 처음부터 메모리가 넉넉하게 주어지며, 사실 기술이 많이 발전한 지금 메모리를 극한으로 제한하는 것은 어불성설인 것 같기도 하다.

하지만 PS 문제에서 메모리를 제한할 때, 알아두면 좋을 방법이니 포스팅해보도록 한다.

---

| 사용되지 않는 비트의 예시

1. 입력 값으로 주어진 수의 범위가 제한적일 때

예를 들어, 특정 문자열이 주어지고, 그 문자열의 길이를 저장해야 할 때 보통

int len = str.length();

이런 식으로 사용하곤 하는데. 만약 주어진 문자열의 길이가 8 이하라면? 100 이하라면? 위의 Integer type변수 len의 앞쪽 비트는 전혀 사용되지 않는다.
다시말해 만약 문자열의 길이가 8 이하라면, 단 3bit로 표현이 가능하고 100 이하라면 7bit로 표현이 가능하다.

2. 입력 값으로 영문 소문자 혹은 대문자만 주어질 때

한글은 2byte로 표현이 되고, 영문 및 특수문자는 1byte로 표현이 된다. 만약 어떤 프로그램의 입력이 영문 소문자 혹은 대문자로만 이루어져 있다면, 1byte 전부를 쓸 필요는 없다. 1byte는 8bit로 숫자 0부터 255까지 표현이 가능하고, 영문자는 단 26개이기 때문에 5bit를 사용하여 각 영문자를 mapping 한다면 전부 표현이 가능하다.

---

| 데이터를 비트단위로 메모리에 차곡차곡 쌓기

위의 1,2번 내용은 어려운 내용이 아니다. 입력 값이 제한되어 있다면, 당연히 그 입력값을 표현하는데 필요한 비트도 적을 것이다.

Int len = str.length();

위의 코드에서 문자열의 길이가 최대 100이라면 숫자 100 이하로 표현이 될 것이고, 어차피 32bit 중 7bit만 사용이 될 것이다. 값 자체는 아무런 영향이 없고 값을 담는 바구니에 따라 낭비되는 비트가 있다/없다로 나뉘는 것이다. 즉, 이말은 바구니가 int가 아니라 char를 쓰더라도 1bit가 낭비가 될 것이다.
그렇다면 어떻게 해야 메모리 낭비 없이 모든 데이터를 저장할 수 있을까? 답은 직관적이다. 그냥 필요한 비트까지만 쓰고 다음 비트는 다른 데이터로 채우는 것이다. 아래는 메모리에 필요한 데이터를 차곡차곡 쌓는 코드이다.

using UI = unsigned int;
void write(char*str, int idx, int val) {
	*((UI*)(str + (idx >> 3))) |= val << (idx & 7);
}

void read(char*str, int idx, int bitLen) {
	UI target = *((UI*)(str + (idx >> 3))), mask = (1 << bitLen) - 1;
	return (tg >> (idx & 7)) & mask;
}

읽기는 쓰기의 반대이니 쓰기만 설명하자면, 메모리를 바이트 단위로 채운다고 하면 1 byte가 8 bit이기 때문에, 몇 번째 byte부터 채울지 정해야 한다. 그러한 코드가 str + (idx >> 3) 부분이다. 오른쪽으로 3번 shift는 나누기 8과 같다.
몇 번째 byte부터 채울지가 정해진다면 그 byte의 몇 번째 bit부터 쓸지를 정해야 하는데 그 코드가 val << (idx & 7) 이 부분이다. & 7은 % 8과 같다. 이런 식으로 해주면 사용 안 하는 비트 없이 필요한 데이터를 모두 채울 수 있다.