[하루한개념] 비트와 비트마스킹

Bit

: 데이터를 나타내는 최소 단위로 이진수의 한자리인 0 or 1을 값으로 갖는다.

• N비트의 정수형 변수는 N자리의 이진수로 나타낼 수 있다.
  • ex.4 byte인 int의 경우 32bit이기 때문에 2^0~2^31, 즉 2,147,483,648의 수를 표현할 수 있다.
• N비트가 표현하는 값은 2^0 ~ 2^N-1이다.
  • 2^0 을 최하위 비트(Least Significant Bit), 2^n-1을 최상위 비트(Most Significant Bit)라고 한다.

 

비트 연산자

비트 논리 연산자

1) & 연산자 (AND, 논리곱)

이진수로 표현된 2개의 피연산자의 각 비트자리값에 모두 1이 있다면 1로 표현 (두 비트 모두 1일 경우에만 연산 결과가 1) ex. 0011 0101 & 0101 0011 -> 0001 0001 (53 & 83 -> 17)

2) | 연산자 (OR, 논리합)

이진수로 표현된 2개의 피연산자의 각 비트자리값에 하나라도 1이 있다면 1로 표현 (두 비트 중 하나만 1일 경우에만 연산결과가 1) ex. 0011 0101 | 0101 0011 -> 0111 0111 (53 & 83 -> 119)

3) ^ 연산자 (XOR, 배타적 논리합)

이진수로 표현된 2개의 피연산자의 각 비트자리값이 동일하면 0 다르면 1로 표현 (두 비트중 하나는 1이고 다른 하나가 0일경우에만 연산결과가 1) ex. 0011 0101 ^ 0101 0011 -> 0110 0110 (53 ^ 83 -> 102)

4) ~ 연산자 (NOT, 보수)

이진수로 표현된 피연산자의 값을 반전시켜주어 표현 ex. 0011 0101 -> 1100 1010 (~53 -> 202)

 

비트 이동 연산자 (Shit 연산자)

1) x<<y

정수 x의 각 비트를 y만큼 왼쪽으로 이동시킨다.(빈자리는 0으로 채워짐) ex. 16 << 3 의 경우 0001 0000 (2^4, 16) -> 1000 0000 (2^7, 128)

2) x>>y

정수 x의 각 비트를 y만큼 오른쪽으로 이동시킨다.(빈자리는 a의 최상위 부호화 동일한 값으로 채워짐) ex. 16 >> 3 의 경우 0001 0000 (2^4, 16) -> 0000 0010 (2^1, 2)

3) x>>>y

정수 x의 각 비트를 y만큼 오른쪽으로 이동시킨다(빈자리는 0으로 채워짐) ex. 16 >> 3 의 경우 0001 0000 (2^4, 16) -> 0000 0010 (2^1, 2)

Bit masking

: 이진수를 이용해 연산을 하면 매우 빠르게 연산이 가능하단 특징을 이용해 자료구조로 사용하는 기법

• 비트가 1이면 켜져있다고 말하고 0이면 꺼져있다고 말한다.

장점

1. 수행시간이 빠르다. -> bit연산이기 때문에 O(1)에 구현되는 것이 많아 다른 자료구조보다 훨씬 빠르게 동작한다.
2. 코드가 간결해진다. -> 다양한 집합연산을 기존 제어문보다 비트연산자를 통해 한줄로 작성이 가능해 코드가 더 간결해진다.
3. 메모리 사용이 적다 -> 예시 코드(BOJ15787)에서도 볼 수 있듯이 int[][]으로 사용할 자료구조를 int[]로 구현해내 메모리 효율성을 높인다. -> ex. 5개의 연구소의 불이켜지고 꺼짐을 배열로 나타내면 boolean[]{true, false, false, true, true}지만 비트연산자로 표현하면 이진값이 10011인 19로 표현이 가능하다.

비트마스크의 집합 구현 (알아두면 구현에 용이하다)

• A를 집합 n개의 상태를 나타내는 변수라고 가정 (0~n-1원소를 갖는다)
• 이후 k의 의미는 k자리에 비트(혹은 원소)를 말한다.

연산집합 구현 예시비트 단위로의 설명

공집합	A=0	n자리의 0으로 채워진 값을 만든다
꽉 찬 집합	A = (1<<n)-1	n자리의 1로 채워진 값을 만든다
원소 추가	A	=(1<<k)
원소 삭제	A &= ~(1<<k)	k자리의 원소를 0으로 변경
원소 포함 확인	if((A & (1 << k)) == (1 << k))	k자리의 원소가 1인지 확인
원소 토글	A ^= (1<<k)	k자리의 원소가 1이면 0, 0이면 1로 변경
최소 원소 삭제	A &= (A - 1)	A의 가장 작은 원소를 삭제
합집합	A | B	A와 B 중 하나라도 1이면 1로 값을 표현
교집합	A & B	A와 B 모두 1이면 1로 값을 표현
차집합	A & (~B)	A와 B중 A에서만 1인 값만 1로 값을 표현

 

 

 

 

자료조사 출처목록

비트마스크(BitMask) 는 무엇인가? :: 마이구미

[알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java)