비트 연산자는 비트(bit) 수준에서의 연산을 수행하는 연산자로, 이진수를 다룰 때 유용하게 사용된다.
Java에서 제공하는 주요 비트 연산자는 다음과 같다.
& : 논리곱(AND) 연산자. 두 비트가 모두 1일 때만 1을 반환한다.
| : 논리합(OR) 연산자. 두 비트 중 하나가 1일 때 1을 반환한다.
^ : 배타적 논리합(XOR) 연산자. 두 비트가 서로 다를 때 1을 반환한다.
~ : 부정(NOT) 연산자. 비트를 반전한다.
<< : 왼쪽 시프트(Left shift) 연산자. 비트를 왼쪽으로 이동한다.
>> : 오른쪽 시프트(Right shift) 연산자. 비트를 오른쪽으로 이동한다.
>>> : 부호 없는 오른쪽 시프트(Unsigned right shift) 연산자. 비트를 오른쪽으로 이동한다.
이러한 비트 연산자들은 보통 정수형 변수와 함께 사용되며, 이진수(bit) 연산을 수행할 때 유용하다.
일단 개념정리를 위해 예제소스를 한번 살펴보자
//비트 연산자 개념정리
public class Example {
public static void main(String[] args) {
int a = 0b0101; // 5
int b = 0b1010; // 10
int c = a & b; // 0b0000 (0)
int d = a | b; // 0b1111 (15)
int e = a ^ b; // 0b1111 (15)
int f = ~a; // 0b1010 (-6)
int g = a << 1; // 0b1010 (10)
int h = a >> 1; // 0b0010 (2)
int i = a >>> 1; // 0b0010 (2)
System.out.println(c);
System.out.println(d);
System.out.println(e);
System.out.println(f);
System.out.println(g);
System.out.println(h);
System.out.println(i);
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int xor = nums[i] ^ nums[j];
sum += xor;
}
}
System.out.println(sum);
}
}
코드가 쉽고 단순하다. 그래서 "시간초과" 당했다.
이래저래 수정해서 아래와 같이 최종 수정했더니 겨우 통과되었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(br.readLine());
}
long sum = 0;
for (int i = 0; i < 31; i++) {
long count = 0;
for (int j = 0; j < n; j++) {
if (((nums[j] >> i) & 1) == 1) {
count++;
}
}
sum += count * (n - count) * (1L << i);
}
System.out.println(sum);
}
}