riella98   1년 전

답에 관한 스포일러가 될수도 있습니다

1. 우선 올림을 하지않는 이진수끼리의 덧셈을 xor 연산으로 대체할 수 있는건 많이들 아실거 같습니다.

2. 그리고 x가 0이면 수가 같은 경우만 세어도 되어 최적화가 가능하다는 점도요

3. 마지막으로 xor 식으로 아래를 유도할 수 있다는 점입니다.

int1 xor int2 = x라고 하면

xor이 associative 혹은 commutative 하므로 아래 굵게 된 부분을 유도할 수 있습니다.

int1 xor (int1 xor int2) = int1 xor x

같은 수끼리의 xor값은 0

-> 0 xor int2 = int1 xor x

0과 xor하는건 그 값 그대로

-> int2 = int1 xor x

따라서 v내의 각 원소의 개수만 안다면 계산이 가능합니다.

댓글을 작성하려면 로그인해야 합니다.