[Algorithm] Bit 연산

알고리즘 문제에서 Bit연산 사용법

 

1. bit 연산의 종류 (총 6 가지)

and: &

or: |

not: ~

xor: ^

Lshift: <<

Rshift: >> 

 

 

2. 숫자 A의 i 번 비트를 반전

A ^= (1 << i)

//Ex) 5 ^= (1 << 2) 의 경우
5: 101
1 << 2 = 2 : 10

101 & 10 = 111

 

 

3. 숫자 A의 i번 비트를 1로 설정

A |= (1 << i)

//Ex) 5 |= (1 << 2) 의 경우
5: 101
1 << 2 = 2 : 10

101 | 10 = 111

 

 

4. 숫자 A의 i번 비트가 1 인지 확인

A &= (1 << i)

(A >> i) & 1

//Ex) (7 >> 2) & 1 의 경우
7: 111
7 >> 2 : 11

111 & 11 == 111 
즉 111 이므로 True

 

 

5. K - 1 길이를 1 로 구성된 숫자 (체크숫자) 생성

(1 << K) - 1;

//Ex) 길이가 K=4 인 (1111) 만들기
( 1 << 4 ) - 1
16 - 1 = 15
1111

 

 

6. 특정 input이 특정 값과 일치하는지

int checkBit = (1 << 4) - 1;
if((checkBit & inputNum) == checkBit)
{
	cout << "Pass" << "\n";
}

//특정 비트의 뒷 4 자리가 1 인 경우를 찾기
inputNum = 47 일 때

	42 : 0010 1111
  checkBit : 0000 1111
    answer : 0000 1111
 
 >> true