Bit addition arises virtually everywhere in digital circuits: arithmetic operations, increment/decrement operators, computing addresses and table indices, and so on. Since bit addition is such a basic task in Boolean circuit synthesis, a lot of research has been done on constructing efficient circuits for various special cases of it. A vast majority of these results are devoted to optimizing the circuit depth (also known as delay). In this paper, we investigate the circuit size (also known as area) over the full binary basis of bit addition. Most of the known circuits are built from Half Adders and Full Adders as suggested by Dadda in 1965 for designing multiplier circuits. Applying these ideas to the bit addition function, one gets a 5n-3m upper bound on its circuit size, where n is the number of input bits and m is the number of output bits. We prove an upper bound 4.5n-2m. In the regimes where m is small compared to n (for example, for computing the sum of n bits or multiplying two n-bit integers), this leads to 10% improvement. We also show that it is provably impossible to improve the two upper bounds above to 5n-3.01m or 4.5n-2.51m. We achieve this by establishing that the circuit size of the increment function (a special case of the bit addition function with m = n+1) is equal to 2n. We complement our theoretical result by an open-source implementation of generators producing circuits for bit addition and multiplication. The generators allow one to produce the corresponding circuits in two lines of code and to compare them to existing designs.

We present an open-source tool for manipulating Boolean circuits. It implements efficient algorithms, both existing and novel, for a rich variety of frequently used circuit tasks such as satisfiability, synthesis, and minimization. We tested the tool on a wide range of practically relevant circuits (computing, in particular, symmetric and arithmetic functions) that have been optimized intensively by the community for the last three years. The tool helped us to win the IWLS 2024 Programming Contest. In 2023, it was Google DeepMind who took the first place in the competition. We were able to reduce the size of the best circuits from 2023 by 12% on average, whereas for some individual circuits, our size reduction was as large as 83%.