I’ll walk through an algorithm to do addition using Python. Using bitwise operators and C++ extension modules results in nearly on-par performance with base Python addition.

I’ve recently been dealing with bytes and bits a lot. I thought I’d revisit some of the old algorithm problems I remember seeing back in the day. One classic problem is this:

Create an integer addition ‘+’ operator. Assume you can not use multiplication, division, or subtraction. For simplicity, assume inputs can only be non-negative integers.

Let’s first think of a simple naive solution to this. One way to do this would be to replicate long addition but optimize it using some simple memoization.

For long addition, you align the two numbers you want to add. Starting on the far right (first digit), you keep adding and carrying over terms if the two terms you’ve added are greater than 9.

We describe the algorithm in pseudo-code, then walk through a simple example.

Pseudo Code

We will explain more in-depth what this pseudo-code means using an example.

Walking through the pseudo-code

Let’s take an example for adding the two numbers 23 and 48. Think of these two numbers as two arrays of strings:

[‘2’, ‘3’] and [‘4’, ‘8’]

We align the numbers, then go right to left. At each position, we will only be adding two single digit numbers (such as 3+8 in position 1, and 2+4 in position 0).

Bring forward remainder term from prior step: (2+1, 4)

Remainder Step: remainder(3, 4) = 7

Carryover Step: carryover(3,4) = 0

Add remainder step to output array: [7, 1]

Final Step

Return concatenated array: 71

What we see is that in position 1, the remainder step gives us the digit in the output, whereas the carry-over step will increment the digits in the next position (ie position 0). We repeat this process, appending an output array using the remainder step until we have exhausted both arrays.

Python Code

Now for the python code. Unfortunately, it’s very complex. We won’t spend time refactoring this, because another solution is both more readable and faster.