비트 연산에 대한 이해

Goal

• 정수 자료형과 비트 연산자에 대한 이해
• 비트 연산자의 활용

---

비트 연산자(bitwise operator)

bit 단위로 수행되는 논리 연산자

 

비트 연산자	설명
& (bitwise and)	대응 되는 비트가 모두 1인 경우에만 1반환 (logical AND 연산)
| (bitwise or)	대응 되는 비트 중 하나라도 1이면 1반환 (logical OR 연산)
^ (bitwise xor)	대응되는 비트가 서로 다르면 1을 반환 (logical XOR 연산)
~ (bitwise not)	비트의 반전(1 -> 0, 0 -> 1). 이진수의 (1의)보수값을 취하는 단항 연산자.
<< (left logical shift)	C계열 언어에서 << 연산은 logical shift 연산을 의미
>> (right logical/arithmetic shift)	C계열 언어에서 >> 연산은 unsinged 정수형에 대해서는 logical right shift 연산 수행 signed 정수형에 대해서는 arithmetic right shift 연산 수행

 

 

 

 

산술 Shift

1. Left : 새 비트를 0bit로 채움
2. Right : 새 비트를 부호 bit로 채움

Left arithmetic shift

Right arithmetic shift

논리 Shift

• Left, Right 모두 0bit로 채움

Left logical shift

Right logical shift

 

Circular shift도 있는데 산술, 논리 Shift와는 다르게 양끝 bit를 재활용하는 형식이다.

(산술, 논리 Shift는 밀려난 bit를 버린다.)

 

Bit연산 관련 용어

비트 필드(bit field)

인접한 비트들의 연속적인 공간

ex) 

- char : 8bit(1byte) 비트 필드를 갖는 자료형

- int, float : 32bit(4byte) 비트 필드를 갖는 자료형

 

비트 플래그(bit flag)

비트 필드에서 비트들의 상태값을 확인 하기 위한 특정 값

(깃발을 통해 어떤 상태를 확인하듯이, bit를 통해 어떤 상태를 확인 한다는 의미)

 

비트 플래그는 특정 상태값을 확인하거나, 비트를 조작하는데 사용 될 수 있다.

 

플래그(flag)라고도 한다. 굳이 구분하자면 어감상 다음과 같은 차이가 있을 수 있다.

• bit flag : 특정 단일 비트 값이 1로 세팅 되어 있는 경우
• flag : 1개 이상의 bit값이 1로 되어 있는 경우, bit flag를 결합해서 하나의 새로운 flag를 만들 수 있다.

 

비트 마스크(bit masking)

비트 연산에 사용되는 플래그

 

즉, 플래그인데 특정 연산에 사용될 때 마스크라고도 한다.

마스크를 사용한 비트 연산을 '비트 마스킹(bit masking)'이라고 한다.

 

활용 예

이미지 마스킹, IP 주소의 mask 값, 해시 테이블

---

비트 연산의 활용

MSB, LSB

MSB : Most Significant Bit (최상위 비트)

LSB - Least Significant Bit (최하위 비트)

 

설명

최상위 또는 최하위 비트는 특정 검사를 하기 위한 용도로 사용 되는 경우가 많다. (flag 값으로 활용)

단순히 1bit만 검사하는 경우도 있지만, 연속된 몇 bits를 조사하는 경우도 있다.

 

다음은 그림은 송신 데이터를 MSB로 받는 경우와 LSB로 받는 경우를 나타낸다. 

 

Left Shift, Right Shift

• << (Left Shift) : 곱하기 2연산에 활용 가능
• >> (Right Shift) : 나누기(/) 2연산에 활용 가능

비트연산자를 사용한 Masking (OR, AND, XOR, NOT)

비트연산자는 다음과 같은 용도로 사용될 수 있다.

• OR : 특정 비트 1로 세팅
• AND : 특정 비트 소거 가능
• XOR : 비트 toggle
• NOT : 픽셀 반전 (~x = 255 - x), 원래 이진수의 1의보수 값을 의미

 

비트 연산자를 활용해서 구현한 연산

• test : 비트 확인
• set : 비트를 1로 세팅
• reset : 비트를 0으로 세팅
• toggle : 비트 토글

구현 코드

/*
	플래그 값을 여러가지 방법으로 표현할 수 있다. 
	1. 십진수 표기(정수 리터럴)
	2. left shift 또는 right shift
	3. 16진수(hex)리터럴
	4. 바이너리 리터럴 - C++ 14 이후부터 제공

	1 == (1 << 0) == 0x01 == 0b0000'0001
	2 == (1 << 1) == 0x02 == 0b0000'0010
	4 == (1 << 2) == 0x04 == 0b0000'0100
	8 == (1 << 3) == 0x08 == 0b0000'1000
	16 == (1 << 4) == 0x10 == 0b0001'0000
	32 == (1 << 5) == 0x20 == 0b0010'0000
	64 == (1 << 6) == 0x40 == 0b0100'0000
	128 == 1 << 7 == 0x80 == 0b1000'0000

	shift연산이나 16 진수로 많이 표현된다.
*/

//플래그 선언
enum FLAG : unsigned char
{
	FLAG_1			= 1 << 0,
	FLAG_2			= 1 << 1,
	FLAG_3			= 1 << 2,
	FLAG_4			= 1 << 3,
	FLAG_5			= 1 << 4,
	FLAG_6			= 1 << 5,
	FLAG_7			= 1 << 6,
	FLAG_8			= 1 << 7,
};

//특정 비트가 1로 세팅 되어있는지 확인
bool test(unsigned char& val, FLAG flag)
{
	return (val & flag) != 0;
}

// 특정 비트를 1로 세팅(Masking bits to 1)
void set(unsigned char& val, FLAG flag)
{
	val |= flag; // | (or) 연산 사용
}

// 특정 비트를 0으로 세팅(Masking bits to 0)
void reset(unsigned char& val, FLAG flag)
{
	val &= ~flag; // & (and), not (~) 연산 사용
}

// 특정 비트를 토글(0 -> 1, 1 -> 0) - toggle bits
void toggle(unsigned char& val, FLAG flag)
{
	val ^= flag; // ^ (xor) 연산 사용
}

(bit조작을 쉽게 다루기 위해 std::bitset 타입을 따로 지원하기도 한다)

집합과 비트 연산자의 관계

 

이외에도 비트 연산을 사용해서 집합 관련 연산이 가능하다.

• 집합 크기 구하기 (켜저 있는 원소 갯수 구하기)
  • gcc/g++ : __builin_popcount(value)
  • Visual C++ : __popcnt(value)
• 최소 원소 찾기 (최하위 비트 이하의 비트는 모두 0값을 갖는다)
  • gcc/g++ : __builtin_ctz(value)
  • Visual C++ : _BitScanfForward(*index, mask)
• 최소 원소(최하위 비트) 찾기
  • int firstBit = (value & -value); // 음수 표현을 위해 2의 보수를 취한다는 것을 이용한 방법
• 최소 원소(최하위 비트) 지우기
  • value &= (value - 1); // 최소 원소가 무엇인지 몰라도 최소 원소를 지울 수 있다.
• 모든 부분 집합 순회
  • for(int subset = value; subset; subset = ((subset-1) & value)) { }