C, C++ - 비트 연산으로 2의 제곱수 처리하기

C, C++ 전체 링크

삼성 C형 전체 링크

 

2ⁿ 또는 2ⁿ - 1 판단하기.

 

숫자 x에서 -1을 하고 & 연산을 해서 0이 되면 2ⁿ이다.

그리고 x에서 +1을 하고 & 연산을 해서 0이 되면 2ⁿ - 1이다.

 

2ⁿ은 bit로 나타내면 하나의 bit만 1이기 때문에 이런 규칙이 생긴다.

 

0100 0000 = 64

0011 1111 = 63

------------------

0000 0000 = 64 & 63 = 0

 

마찬가지로 2n - 1도 연산을 해보면 쉽게 규칙을 파악할 수 있다.

 

0111 1111 = 127

1000 0000 = 128

-------------------

0000 0000 = 127 & 128 = 0

#include <stdio.h>

int main(void)
{
	int x;
	
	/* 주어진 부호 없는 정수가 2의 거듭제곱이나 0인지 판정 */
	printf("check power of n\n");
	x = 15;
	printf("%d is power of n (%d)\n", x, x & (x - 1));
	x = 256;
	printf("%d is power of n (%d)\n", x, x & (x - 1)); // 결과는 0
	putchar('\n');

	printf("========================================\n");
	
	/* 주어진 부호 없는 정수가 2의 거듭제곱 -1 이나 0인지 판정 */
	printf("check power of n - 1\n");
	x = 15;
	printf("%d is power of n - 1  (%d)\n", x, x & (x + 1)); // 결과는 0
	x = 253;
	printf("%d is power of n - 1 (%d)\n", x, x & (x + 1));
	putchar('\n');

	printf("========================================\n");

	return 0;
}

---

2ⁿ으로 올림 / 내림

 

어떤 숫자를 특정한 배수로 올림 또는 내림할 수 있다.

 

예를 들어서 x가 205인 경우에 32의 배수로 올림하면 224되고, 32의 배수로 내림하면 192가 된다.

 

올림을 구하는 방법은 다음과 같다.

 

1) x에 2ⁿ - 1을 더한다.

2) x에 & ~(2ⁿ - 1)연산을 한다.

 

내림을 구하는 방법은 더 간단하다.

 

1) x에 & ~(2ⁿ - 1)연산을 한다.

 

(2ⁿ - 1)의 ~ 연산에 & 연산은 bit를 모두 클리어 시키는 효과가 있기 때문에 이런 결과가 나오게 된다.

int main(void)
{
	unsigned int x;

	x = 205;
	x += (31);
	x &= ~(31);
	printf("%d\n", x); // 224
	
	x = 205;
	x &= ~(31);
	printf("%d\n", x); // 192

	/* & ~ 대신 -연산도 가능 */
	x = 205;
	printf("%d\n", (x + 31) & -32); // 224
	printf("%d\n", x & -32);        // 192

	return 0;
}