byte 아니고?
바이트 아닙니다. 비트입니다.
프로그래밍을 할 적에 극한의 메모리나 시간 효율을 추구해야 하거나 추구하고 싶을 때가 있습니다. 가령 0~3 사이의 정수 값을 한 8개 정도 저장해야 하는 상황이면 int[8]에 0~3을 넣어 $32\cdot 8=256$비트를 쓰기보다는 필요한 만큼($2\cdot 8=32$비트)만 메모리를 주고 싶은 거죠. 이게 얼마나 성능 향상을 가져올지는 모르겠지만 기분이 좋잖아요?
그래서 2비트 정수 8개를 32비트짜리 unsigned int에 채워담았다고 해봅시다(unsigned short에 꽉 채워담아도 되는데 그러면 이후 계산이 좀 곤란합니다).
전체 합 계산
이 8개의 정수를 모두 합하고 싶습니다. 어떻게 구현하면 효율적일까요? 반복문을 통한 나이브 구현은 이렇게 됩니다.
unsigned int v; //저장소
int count = 0;
for (int i = 0; i < 16; i += 2)
count += (v >> i) & 0b11;썩 효율적이다라고는 못 하겠습니다. 더 좋은 방법이 있습니다. 바로 popcount 함수를 이용하는 겁니다.
popcount는 입력으로 들어온 값의 비트 중 켜진 비트(1인 비트)의 개수를 반환하는 함수입니다. cpu 단에서 돌아가는 명령이라 훨씬 빠르다... 고 알고 있습니다. 이 방법으로 짝수 비트의 개수를 모두 센 뒤 2를 곱하고, 홀수 비트의 개수를 모두 세 더하면 우리가 원하는 값을 얻을 수 있습니다.
unsigned int v; //저장소
int count = popcount(v & 0b1010101010101010) << 1 + popcount(v & 0b0101010101010101);5회의 연산(popcount x2, & x2, << x1)으로 해결됩니다. 훨씬 낫네요.
병렬 차이 계산
8개의 정수 리스트가 하나 더 있다고 합시다. a[], b[]에 대해서 abs(a[0]-b[0]), abs(a[1]-b[1]), ..., abs(a[7]-b[7])을 구하고 싶으면 어떻게 할까요. 반복문은 쓰지 맙시다.
우선 $M$ 미만인 양의 정수 $a, b$를 생각해봅시다. $a - b$의 값은 $-M < a-b < 2M$입니다. 음수는 우리가 다루기 곤란하니까 $a$에 $M$을 더해서 생각해봅시다. $(a+M) - b$의 값은 $0 < (a+M)-b < 3M$이 됩니다. $a-b$나 $(a+M)-b$나 결국 $\text{mod }M$을 씌우면 같은 $a-b$가 되기 때문에 괜찮습니다.
우리가 다루는 케이스는 $M = 4$가 되겠습니다. 계산 과정에서 $0-11$ 사이의 값을 저장해야 하기 때문에 짝수 번째 값들과 홀수 번째 값들을 따로 다루기로 합시다.
unsigned int a, b;
unsigned int e = ((a & 0b1100110011001100) >> 2 + 0b0100010001000100) - ((b & 0b1100110011001100) >> 2);
unsigned int o = ((a & 0b0011001100110011) + 0b0100010001000100) - (b & 0b0011001100110011);
unsigned int result = (e & 0b0011001100110011) << 2 + (o & 0b0011001100110011);14회의 연산로 해결됩니다.
이걸 응용하면 병렬 합도 계산 가능합니다. 코드의 $e$와 $o$를 구하는 식에서 $M$(0b0100010001000100)의 덧셈을 제거하고, 가운데 뺄셈을 덧셈으로 바꾼 뒤에 $e$와 $o$를 이어붙이면 합이 들어간 4-bit 정수 리스트가 됩니다. 대신 값의 순서는 바뀌겠네요.
심심하면 더 추가해 적거나 최적화해보거나 하겠습니다.