Java) 비트연산자 정리 feat) 백준 1740

---

 

비트 연산자

• 비트 연산자는 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

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

byte 16진수 문자열 변환

비트연산자