9. [7] What is the sum of all numbers between 0 and 511 inclusive that have an even number of $1 \mathrm{~s}$ when written in binary?
Answer: 65408 Call a digit in the binary representation of a number a bit. We claim that for any given $i$ between 0 and 8 , there are 128 numbers with an even number of $1 \mathrm{~s}$ that have a 1 in the bit representing $2^{i}$. To prove this, we simply make that bit a 1 , then consider all possible configurations of the other bits, excluding the last bit (or the second-last bit if our given bit is already the last bit). The last bit will then be restricted to satisfy the parity condition on the number of $1 \mathrm{~s}$. As there are 128 possible configurations of all the bits but two, we find 128 possible numbers, proving our claim.
Therefore, each bit is present as a 1 in 128 numbers in the sum, so the bit representing $2^{i}$ contributes $128 \cdot 2^{i}$ to our sum. Summing over all $0 \leq i \leq 8$, we find the answer to be $128(1+2+\ldots+128)=$ $128 \cdot 511=65408$