# Logic circuit to handle incrementing by 1

You can use cascaded full adders to add any two binary numbers together. Is there a circuit for when I only want to add 1 (incrementing the value)? Is there a similar circuit for subtracting (i.e. adding 0b1111 1110)? I'm working with 8 bit numbers, but this applies for all word lengths.

• A circuit besides a full adder? You could just use one where one set of inputs is static, either 00...01 (++) or FF...FF (--) You could optimize/eliminate some of the input gates with the knowledge of constant inputs. – Nick T Dec 14 '10 at 15:45
• @Nick T, I was thinking of doing this but wasn't certain how to approach it. – Thomas O Dec 14 '10 at 15:53
• You could feed the carry-in line, but I suspect you don't have access to silicon... – tyblu Dec 14 '10 at 22:50

Let's see. In a simple ripple carry adder, sum,carry-out = a + b + carry-in

c = carry-in
for i in n
sum[i] = a[i] ^ b[i] ^ c[i]
c[i+1] = (a[i]&b[i]) | (a[i]&c[i]) | (b[i]&c[i])
carry-out = c[n]


Now if we want to compute sum,carry-out = a + 0 + 1, set b[] = all 0 and simplify:

c = 1
for i in n
sum[i] = a[i] ^ c[i]
c[i+1] = a[i] & c[i]
carry-out = c[n]


which is simpler. Subtraction by 1 can be similarly simplified (exercise for reader: what is b[] and carry-in in that case?)

Happy hacking!

If you're talking about discrete logic, like 7400 series logic, then the chip you're looking for is called a counter. Two 74191 (4-bit up/down synchronous counter) chips cascaded will give you what you want, and there are other chips that do a similar function.

If you want the most compact way to add '1', then you could use half-adders for each bit instead of full adders. Not too sure about subtraction though.

• Thanks. I'm considering building a transistor computer so whereever I can save transistors it is good. – Thomas O Dec 14 '10 at 15:53
• Transistor computers are easy to make when you're building the transistors on a single silicon wafer :) – W5VO Dec 14 '10 at 16:07
• Food for thought, if you're talking about making a discrete transistor CPU: The Intel 4004 (4 bit CPU) has 2300 transistors (excluding main ROM/RAM, and I/O. – W5VO Dec 14 '10 at 17:01
• @Thomas: I don't want to discourage you, but even the most simple CPU needs a few thousand transistors and the more components the greater the chance that something is wrong somewhere. I wouldn't want to debug it anyway. Why don't you build one with standard 74HCxx logic? This may increase your chances considerably, and it should be a serious challenge too. – stevenvh Dec 14 '10 at 17:14
• @stevenvh Actually I should have written relay computer and it's been done before (web.cecs.pdx.edu/~harry/Relay/.) I doubt I'd actually build it, but it would be a design project to do in my spare time. – Thomas O Dec 14 '10 at 17:29

What you are looking for is a edge triggered T-triggers. Input = output of previous stage AND count clock.

Here is schematics for transistor-based T-trigger:

http://forum.cxem.net/index.php?app=core&module=attach&section=attach&attach_rel_module=post&attach_id=45908

In the diagrams, lines to the right are outputs and all others (from the top, bottom or left) are inputs.

next                 b0                     b1                   b2
number   B0 ─ XOR ─┬──┘        B1 ─ XOR ─┬──┘        B2 ─ XOR ─┬──┘
counter     ┌──┘   └─ NOT ─┐      ┌──┘   └─ NOT ─┐      ┌──┘   └─ NOT ─┐
1 ─┴──────────── AND ─c1─┴──────────── AND ─c2─┴──────────── AND ──  ...

c = 1                 | Note: sum[i] =              c[ i ]      + B[i]
for i in n               |              =            2*c[i+1]      + b[i]
b[ i ] =  B[i] ^ c[i]  |              =              c[i+1] <<1  + b[i]
c[i+1] = ~b[i] & c[i]  |              = (~b[i]      & c[i]) <<1  + b[i]
carry-out = c[n+1]       |              =                        (B[i] ^ c[i]) +
|            (~(B[i] ^ c[i]) & c[i]) <<1


If a half adder must be used:

                                                                    b[i]
B ────┬── XOR ────      to use a half   B[i] ──┬───────┬───── XOR ────┘
┌──────┘   half     adder without          │   ┌─ XOR ─────┘
│ └────┐   adder    circuit trace         XOR ─┤
C ──┴──── AND ────      crossings you          │   └─ XOR ─────┐
can use this:   C[i] ──┴───────┴───── AND ─ c[i+1] ── ...


A simple decrement is a complemented negation: D-1 = ~-D.
Negation is 2's complement which is an incremented complement: -D = ~D +1.

Thus, D-1 = ~(~D +1), so a bit-wise combinational (parallel) complementation before and after a sequential incrementation suffices.

However, https://en.wikipedia.org/wiki/Half_subtractor the sequential decrement circuit is even simpler:

 previous                  d0                 d1                 d2
count       D0 ── XOR ─┬──┘    D1 ── XOR ─┬──┘    D2 ── XOR ─┬──┘
(decrement)       ┌──┘   └──┐        ┌──┘   └──┐        ┌──┘   └──┐
1 ─┴─────── AND ─ b1 ─┴─────── AND ─ b2 ─┴─────── AND ──  ...

b = 1
for i in n
d[ i ] =  D[i] ^ b[i]
b[i+1] =  d[i] & b[i]
borrow-out = b[n+1]