참고
다음과 같은 비트가 있다고 가정하자.
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가 된다.
'개발 > C, C++' 카테고리의 다른 글
scanf로 문자열과 공백 받기 (0) | 2021.03.16 |
---|---|
소수 판단 함수 (0) | 2021.03.14 |
C, C++ - 정수로된 FILE 입력 (1) | 2021.03.14 |
유일한 수 두개 (0) | 2021.03.01 |
유일한 수 (0) | 2021.03.01 |
댓글