Java
Java) 비트연산자 정리 feat) 백준 1740
가짜 개발자
2021. 8. 31. 16:31
비트 연산자
- 비트 연산자는 low-level의 연산자이며, 논리 연산자와 비슷하지만, 비트 단위로 논리 연산을 할 때 사용하는 연산자.
- 비트 단위로 왼쪽, 오른쪽으로 전체 비트를 이동하거나, 1의 보수를 만들 때도 사용.
- 실수(Double), Boolean, 배열(Array), 객체(Object)에는 사용할 수 없다. 만약 boolean 연산자를 사용하고 싶다면 |, &, ^ 연산 등을 사용해야 한다.
&(AND 연산자) - 대응되는 두 비트가 모두 1일 때만 1을 반환, 다른 경우 0 반환.
- 각 비트와 연산을 하기 때문에 아래의 예제처럼 각 비트가 모두 1인 경우 1을 반환한다.
int a = 2;
int b = 3;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
System.out.println(Integer.toBinaryString(a & b));
System.out.println((a & b));
output:
10
11
10
2
|(OR 연산자) - 대응되는 두 비트 중 하나라도 1이면 1반환, 두 비트 모두 0일 때 0 반환.
- 서료 비교하는 비트에 하나라도 1이 들어가 있으면 아래와 같이 1을 반환한다.
int a = 18;
int b = 7;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
System.out.println(Integer.toBinaryString(a | b));
System.out.println((a | b));
output:
10010
111
10111
23
^(XOR 연산자) - 대응되는 두 비트가 서로 다르면 1 반환, 같으면 0 반환.
- Exclusive OR이라고도 하며, 두 개의 비트가 1로 같으면 0을 반환한다.
int a = 10;
int b = 7;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
System.out.println(Integer.toBinaryString(a ^ b));
System.out.println((a ^ b));
output:
1010
00111
1101
15
~(NOT 연산자) - 해당 비트가 1이면 0 반환, 0이면 1 반환. 보수를 알기위해 연산으로 사용.
- 12의 바이너리 표현은 1100, 이를 보수 연산을 하면 0011로 바뀐다. 출력된 바이너리 확인을 위해 Integer.toBinaryString() 사용해보면 32비트(8바이트)로 변경된다.
- 0xFF를 사용하여 8비트로 표현 가능하다. 0 xFF는 10진수 255, 2진수 11111111을 16진수로 나타낸 것.
- 0 xFF는 의도치 않게 채워진 1을 전부 0으로 바꾸기 위해 수행. byte형은 8비트의 공간을 차지하고, int는 32비트의 공간을 차지한다. 비트 연산자 &를 수행하면, 비트수가 넓은 곳에 맞춰 낮은 비트를 가진 자료형을 확장한다. 그래서 byteData & 0xFF를 하면 byte는 32비트의 int형으로 강제 형 변환이 되고 이때 byteData의 가장 앞 비트가 0인 경우는 0으로, 1인 경우는 1로 모든 비트를 채워 확장한다. 이런 경우 원본 값과 전혀 다른 값이 되기에 & 0xFF와 비트 연산을 수행.
byte b = 12;
System.out.println(Integer.toBinaryString(b));
System.out.println(Integer.toBinaryString(~b));
System.out.println(Integer.toBinaryString(~b & 0xFF));
output:
1100
11111111111111111111111111110011
11110011
<<(Left 쉬프트 연산자)
- 비트를 왼쪽으로 옮긴다. 0001이라는 비트가 있으면 <<1을 수행하면 1칸 왼쪽으로 밀어서 0010이 된다.
- 0001 =1, 0010 << 1 = 2, 0100 << 2 = 4 이처럼 쉬프트 연산은 2^n의 특징을 가지고 있다. 1만큼 쉬프트 연산을 수행하면 2^1 숫자가 int형에 곱해진다.
int a = 10;
int b = 7;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
System.out.println(Integer.toBinaryString(a << 1));
System.out.println(Integer.toBinaryString(b << 3));
output:
1010
111
10100
111000
>>(Right 쉬프트 연산자)
- left 반대로 오른쪽으로 민다. Left 쉬프트 연산은 2^n을 곱하는 규칙이 있었는데, Right 쉬프트 연산은 2^n을 나누는 규칙이 있다.
int a = 10;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(a >> 1));
output:
1010
101
- 비트의 이동으로 새로 생기는 왼쪽 비트들은 양수일 경우 모두 0으로 채워지고, 만약 피연산자가 음수라면 빈 공간을 1로 채운다. 이는 부호(음수)를 지속적으로 유지시키기 위함이다.
int a = -10;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(a >> 1));
output:
11111111111111111111111111110110
11111111111111111111111111111011
>>>(Unsigned Right 쉬프트 연산자)
- >>> 연산은 부호 비트까지 포함하여 모든 비트를 전부 오른쪽으로 이동시킨다. 이때 비트의 이동으로 새로 생기는 왼쪽 비트들은 전부 0으로 채워진다.
- 따라서 피연산자가 양수인 경우 부호 비트를 이동하지 않는 >> 와 같은 결과 반환. 음수인 경우 부호 비트까지 이동하므로 전혀 다른 결과가 반환.
int b = -2147483648;
System.out.println(Integer.toBinaryString(b >>> 1));
System.out.println(Integer.toBinaryString(b >>> 30));
output:
1000000000000000000000000000000
10
https://www.acmicpc.net/problem/1740
결론은 위의 유형과 같은 문제를 풀기 위해 비트 연산자와 이진법을 정리해야겠다는 생각이 들었습니다.
풀이
- 3의 제곱수를 2진수로 바꾼 후에 3진수를 이용해서 다시 10진수로 바꾸는 것.
long n = Long.parseLong(br.readLine());
Queue<Long> queue = new LinkedList<>();
while (n != 0) {
queue.add(n % 2);
n /= 2;
}
long answer = 0;
long mul = 1;
while (!queue.isEmpty()) {
answer += queue.poll() * mul;
mul *= 3;
}
Preference
반응형