Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations. Positions are numbered from 1 to 10^11. Every 3rd bit of a is equal to 1 (in other words bits number 3,6,9 and so-on), every 7th bit of b is equal to 1, every 4th bit of c is equal to 1, every 5th bit of d is equal to 1. The task is to determine the number of 1 bits in a ⊕ b ⊕ c ⊕ d, where ⊕ is bitwise XOR operation.

  • 1
    $\begingroup$ What are your thoughts about this question? $\endgroup$ – Yuval Filmus Dec 25 '20 at 11:24

The value of $(a \oplus b \oplus c \oplus d)_i$ depends on whether $i$ is divisible by $3,4,5,7$, and in particular, by $i \bmod 3\cdot 4\cdot 5\cdot 7$. In order to complete the calculation, you need to know, for each $j \in \{0,\ldots,3\cdot 4\cdot 5\cdot 7 - 1\}$, how many indices $i \in \{1,\ldots,10^{11}\}$ satisfy $i \equiv j \pmod{3\cdot 4\cdot 5\cdot 7}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.