두 정수 a, b가 주어질때 xor(a, b)는 두 정수의 같은 자리 비트를 비교하여

비트가 서로 다른 자리만 1로 남긴다. (xor연산 참조 - 3293 : 비트연산1 )

예를 들어 a = 15, b = 5 이라고 할 때,

각각을 4비트 이진수로 바꾸면 a = 1111(2), b = 0101(2) 가 된다.

a와 b를 xor연산한 결과 ret = 1010(2) 이 된다.

우리는 xor 연산의 결과로 얻어진 결과에서 비트가 1인 개수에 관심이 있다.

N( 10 <= N <= 100,000)개의 32bit 정수 A[i] ( 0 <= i < N)가 주어진다.

함수 pcxor(A[i], A[j]) (0 <= i, j < N)는 A[i]와 A[j]를 xor연산한 결과의 비트수를 구하는 함수이다.

모든 (i, j)쌍에 대하여 pcxor(A[i], A[j]) (0 <= i, j < N)의 총합을 구하고

이를 10억 7로 나눈 나머지를 구하는 프로그램을 작성하시오.

아래 예를 설명하면 다음과 같다.

N = 3

A = {1, 2, 3}

pcxor(A[0], A[1]) => 001 ^ 010 = 011 => 2개

pcxor(A[0], A[2]) => 001 ^ 011 = 010 => 1개

pcxor(A[1], A[0]) => 010 ^ 001 = 011 => 2개

pcxor(A[1], A[2]) => 010 ^ 011 = 001 => 1개

pcxor(A[2], A[0]) => 011 ^ 001 = 010 => 1개

pcxor(A[2], A[1]) => 011 ^ 010 = 001 => 1개

출력결과 : 2 + 1 + 2 + 1 + 1 + 1 = 8

비트연산2 (popcount_xor) timer 1s memory 256MB

비트연산2 (popcount_xor) 1s 256MB