📌 비트 마스킹(Bit-Masking)
컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다.
이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 한다.
📌 비트 연산자(Bitwise Operator)
비트마스킹에 사용되는 기본 연산자를 말한다.
| 비트 연산자 | 설명 |
| & | 대응되는 비트가 모두 1이면 1을 반환함 (비트의 AND 조건 연산) |
| | | 대응되는 비트 중 하나라도 1이면 1을 반환함 (비트의 OR 조건 연산) |
| ^ | 대응되는 비트가 서로 다르면 1을 반환함 (비트의 XOR 연산) |
| ~ | 비트를 1이면 0으로, 0이면 1로 반전시킴 (비트의 NOT 연산, 1의 보수) |
| << | 명시된 수만큼 비트들을 전부 왼쪽으로 이동시킴 (LEFT SHIFT 연산) |
| >> | 부호를 유지하면서 지정된 수만큼 비트를 전부 오른쪽으로 이동시킴 (RIGHT SHIFT 연산) |
| >>> | 지정한 수만큼 비트를 전부 오른쪽으로 이동시키며, 새로운 비트는 전부 0이 된다. |
※ 보수(Complement) : 보충해주는 수를 의미
어떤 수 A에 무언가를 더했을 때, 깔끔한 [N진법의 수]를 만들어 냈다면, 그 무언가를 A의 N의 보수라고 부른다.
✔️ AND(&) 연산
대응되는 두 쌍의 비트가 모두 1이면 1을 반환한다.
✔️ OR(|) 연산
대응되는 두 비트 중 하나라도 1이라면 1을 반환한다.
✔️ XOR(^) 연산
대응되는 두 비트가 서로 다르다면 1을, 같다면 0을 반환한다.
✔️ NOT 연산(~)
비트가 1이라면 0을 반환하고, 0이면 1을 반환한다.
✔️ LEFT SHIFT 연산(<<) - Arithmetic
비트의 칸 수를 주어진 숫자만큼 왼쪽으로 이동시킨다.
비트가 왼쪽으로 이동함에 따라 비워지는 비트는 0을 채워주고, 왼쪽으로 이동함에 따라 MSB 영역을 넘어가는 비트 공간은 제거한다.
해당 연산은 부호 비트를 제외한다.
※ MSB(Most Significant Bit) : 최상위 비트를 말한다.
✔️ RIGHT SHIFT 연산(>>) - Arithmetic
부호 비트를 제외한 비트의 칸 수를 주어진 숫자만큼 오른쪽으로 이동시킨다.
비트가 오른쪽으로 이동함에 따라 비워지는 비트는 1을 채워주고, 오른쪽으로 이동함에 따라 LSB 영역을 넘어가는 비트 공간은 제거한다.
해당 연산은 부호 비트를 제외한다.
※ LSB(Least Significant Bit) : 최하위 비트를 말한다.
✔️ RIGHT SHIFT 연산(>>>) - Logical
부호 비트를 포함하여 비트의 칸 수를 주어진 숫자만큼 오른쪽으로 이동시킨다.
비트가 오른쪽으로 이동함에 따라 비워지는 비트는 0을 채워주고, 오른쪽으로 이동함에 따라 LSB 영역을 넘어가는 비트 공간은 제거한다.
해당 연산은 부호 비트를 포함한다.
📌 비트 마스킹의 장점
- 빠른 수행시간
시간복잡도 O(1)에 구현되는 것이 많다.
비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이다. 때문에 큰 속도를 항상 기대할 수는 없지만 여러번 수행해야 하는 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있다. - 간결한 코드
양한 집합 연산자들을 반복문 없이 한 줄에 사용할 수 있다. - 작은 메모리 사용량
적은 메모리를 사용할 수 있다는 말은 데이터를 미리 계산하여 저장해 둘 수 있으므로 캐시 효율이 좋다는 의미이기도 하다. - 연관 배열을 배열로 대체
Map<String, Integer>와 같은 맵 객체를 단순 배열 int[]로도 사용할 수 있다.
📌 비트 마스킹의 활용
✔️ getBit
특정 인덱스의 비트 값을 가져온다.
class ImplBitMask {
// 해당 인덱스의 값에 1이 있다면 true, 없다면 false를 반환
static boolean getBit(int num, int i) {
return (num & (1<<i)) != 0;
}
public static void main(String[] args) {
// 1001 -> 1 : true
System.out.println(getBit(9, 3));
// 0101 -> 0 : false
System.out.println(getBit(5, 3));
}
}
✔️ setBit
특정 인덱스의 비트 값 1로 설정한다.
class ImplBitMask {
// 해당 인덱스의 값을 1로 변경해준다.
static int setBit(int num, int i) {
return num | (1<<i);
}
public static void main(String[] args) {
// 0101 -> 1101 : 13
System.out.println(setBit(5, 3));
}
}
✔️ clearBit
특정 인덱스에 있는 비트를 0으로 설정한다.
class ImplBitMask {
// 해당 인덱스의 값을 0으로 변경해준다.
static int clearBit(int num, int i) {
return num & ~(1<<i);
}
public static void main(String[] args) {
// 1001 -> 0001 : 1
System.out.println(clearBit(9, 3));
}
}
✔️ clearLeftBits
특정 인덱스 이상의 비트를 모두 0으로 설정한다.
class ImplBitMask {
// 해당 인덱스 이상의 비트를 모두 0으로 설정해준다.
static int clearLeftBits(int num, int i) {
return num & ((1<<i)-1);
}
public static void main(String[] args) {
// 10101001 -> 00000001 : 1
System.out.println(getBit(169, 3));
}
}
✔️ clearRightBits
특정 인덱스 이하의 비트를 모두 0으로 설정한다.
class ImplBitMask {
// 해당 인덱스 이하의 비트를 모두 0으로 설정해준다.
static int clearRightBits(int num, int i) {
return num & (-1<<(i+1));
}
public static void main(String[] args) {
// 10101001 -> 10100000 : 160
System.out.println(clearRightBits(169, 3));
}
}
✔️ updateBit
특정 인덱스의 값을 업데이트한다.
class ImplBitMask {
// 해당 인덱스에 특정 값의 비트를 업데이트해준다.
static int updateBit(int num, int i, boolean val) {
return (num & ~(1 << i)) | ((val? 1:0) << i);
}
public static void main(String[] args) {
// 10101001 -> 10100001 : 161
System.out.println(updateBit(169, 3, false));
}
}
✔️ 순열 구현(작성 예정중)
준비중입니다 ㅎㅎ;
📌 참조
[ 개념 ] 53. 비트마스킹(bit mask)
> 비트마스킹 bitmask : 정수의 이진수 표현을 자료구조로 쓰는 기법 데이터들은 0과 1의 집합이라고 합니다. 비트는 네트워크 외에도 운영체제 등에서도 자주 접할 수 있는데요 때문에 최적의 성
coder-in-war.tistory.com
[자료구조 알고리즘] 비트연산 완전정복 -Bit Operation
댓글