Constants are shifts and adds

A constant shift is rewiring, so it costs nothing. A constant product becomes a few shifts plus adds.

Each extra 1 in the binary constant costs about one more adder. Sparse constants are nearly free.

Carry-in tricks

Subtraction reuses addition as a + ~b + 1. The 1 arrives as the carry-in, so no extra adder is needed.

The same carry-in gives increments and decrements for free. Tie one addend to zero and drive the carry-in with the 1.

8-bit example: a = 61, b = 27
bitwise NOT of b within 8 bits: 255 - 27 = 228
a - b as addition: 61 + 228 + 1 = 290; 290 - 256 = 34; check 61 - 27 = 34
carry out is 1 because 290 >= 256, so a < b (unsigned) is false
increment through the carry-in: 61 + 0 + 1 = 62 with B tied to 0

Width pitfalls of shifts

A left shift widens the value: a shifted by 3 needs 3 more bits. Storing back into the original width silently drops the top bits.

Size the whole adder chain for the widest shifted term. Then wreduce trims whatever the result keeps.

A runnable shift-add proof

The program below checks x13 shift-add against multiplication on all 256 byte values. It also proves the subtract and carry rules on all 65536 operand pairs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import sys

def adds_for_const(n):
    return bin(n).count("1") - 1

bad = 0
for a in range(256):
    if ((a << 3) + (a << 2) + a) != 13 * a:
        bad = bad + 1
    if (((a << 3) + (a << 2) + a) & 0xFF) != (13 * a) & 0xFF:
        bad = bad + 1
for a in range(256):
    for b in range(256):
        s = a + (b ^ 0xFF) + 1
        if (s & 0xFF) != (a - b) & 0xFF:
            bad = bad + 1
        carry = s >> 8
        if carry != (0 if a < b else 1):
            bad = bad + 1
if adds_for_const(13) != 2:
    bad = bad + 1

if bad != 0:
    print("FAIL: " + str(bad) + " bad cases")
    sys.exit(1)

print("PASS: shift-add matches multiply on 256 cases and carry rules hold on 65536 cases")

Related topics

• wreduce and operator widths

• Multipliers and Compressors

• Comparators and Shifters