비트 연산자
비트 연산은 컴퓨터의 기본 연산이기 때문에 속도가 빠릅니다.
And(&) 연산자
- 두 수를 이진법으로 표현합니다.
- 각 자리에 적힌 bit에 대해 and 연산을 진행합니다.
- 10진수로 표현합니다.
예시는 다음과 같습니다. ( 5 & 6 )
101 (5)
110 (6)
and ----------
100 (4)
or(|) 연산자
- 두 수를 이진법으로 표현합니다.
- 각 자리에 적혀있는 bit에 대해 or 연산을 진행합니다.
- 10 진수로 표현합니다.
예시는 다음과 같습니다. ( 5 | 6 )
101 (5)
011 (3)
or ----------
111 (7)
xor 연산자 (^)
주로 x를 상태 반전할 때 사용합니다.
- 두 수를 이진법으로 표현합니다.
- 각 자리에 적혀있는 bit에 대해 xor 연산을 진행합니다.
- 10진수로 표현합니다.
예시는 다음과 같습니다. (5 ^ 3)
101 (5)
011 (3)
xor ----------
110 (6)
left shift(<<) 연산자
값이 두배가 됩니다.
- a를 이진법으로 표현합니다.
- 모든 bit을 왼쪽으로 b번 밉니다.
- 10진수로 표현합니다.
예시는 다음과 같습니다.
5 = 0000101 (5)
5 << 1 = 0001010 (10)
5 << 2 = 0010100 (20)
5 << 3 = 0101000 (40)right shift(>>) 연산자
값이 1/2배 됩니다.
- a를 이진법으로 표현합니다.
- 모든 bit를 b번 오른쪽으로 밉니다.
- 10진수로 표현합니다.
예시는 다음과 같습니다.
13 = 0001101 (13)
13 >> 1 = 0000110 (6)
13 >> 2 = 0000011 (3)
13 >> 3 = 0000001 (1)비트 마스크
정수 하나를 표현하기 위해 32bit를 사용합니다.
만약 0~31까지의 요소를 중복 없이 사용하는 문제가 주어진다면 두가지 방법으로 해결할 수 있습니다.
- 32 크기의 boolean 배열을 만들기
- 하나의 수에서 비트 마스킹으로 표현하기
비트 마스킹으로 사용여부를 표현한다면 다음과 같이 사용할 수 있습니다.
x 상황
00000000000000000000000000000000 (0) : 아무 수도 없는 경우
00000000000000000000000000001010 (10) : 1, 3만 있는 경우
00000000000000000000000000100111 (39) : 0, 1, 2, 5만 있는 경우
00000000000000000000000001000000 (64) : 6만 있는 경우 수가 존재하는지 여부 확인
현재 수 2가 존재하는지 x를 통해서 알아보고자합니다.
이 경우에는 간단하게, 오른쪽에서 3번째 수가 1인지를 알아내면됩니다.
-
right shift 연산자를 이용해 x를 오른쪽으로 2칸 밉니다.
x 00000000000000000000000000100111 (39) x >> 2 00000000000000000000000000001001 (9) -
가장 오른쪽 bit가 1인지 확인합니다.
x 00000000000000000000000000100111 (39) x >> 2 00000000000000000000000000001001 (9) (x >> 2) & 1 00000000000000000000000000000001 (1)어떤 수가 주어졌을 때 가장 마지막 bit를 찾아내는 방법은 알아내기 원하는 bit에만 1을 넣고 나머지에 전부 0을 넣었을 때 나오는 값과 and 연산을 진행합니다.
-
만약 존재하지 않는 경우의 연산은 다음과 같이 진행됩니다.
x 00000000000000000000000000100011 (35) x >> 2 00000000000000000000000000001000 (8) (x >> 2) & 1 00000000000000000000000000000000 (0)
수를 새롭게 추가하거나 삭제
0,1,2,5만 있는 경우에서 4를 추가해봅시다.
-
오른쪽에서 5번째 bit만 1인 수를 만든 뒤, 기존 x와 이 수를 더합니다.
x 00000000000000000000000000100011 (35) 1 << 4 00000000000000000000000000010000 (16) x + (1 << 4) 00000000000000000000000000110011 (51)
- 참고로 더하는 것 대신, or나 xor 연산을 사용해도 무방합니다.
- xor를 사용할 경우 존재하는 수를 제거하는 것도 가능합니다.
정리
즉, x ^ (1 << k)는 수 k가 있다면 없애고, 없다면 새로 만들어주는 역할을 해주게 됩니다.
모든 수를 한번에 다 채우기
(1 << 5) - 1 00000000000000000000000000011111 (31)숫자들의 비트가 겹치지 않을 경우
숫자들의 총합과 숫자들의 or 연산 값이 같습니다.
예제
bit 계산
문제 보러가기
->
https://www.codetree.ai/missions/9/problems/bit-calculation?&utm_source=clipboard&utm_medium=text
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokens;
private static int add(int set, int data){
if(print(set,data)==1) return set;
return set^(1<<data);
}
private static int delete(int set, int data){
if(print(set,data)==0) return set;
return set^(1<<data);
}
private static int print(int set, int data){
return (set>>data)&1;
}
private static int toggle(int set, int data){
return set^(1<<data);
}
private static int clear(){
return 0;
}
public static void main(String[] args)throws IOException {
int commandNum = Integer.parseInt(buffer.readLine());
StringBuilder result = new StringBuilder();
int set = 0;
for(int commandIdx = 0 ; commandIdx<commandNum; commandIdx++){
tokens = new StringTokenizer(buffer.readLine());
String command = tokens.nextToken();
if(command.equals("add")){
int data = Integer.parseInt(tokens.nextToken());
set = add(set, data);
}else if(command.equals("delete")){
int data = Integer.parseInt(tokens.nextToken());
set = delete(set, data);
}else if(command.equals("print")){
int data = Integer.parseInt(tokens.nextToken());
result.append(print(set, data)).append("\n");
}else if(command.equals("toggle")){
int data = Integer.parseInt(tokens.nextToken());
set = toggle(set, data);
}else if(command.equals("clear")){
set = clear();
}
}
System.out.println(result);
}
}```
ㅣ