C, C++ - 최하위 / 최상위 비트 구하기 (Find MSB, LSB)

C, C++ 전체 링크

삼성 C형 전체 링크

 

참고

- 비트 단위로 출력하기

 

다음과 같은 비트가 있다고 가정하자.

 

0010 0000 1100 0010

 

그러면 최하위 비트(Least Significant Bit)와 최상위 비트(Most Significant Bit)는 아래와 같다.

 

0010 0000 1100 0010

0000 0000 0000 0010 →       2 : 최하위 비트 (LSB : Least Significant Bit)  

0010 0000 0000 0000 → 8192 : 최상위 비트 (MSB : Most Significant Bit)

---

최하위 비트 구하기

 

최하위 비트 추출법은 매우 간단하다.

int lsb = x & (-x);
// int lsb = x & (~x + 1)

 

2의 보수를 구하는 방법이기도 한데, 실제로 연산을 해보자.

 

0010 0000 1100 0010 : x

1101 1111 0011 1101 : ~x

1101 1111 0011 1110 : ~x + 1 = -x

 

0010 0000 1100 0010 : x

1101 1111 0011 1110 : -x

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

0000 0000 0000 0010 : x & (-x)

#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 % 4 == 3) printf(" ");
	}
	putchar('\n');
}

int main()
{
	unsigned short x = 0x20C2;

	printBitNumber(x);
	printBitNumber((unsigned short)-x);

	unsigned short lsb = x & (-x);

	printBitNumber(lsb);

	return 0;
}

---

최상위 비트 구하기

 

최상위 비트를 구하는 것은 좀 더 까다롭다.

 

먼저 최상위 비트 아래의 비트를 모두 1로 만드는 과정이 필요하다.

이 과정은 O(logN)이 소요된다.

 

그리고 모든 최상위 비트 아래에 모든 비트가 1이 되었다면, +1을 해주고 >> 1을 해주면 최상위 비트만 남게 된다.

 

0010 0000 1100 0010 : x

0011 1111 1111 1111 : 어떤 과정에 의해 최상위 비트 아래를 모두 1로 변경.

0100 0000 0000 0000 : x + 1

0010 0000 0000 0000 : x >> 1

 

어떤 과정은 아래와 같다. 

unsigned short getMsb(unsigned short n)
{
	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;

	n = n + 1;

	return (n >> 1);
}

 

여기에서는 short에 대해서 구하고 있지만, int라면 n >> 16이 추가되고, long이라면 n >> 32가 추가되어야 한다.

#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 % 4 == 3) printf(" ");
	}
	putchar('\n');
}

unsigned short getMsb(unsigned short n)
{
	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;

	n = n + 1;

	return (n >> 1);
}

int main()
{
	unsigned short x = 0x20C2;

	printBitNumber(x);

	unsigned short msb = getMsb(x);

	printBitNumber(msb);

	return 0;
}

---

getMsb의 과정이 왜 최상위 비트 아래를 1로 만드는지 궁금하다면, x = 8192으로 두고 printBitNumber를 찍어보자.

#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 % 4 == 3) printf(" ");
	}
	putchar('\n');
}

unsigned short getMsb(unsigned short n)
{
	n |= n >> 1;
	printBitNumber(n);
	n |= n >> 2;
	printBitNumber(n);
	n |= n >> 4;
	printBitNumber(n);
	n |= n >> 8;
	printBitNumber(n);

	n = n + 1;
	printBitNumber(n);

	return (n >> 1);
}

int main()
{
	unsigned short x = 8192;

	printBitNumber(x);

	unsigned short msb = getMsb(x);

	printBitNumber(msb);

	return 0;
}

 

8192의 최상위 비트는 0010 0000 0000 0000 그 자체이다.

그리고 >> 1칸 미룬 값을 or 연산하면 1이 늘어난다.

마찬가지로, 2/4/8/16을 하면 모든 하위 비트에 1이 쓰여지게 된다.

그 이후 +1을 한 후, >> 1을 해주면 원래대로 8192가 된다.