79brue의 PS 블로그

BOJ 15986. &+ +&먼저 모든 $A[i] \wedge B[j]$의 합을 구해 보자. $Acnt[x]$를 $A$의 원소들 중 $2^x$의 비트가 $1$인 것의 개수라고 하고, 마찬가지로 $Bcnt[x]$를 정의하자. 비트별로 따로따로 생각하면 답이 $\sum Acnt[i] Bcnt[i] 2^i$임을 쉽게 알 수 있다. 다음으로 모든 $A[i] + B[j]$의 AND 값을 구해 보자. 이것도 역시 비트별로 생각할 것이다. 즉, 모든 $A[i] + B[j]$ 값에 $2^i$의 비트가 켜져 있는지를 검사할 것이다. 먼저 $i=0$일 때부터 시작해 보자. $2^0$의 비트가 켜져 있으려면 $A$는 모두 홀수, $B$는 모두 짝수거나 그 반대여야 한다. $i$가 더 커지는 경우에는 어떻게 검사할 수 있을까..