[출처 : http://javawork.egloos.com/2297723]
비트를 다루는 문제는 인터뷰에서 자주 출제되는 문제입니다. 한국에서는 코드 가독성 및 유지보수 문제로 이런 코드는 잘 쓰지않는 것으로 아는데, 외국에서는 콘솔에서 게임 만들때 사용하던 방법이라 아직도 많이 사용하는 것 같습니다.
가장 오른쪽의 1 -> 0
1011 -> 1010
1110 -> 1100
x = x & (x - 1);
가장 오른쪽의 0 -> 1
1100 -> 1101
1001 -> 1011
x = x | (x + 1);
가장 오른쪽 비트가 1인가
1101 -> true
1000 -> false
bool result = x & 1;
가장 오른쪽의 1을 끝까지 연장
100 -> 111
1000 -> 1111
1010 -> 1011
10100 -> 10111
x = x | (x - 1);
가장 오른쪽의 1을 끝까지 연장(좌측 비트들은 버림)
100 -> 111
1000 -> 1111
1010 -> 11
10100 -> 111
x = x ^ (x - 1);
1인 비트 세기 #1
1101 -> 3
unsigned int v = 13; // count the number of bits set in v
unsigned int c = 0; // c accumulates the total bits set in v
for (c = 0; v; v >>= 1)
{
c += v & 1;
}
1인 비트 세기 #2
unsigned int v = 13; // count the number of bits set in v
unsigned int c = 0; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
비트 뒤집기
11001010 -> 01010011
10101111 -> 11110101
unsigned char v = 202; // input bits to be reversed
unsigned char r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end
for (v >>= 1; v; v >>= 1)
{
r <<= 1;
r |= v & 1;
s--;
}
r <<= s; // shift when v's highest bits are zero
오른쪽의 연속적인 0비트 세기
1101000 -> 3
1000010 -> 1
unsigned char v = 104; // input to count trailing zero bits
int c = 0; // output: c will count v's trailing zero bits,
// so if v is 1101000 (base 2), then c will be 3
if (v)
{
v = (v ^ (v - 1)) >> 1; // Set v's trailing 0s to 1s and zero rest
for (c = 0; v; c++)
{
v >>= 1;
}
}
else
{
c = CHAR_BIT * sizeof(v);
}