참고
- N x N 2차원 배열 뒤집기, 회전하기 (Rotate, Flip 2D Array)
아래의 char 배열은 2차원 배열로 16 x 2의 크기를 가진다.
하지만 비트 단위로 볼 때, char는 1byte이므로 16 x (2 x 8) = (16 x 16)인 정사각형의 비트맵으로 볼 수 있다.
char bitmap[16][2];
N x N 2차원의 배열을 뒤집거나 회전하는 것은 간단하지만,
비트 연산의 경우 1 byte를 8개로 나눠서 구현해야 한다.
높이와 너비(x 8)가 같은 2차원 비트맵을 반전시키거나 회전시켜보자.
bitmap의 SIZE = HEIGHT와 같다.
하지만 너비 WIDTH는 비트 단위로 계산하기 때문에 HEIGHT를 8로 나눈다.
그렇게 되면 bit 단위로 보았을 때 HEIGHT x WIDTH = SIZE x SIZE 인 정사각형 비트맵이 된다.
#define SIZE (16)
#define HEIGHT (SIZE)
#define WIDTH (HEIGHT / 8)
char bitmap[HEIGHT][WIDTH];
여기서 다룰 비트맵의 사이즈는 8의 배수다.
bitmap을 아래와 같이 init해보자.
void init(char bitmap[HEIGHT][WIDTH])
{
for (int i = 0; i < HEIGHT; i++)
for (int k = 0; k < WIDTH; k++)
bitmap[i][k] = 0;
bitmap[0][0] = 0xFF;
bitmap[1][0] = 0xFE;
bitmap[2][0] = 0xFC;
bitmap[3][0] = 0xF8;
bitmap[4][0] = 0xF0;
bitmap[5][0] = 0xE0;
bitmap[6][0] = 0xC0;
bitmap[7][0] = 0x80;
bitmap[HEIGHT - 4][WIDTH - 1] = 0x01;
bitmap[HEIGHT - 3][WIDTH - 1] = 0x03;
bitmap[HEIGHT - 2][WIDTH - 1] = 0x07;
bitmap[HEIGHT - 1][WIDTH - 1] = 0x0F;
}
위의 bitmap을 비트 단위로 출력하면 아래와 같다.
2차원 배열을 비트 단위로 출력 = printBitmap은 아래와 같다.
template <typename T>
void printBitNumber(T number)
{
unsigned int bitSize = sizeof(number) * 8;
T mask = (1ull) << (bitSize - 1);
printf("%d ", (number & mask) == mask);
mask = (1ull) << (bitSize - 2);
for (int i = 1; i < bitSize; i++)
{
printf("%d ", (number & mask) == mask);
mask >>= 1;
if (i % 8 == 7) printf(" ");
}
}
void printBitmap(char bitmap[HEIGHT][WIDTH])
{
for (int i = 0; i < HEIGHT; i++)
{
for (int k = 0; k < WIDTH; k++)
printBitNumber(bitmap[i][k]);
putchar('\n');
if (i % 4 == 3) putchar('\n');
}
putchar('\n');
}
get, set
N x N 크기의 2차원 비트맵에서 (row, column)의 비트를 가져오는 함수는 다음과 같다.
column은 8개의 비트로 이루어져 있으므로,
비트마스크 = 1000 0000 (0x80)을 8로 나눈 나머지만큼 옮긴다.
그리고 bitmap의 (r, c / 8) 이 N x N의 (r, c)가 된다.
char getBit(char bitmap[HEIGHT][WIDTH], int r, int c) {
unsigned char mask = 0x80 >> (c % 8);
return ((bitmap[r][c / 8] & mask) == mask) ? 1 : 0;
}
해당 비트가 mask와 같다면 1 비트일 것이므로 1을 return하고 그렇지 않으면 0을 return한다.
같은 원리로 setBit는 아래와 같다.
해당 비트에서 &와 ~ 연산을 하면 0으로 만들 수 있고, | 연산을 하면 1로 만들 수 있다.
void setBit(char bitmap[HEIGHT][WIDTH], int r, int c, char bit)
{
unsigned char mask = 0x80 >> (c % 8);
if (bit == 0) bitmap[r][c / 8] &= ~mask; // 해당 위치 bit를 0으로 변경
else bitmap[r][c / 8] |= mask; // 해당 위치 bit를 1로 변경
}
getBit가 제대로 되는지 확인하려면 printGetBitTest와 printBitMap을 비교하면 된다.
void printGetBitTest(char bitmap[HEIGHT][WIDTH])
{
for (int i = 0; i < SIZE; i++)
{
for (int k = 0; k < SIZE; k++)
printf("%d ", getBit(bitmap, i, k));
putchar('\n');
if (i % 4 == 3) putchar('\n');
}
putchar('\n');
}
int main(void)
{
printBitmap(bitmap);
printGetBitTest(bitmap);
return 0;
}
Flip, Rotate
N x N 2차원 배열 뒤집기, 회전하기 코드와 getBit, setBit를 이용하면
N x N 2차원 비트맵을 뒤집거나 회전할 수 있다.
수평 뒤집기를 2차원 배열 vs 2차원 비트에 대해 비교해보자.
// N x N 2차원 배열
void flipHorizontal(int map[SIZE][SIZE])
{
int temp[SIZE][SIZE];
copyMap(temp, map);
for (int i = 0; i < SIZE; i++)
for (int k = 0; k < SIZE; k++)
map[i][k] = temp[SIZE - 1 - i][k];
}
// N x N 2차원 비트맵
void flipHorizontal(char bitmap[HEIGHT][WIDTH])
{
char temp[HEIGHT][WIDTH];
copyMap(temp, bitmap);
for (register int i = 0; i < SIZE; i++)
for (register int k = 0; k < SIZE; k++)
setBit(bitmap, i, k, getBit(temp, SIZE - 1 - i, k));
}
2차원 배열에서는 [][]로 바로 값에 접근하지만, 비트맵은 getBit로 접근하고 setBit로 설정한 것 뿐이다.
전체 코드는 다음과 같다.
#include <stdio.h>
#define SIZE (16)
#define HEIGHT (SIZE)
#define WIDTH (HEIGHT / 8)
char bitmap[HEIGHT][WIDTH];
void init(char bitmap[HEIGHT][WIDTH])
{
for (int i = 0; i < HEIGHT; i++)
for (int k = 0; k < WIDTH; k++)
bitmap[i][k] = 0;
bitmap[0][0] = 0xFF;
bitmap[1][0] = 0xFE;
bitmap[2][0] = 0xFC;
bitmap[3][0] = 0xF8;
bitmap[4][0] = 0xF0;
bitmap[5][0] = 0xE0;
bitmap[6][0] = 0xC0;
bitmap[7][0] = 0x80;
bitmap[HEIGHT - 4][WIDTH - 1] = 0x01;
bitmap[HEIGHT - 3][WIDTH - 1] = 0x03;
bitmap[HEIGHT - 2][WIDTH - 1] = 0x07;
bitmap[HEIGHT - 1][WIDTH - 1] = 0x0F;
}
template <typename T>
void printBitNumber(T number)
{
unsigned int bitSize = sizeof(number) * 8;
T mask = (1ull) << (bitSize - 1);
printf("%d ", (number & mask) == mask);
mask = (1ull) << (bitSize - 2);
for (int i = 1; i < bitSize; i++)
{
printf("%d ", (number & mask) == mask);
mask >>= 1;
if (i % 8 == 7) printf(" ");
}
}
void printBitmap(char bitmap[HEIGHT][WIDTH])
{
for (int i = 0; i < HEIGHT; i++)
{
for (int k = 0; k < WIDTH; k++)
printBitNumber(bitmap[i][k]);
putchar('\n');
if (i % 4 == 3) putchar('\n');
}
putchar('\n');
}
char getBit(char bitmap[HEIGHT][WIDTH], int r, int c) {
unsigned char mask = 0x80 >> (c % 8);
return ((bitmap[r][c / 8] & mask) == mask) ? 1 : 0;
}
void setBit(char bitmap[HEIGHT][WIDTH], int r, int c, char bit)
{
unsigned char mask = 0x80 >> (c % 8);
if (bit == 0) bitmap[r][c / 8] &= ~mask; // 해당 위치 bit를 0으로 변경
else bitmap[r][c / 8] |= mask; // 해당 위치 bit를 1로 변경
}
void printGetBitTest(char bitmap[HEIGHT][WIDTH])
{
for (int i = 0; i < SIZE; i++)
{
for (int k = 0; k < SIZE; k++)
printf("%d ", getBit(bitmap, i, k));
putchar('\n');
if (i % 4 == 3) putchar('\n');
}
putchar('\n');
}
void copyMap(char src[HEIGHT][WIDTH], char dest[HEIGHT][WIDTH])
{
for (int i = 0; i < HEIGHT; i++)
for (int k = 0; k < WIDTH; k++)
src[i][k] = dest[i][k];
}
void flipHorizontal(char bitmap[HEIGHT][WIDTH])
{
char temp[HEIGHT][WIDTH];
copyMap(temp, bitmap);
for (register int i = 0; i < SIZE; i++)
for (register int k = 0; k < SIZE; k++)
setBit(bitmap, i, k, getBit(temp, SIZE - 1 - i, k));
}
void flipVertical(char bitmap[HEIGHT][WIDTH])
{
char temp[HEIGHT][WIDTH];
copyMap(temp, bitmap);
for (register int i = 0; i < SIZE; i++)
for (register int k = 0; k < SIZE; k++)
setBit(bitmap, i, k, getBit(temp, i, SIZE - 1 - k));
}
void rotateClockwise90(char bitmap[HEIGHT][WIDTH])
{
char temp[HEIGHT][WIDTH];
copyMap(temp, bitmap);
for (register int i = 0; i < SIZE; i++)
for (register int k = 0; k < SIZE; k++)
setBit(bitmap, i, k, getBit(temp, SIZE - 1 - k , i));
}
void rotateClockwise180(char bitmap[HEIGHT][WIDTH])
{
char temp[HEIGHT][WIDTH];
copyMap(temp, bitmap);
for (register int i = 0; i < SIZE; i++)
for (register int k = 0; k < SIZE; k++)
setBit(bitmap, i, k, getBit(temp, SIZE - 1 - i, SIZE - 1 - k));
}
void rotateClockwise270(char bitmap[HEIGHT][WIDTH])
{
char temp[HEIGHT][WIDTH];
copyMap(temp, bitmap);
for (register int i = 0; i < SIZE; i++)
for (register int k = 0; k < SIZE; k++)
setBit(bitmap, i, k, getBit(temp, k, SIZE - 1 - i));
}
int main(void)
{
printf("Original \n");
init(bitmap);
printBitmap(bitmap);
printf("Flip Horizontal\n");
init(bitmap);
flipHorizontal(bitmap);
printBitmap(bitmap);
printf("Flip Vertical\n");
init(bitmap);
flipVertical(bitmap);
printBitmap(bitmap);
printf("Rotate Clockwise 90 = CounterClockwise 270\n");
init(bitmap);
rotateClockwise90(bitmap);
printBitmap(bitmap);
printf("Rotate Clockwise 180 = CounterClockwise 180\n");
init(bitmap);
rotateClockwise180(bitmap);
printBitmap(bitmap);
printf("Rotate Clockwise 270 = CounterClockwise 90\n");
init(bitmap);
rotateClockwise270(bitmap);
printBitmap(bitmap);
return 0;
}
각각의 함수를 Original과 비교하면 다음과 같다.
'개발 > C, C++' 카테고리의 다른 글
C, C++ - 비트 교환 (Change Some Bits) (0) | 2023.08.15 |
---|---|
C, C++ - 비트 뒤집기 (Reverse Bits) (0) | 2023.07.30 |
C, C++ - 1차원 비트 회전하기 (Rotate Bits of a Number) (0) | 2023.07.30 |
C, C++ - 1 비트 개수 세기 (Bit Counter) (0) | 2023.07.29 |
C, C++ - 비트 연산으로 2의 제곱수 처리하기 (0) | 2023.07.29 |
댓글