Disjoint subsets and Number of 1's in the binary representation For a subset $S$ of $[n]$, let $\chi(S)$ denote the $n$ bit 'characterisitc vector' of $S$, i.e., $\chi(S)=(a_1, a_2, \ldots, a_n)$ where $a_i=1$ if $i \in S$ and $a_i=0 $ if $i \notin S$. Think of $\chi(S)$ as an $n$ bit binary number and let $D(\chi(S))$ denote the decimal representation of $\chi(S)$.
Let $A, B \subseteq [n]$. The question is to show that $A \cap B = \varnothing$ if and only if the number of 1's in the binary representation of $D(\chi(A))+ D(\chi(B)) = |A|+|B|$.
I could prove the forward direction:
Observe that $D(\chi(S))= \sum_{i \in S} 2^{n-i}$ and the number of 1's in $\chi(S)= |S|$.
Then if $A \cap B = \varnothing$, $$D(\chi(A))+ D(\chi(B)) = \sum_{i \in A} 2^{n-i} + \sum_{i \in B} 2^{n-i} = \sum_{i \in A \cup B} 2^{n-i} = D(\chi(A \cup B))$$
Then
\begin{equation}
\begin{split}
\text{number of 1's in the binary representation of }\ D(\chi(A))+D(\chi(B)) \\
= \text{number of 1's in the binary representation of}\ D(\chi(A \cup B)) 
= \text{number of 1's in}\ \chi(A \cup B)
= {|A \cup B|} 
=|A|+|B|
\end{split}
\end{equation}
To prove the converse, we have, 
\begin{equation}
\begin{split}
D(\chi(A))+ D(\chi(B)) & = \sum_{i \in A} 2^{n-i} + \sum_{i \in B} 2^{n-i} \\
 &= \sum_{i \in A \cup B} 2^{n-i} + \sum_{i \in A \cap B} 2^{n-i} \\
 &= D(\chi(A \cup B))+ D(\chi(A \cap B))
\end{split}
\end{equation}
But I don't quite see how to reach the conclusion from here. Hints will be appreciated.
 A: Let $B(n)$ be the number of ones in the binary representation of the integer $n$.
We have to show that if $a\&b\neq0$, $B(a+b)<B(a)+B(b)$.
Imagine we've set up the addition in the normal way:$$\begin{array}{rrrrrrr}&1&0&1&0&1&0\\+&0&1&1&1&0&1\\\hline&\end{array}$$
Let $B'(a), B'(b), B'(a+b)$ be the number of ones encountered so far while performing the addition: that is, in the columns to the right of an imaginary vertical line.
Performing the addition from right to left, $B'(a+b)$ will continue to equal $B'(a)+B'(b)$ so long as we only encounter ${0\atop0}$ or ${0\atop1}$ or ${1\atop0}$.
As soon as we meet ${1\atop1}$, we have to write $0$ in the sum. This causes $B'(a+b)$ to start lagging by $2$. Then three things can happen:


*

*The next thing we have to add is $0\atop0$. Then we write down the carry bit, and from now on, things proceed in a carryless state (as though we were starting afresh to the left of the line), but with $B'(a+b)$ lagging by $1$.

*The next thing we have to add is $0\atop1$ or $1\atop0$. Then we have to write down another $0$ in the sum, so $B'(a+b)$ is lagging by an extra $1$.

*The next thing we have to add is $1\atop1$. Then we write down $1$ in the sum, so again $B'(a+b)$ is lagging by an extra $1$.


Sooner or later we reenter the carryless state, but if $B'(a+b)$ ever lags by $2$ or more, only one point can be restored; there is no way to make up the lost ground.
