Assume we are given an $n$-bit number $s=(s_0\dots s_{n-1})_2$ in binary representation and we want to evaluate the sum $\sum_{i=0}^{n-1}s_i2^i$. In the worst case, when all $s_i=1$, this becomes a sum of $n$ elements (assuming the $2^i$ are already known).
I am currently looking at ways to optimize this for multiple $n$-bit numbers by partially computing them at the same time. For example, if we have $N=2$ numbers, e.g. $s=(s_0\dots s_{n-1})_2$ and $r=(r_0\dots r_{n-1})_2$, then the worst case cost can also be reduced to a sum of $n$ elements (instead of $2n$) as follows. Let $R=\{i\mid r_i=1\}$ and $S=\{i\mid s_i=1\}$, then we can first compute $$ t=\sum_{i\in R\cap S}r_i2^i\,,\quad\text{ and then }\quad s=t+\sum_{i\in S\backslash R}s_i2^i \quad\text{and}\quad r=t+\sum_{i\in R\backslash S}r_i2^i\,, $$ which gives a total of $\#(R\cap S)+\#(S\backslash R)+\#(R\backslash S)=\#(R\cup S)$ summands. In the worst case, $\#(R\cup S)=n$.
I've been trying to find a similar approach for higher $N$, but I am already struggling with the case $N=3$, especially since the sets (such as $S$ and $R$) don't add up as nicely as for $N=2$. I realized that the approach for $N=2$ can be easily extended to any even integer $N=2k$ by evaluating the numbers pairwise, thus at least giving an upper bound of $kn$ summands in these cases. Is there maybe a straightforward approach I don't see, or already something in the literature about these approaches? I guess there should be some kind of closed formula for given $n$ and $N$, but I can't seem to find it, maybe since I don't exactly know what to search for.
Thank you very much for any leads!