2830번 (행성X3)

비트 연산자는 비트(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);
    }
}