C, C++ - 1차원 비트 회전하기 (Rotate Bits of a Number)

C, C++ 전체 링크

삼성 C형 전체 링크

 

비트를 회전시켜보자.

비트의 회전은 unsigned 타입만 가능하다.

 

먼저 아래 코드를 실행시켜 보자.

#include <stdio.h>

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(" ");
	}
	putchar('\n');
}

template <typename T>
T getBitRotateLeft(T number, int n)
{
	unsigned int bitSize = sizeof(number) * 8;
	return (number << n) | (number >> (bitSize - n));
}

template <typename T>
T getBitRotateRight(T number, int n)
{
	unsigned int bitSize = sizeof(number) * 8;
	return (number >> n) | (number << (bitSize - n));
}

int main(void)
{
	unsigned int ux;
	signed int sx;

	ux = 0xFF00FF00;
	printBitNumber(ux >> 2);

	sx = 0xFF00FF00;
	printBitNumber(sx >> 2);
    
	return 0;
}

 

sx는 signed int이기 때문에 최상단 비트가 1이라면 >> 연산으로 1이 추가된다. 

이러한 이유로 rotate를 할 때 원하는 결과를 얻지 못해서 unsigned 타입만 회전이 가능하다.

signed 타입은 bit rotation이 불가능하기 때문에 unsigned int로 타입 캐스팅을 하고 회전한다.

---

rotation

 

이제 비트를 회전해보자.

비트를 5칸 왼쪽으로 회전시키려면 최상단부터 5칸 비트를 맨 뒤로 보내고, 나머지는 앞으로 5칸 밀면 된다.

아래의 코드를 실행해보자.

#include <stdio.h>

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(" ");
	}
	putchar('\n');
}

int main(void)
{
	unsigned int x = 0xFF00FF00;
	unsigned int y;
	int n = 5;

	printf("x             : "); printBitNumber(x);
	printf("x << n        : "); printBitNumber(x << 5);
	printf("x >> (32 - n) : "); printBitNumber(x >> (32 - 5));

	return 0;
}

 

전체 비트를 5칸 << 로 밀고, (32 - 5)비트를 >> 로 밀면 아래의 결과가 나온다.

 

결국 left rotate는 x << n 과 x >> (32 - n)의 | 연산이다. (int가 32비트 이므로)

	printf("x             : "); printBitNumber(x);
	printf("x << n        : "); printBitNumber(x << 5);
	printf("x >> (32 - n) : "); printBitNumber(x >> (32 - 5));

	y = (x << n) | (x >> (32 - n));  /* 왼쪽으로 n칸 이동 */
	printf("x left rotate : "); printBitNumber(y);

 

템플릿을 이용하여 left, right rotate를 작성하면 아래와 같다.

template <typename T>
T getBitRotateLeft(T number, int n)
{
	unsigned int bitSize = sizeof(number) * 8;
	return (number << n) | (number >> (bitSize - n));
}

template <typename T>
T getBitRotateRight(T number, int n)
{
	unsigned int bitSize = sizeof(number) * 8;
	return (number >> n) | (number << (bitSize - n));
}

 

위의 코드를 이용해서 0xF000FF00FFF0FFFF를 left, right로 모두 0 ~ 63칸 이동해보자.

#include <stdio.h>

typedef unsigned long long int ull;

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(" ");
	}
	putchar('\n');
}

template <typename T>
T getBitRotateLeft(T number, int n)
{
	unsigned int bitSize = sizeof(number) * 8;
	return (number << n) | (number >> (bitSize - n));
}

template <typename T>
T getBitRotateRight(T number, int n)
{
	unsigned int bitSize = sizeof(number) * 8;
	return (number >> n) | (number << (bitSize - n));
}

int main(void)
{
	unsigned int x = 0xFF00FF00;
	unsigned int y;
	int n = 5;

	printf("x             : "); printBitNumber(x);
	printf("x << n        : "); printBitNumber(x << 5);
	printf("x >> (32 - n) : "); printBitNumber(x >> (32 - 5));

	y = (x << n) | (x >> (32 - n));  /* 왼쪽으로 n칸 이동 */
	printf("x left rotate : "); printBitNumber(y);

	//printf("right : ");
	//y = (x >> n) | (x << (32 - n));  /* 오른쪽으로 n칸 이동 */
	//printBitNumber(y);
	
	printBitNumber(getBitRotateLeft(x, n));

	ull xx = 0xF000FF00FFF0FFFF;
	
	for (int n = 0; n < 64; n++) printBitNumber(getBitRotateLeft(xx, n));
	putchar('\n');
	for (int n = 0; n < 64; n++) printBitNumber(getBitRotateRight(xx, n));
	putchar('\n');

	return 0;
}

 

left rotate 결과는 아래와 같다.

11110000 00000000 11111111 00000000 11111111 11110000 11111111 11111111
11100000 00000001 11111110 00000001 11111111 11100001 11111111 11111111
11000000 00000011 11111100 00000011 11111111 11000011 11111111 11111111
10000000 00000111 11111000 00000111 11111111 10000111 11111111 11111111
00000000 00001111 11110000 00001111 11111111 00001111 11111111 11111111
00000000 00011111 11100000 00011111 11111110 00011111 11111111 11111110
00000000 00111111 11000000 00111111 11111100 00111111 11111111 11111100
00000000 01111111 10000000 01111111 11111000 01111111 11111111 11111000
00000000 11111111 00000000 11111111 11110000 11111111 11111111 11110000
00000001 11111110 00000001 11111111 11100001 11111111 11111111 11100000
00000011 11111100 00000011 11111111 11000011 11111111 11111111 11000000
00000111 11111000 00000111 11111111 10000111 11111111 11111111 10000000
00001111 11110000 00001111 11111111 00001111 11111111 11111111 00000000
00011111 11100000 00011111 11111110 00011111 11111111 11111110 00000000
00111111 11000000 00111111 11111100 00111111 11111111 11111100 00000000
01111111 10000000 01111111 11111000 01111111 11111111 11111000 00000000
11111111 00000000 11111111 11110000 11111111 11111111 11110000 00000000
11111110 00000001 11111111 11100001 11111111 11111111 11100000 00000001
11111100 00000011 11111111 11000011 11111111 11111111 11000000 00000011
11111000 00000111 11111111 10000111 11111111 11111111 10000000 00000111
11110000 00001111 11111111 00001111 11111111 11111111 00000000 00001111
11100000 00011111 11111110 00011111 11111111 11111110 00000000 00011111
11000000 00111111 11111100 00111111 11111111 11111100 00000000 00111111
10000000 01111111 11111000 01111111 11111111 11111000 00000000 01111111
00000000 11111111 11110000 11111111 11111111 11110000 00000000 11111111
00000001 11111111 11100001 11111111 11111111 11100000 00000001 11111110
00000011 11111111 11000011 11111111 11111111 11000000 00000011 11111100
00000111 11111111 10000111 11111111 11111111 10000000 00000111 11111000
00001111 11111111 00001111 11111111 11111111 00000000 00001111 11110000
00011111 11111110 00011111 11111111 11111110 00000000 00011111 11100000
00111111 11111100 00111111 11111111 11111100 00000000 00111111 11000000
01111111 11111000 01111111 11111111 11111000 00000000 01111111 10000000
11111111 11110000 11111111 11111111 11110000 00000000 11111111 00000000
11111111 11100001 11111111 11111111 11100000 00000001 11111110 00000001
11111111 11000011 11111111 11111111 11000000 00000011 11111100 00000011
11111111 10000111 11111111 11111111 10000000 00000111 11111000 00000111
11111111 00001111 11111111 11111111 00000000 00001111 11110000 00001111
11111110 00011111 11111111 11111110 00000000 00011111 11100000 00011111
11111100 00111111 11111111 11111100 00000000 00111111 11000000 00111111
11111000 01111111 11111111 11111000 00000000 01111111 10000000 01111111
11110000 11111111 11111111 11110000 00000000 11111111 00000000 11111111
11100001 11111111 11111111 11100000 00000001 11111110 00000001 11111111
11000011 11111111 11111111 11000000 00000011 11111100 00000011 11111111
10000111 11111111 11111111 10000000 00000111 11111000 00000111 11111111
00001111 11111111 11111111 00000000 00001111 11110000 00001111 11111111
00011111 11111111 11111110 00000000 00011111 11100000 00011111 11111110
00111111 11111111 11111100 00000000 00111111 11000000 00111111 11111100
01111111 11111111 11111000 00000000 01111111 10000000 01111111 11111000
11111111 11111111 11110000 00000000 11111111 00000000 11111111 11110000
11111111 11111111 11100000 00000001 11111110 00000001 11111111 11100001
11111111 11111111 11000000 00000011 11111100 00000011 11111111 11000011
11111111 11111111 10000000 00000111 11111000 00000111 11111111 10000111
11111111 11111111 00000000 00001111 11110000 00001111 11111111 00001111
11111111 11111110 00000000 00011111 11100000 00011111 11111110 00011111
11111111 11111100 00000000 00111111 11000000 00111111 11111100 00111111
11111111 11111000 00000000 01111111 10000000 01111111 11111000 01111111
11111111 11110000 00000000 11111111 00000000 11111111 11110000 11111111
11111111 11100000 00000001 11111110 00000001 11111111 11100001 11111111
11111111 11000000 00000011 11111100 00000011 11111111 11000011 11111111
11111111 10000000 00000111 11111000 00000111 11111111 10000111 11111111
11111111 00000000 00001111 11110000 00001111 11111111 00001111 11111111
11111110 00000000 00011111 11100000 00011111 11111110 00011111 11111111
11111100 00000000 00111111 11000000 00111111 11111100 00111111 11111111
11111000 00000000 01111111 10000000 01111111 11111000 01111111 11111111

 

right rotate 결과는 아래와 같다.

11110000 00000000 11111111 00000000 11111111 11110000 11111111 11111111
11111000 00000000 01111111 10000000 01111111 11111000 01111111 11111111
11111100 00000000 00111111 11000000 00111111 11111100 00111111 11111111
11111110 00000000 00011111 11100000 00011111 11111110 00011111 11111111
11111111 00000000 00001111 11110000 00001111 11111111 00001111 11111111
11111111 10000000 00000111 11111000 00000111 11111111 10000111 11111111
11111111 11000000 00000011 11111100 00000011 11111111 11000011 11111111
11111111 11100000 00000001 11111110 00000001 11111111 11100001 11111111
11111111 11110000 00000000 11111111 00000000 11111111 11110000 11111111
11111111 11111000 00000000 01111111 10000000 01111111 11111000 01111111
11111111 11111100 00000000 00111111 11000000 00111111 11111100 00111111
11111111 11111110 00000000 00011111 11100000 00011111 11111110 00011111
11111111 11111111 00000000 00001111 11110000 00001111 11111111 00001111
11111111 11111111 10000000 00000111 11111000 00000111 11111111 10000111
11111111 11111111 11000000 00000011 11111100 00000011 11111111 11000011
11111111 11111111 11100000 00000001 11111110 00000001 11111111 11100001
11111111 11111111 11110000 00000000 11111111 00000000 11111111 11110000
01111111 11111111 11111000 00000000 01111111 10000000 01111111 11111000
00111111 11111111 11111100 00000000 00111111 11000000 00111111 11111100
00011111 11111111 11111110 00000000 00011111 11100000 00011111 11111110
00001111 11111111 11111111 00000000 00001111 11110000 00001111 11111111
10000111 11111111 11111111 10000000 00000111 11111000 00000111 11111111
11000011 11111111 11111111 11000000 00000011 11111100 00000011 11111111
11100001 11111111 11111111 11100000 00000001 11111110 00000001 11111111
11110000 11111111 11111111 11110000 00000000 11111111 00000000 11111111
11111000 01111111 11111111 11111000 00000000 01111111 10000000 01111111
11111100 00111111 11111111 11111100 00000000 00111111 11000000 00111111
11111110 00011111 11111111 11111110 00000000 00011111 11100000 00011111
11111111 00001111 11111111 11111111 00000000 00001111 11110000 00001111
11111111 10000111 11111111 11111111 10000000 00000111 11111000 00000111
11111111 11000011 11111111 11111111 11000000 00000011 11111100 00000011
11111111 11100001 11111111 11111111 11100000 00000001 11111110 00000001
11111111 11110000 11111111 11111111 11110000 00000000 11111111 00000000
01111111 11111000 01111111 11111111 11111000 00000000 01111111 10000000
00111111 11111100 00111111 11111111 11111100 00000000 00111111 11000000
00011111 11111110 00011111 11111111 11111110 00000000 00011111 11100000
00001111 11111111 00001111 11111111 11111111 00000000 00001111 11110000
00000111 11111111 10000111 11111111 11111111 10000000 00000111 11111000
00000011 11111111 11000011 11111111 11111111 11000000 00000011 11111100
00000001 11111111 11100001 11111111 11111111 11100000 00000001 11111110
00000000 11111111 11110000 11111111 11111111 11110000 00000000 11111111
10000000 01111111 11111000 01111111 11111111 11111000 00000000 01111111
11000000 00111111 11111100 00111111 11111111 11111100 00000000 00111111
11100000 00011111 11111110 00011111 11111111 11111110 00000000 00011111
11110000 00001111 11111111 00001111 11111111 11111111 00000000 00001111
11111000 00000111 11111111 10000111 11111111 11111111 10000000 00000111
11111100 00000011 11111111 11000011 11111111 11111111 11000000 00000011
11111110 00000001 11111111 11100001 11111111 11111111 11100000 00000001
11111111 00000000 11111111 11110000 11111111 11111111 11110000 00000000
01111111 10000000 01111111 11111000 01111111 11111111 11111000 00000000
00111111 11000000 00111111 11111100 00111111 11111111 11111100 00000000
00011111 11100000 00011111 11111110 00011111 11111111 11111110 00000000
00001111 11110000 00001111 11111111 00001111 11111111 11111111 00000000
00000111 11111000 00000111 11111111 10000111 11111111 11111111 10000000
00000011 11111100 00000011 11111111 11000011 11111111 11111111 11000000
00000001 11111110 00000001 11111111 11100001 11111111 11111111 11100000
00000000 11111111 00000000 11111111 11110000 11111111 11111111 11110000
00000000 01111111 10000000 01111111 11111000 01111111 11111111 11111000
00000000 00111111 11000000 00111111 11111100 00111111 11111111 11111100
00000000 00011111 11100000 00011111 11111110 00011111 11111111 11111110
00000000 00001111 11110000 00001111 11111111 00001111 11111111 11111111
10000000 00000111 11111000 00000111 11111111 10000111 11111111 11111111
11000000 00000011 11111100 00000011 11111111 11000011 11111111 11111111
11100000 00000001 11111110 00000001 11111111 11100001 11111111 11111111