# Electronic – Get number of set bits in digital logic

digital-logic

As an exercise, I am trying to design an implementation of Conway's Game of Life in simple digital logic. I could do the whole thing by minimizing a 9-Variable function, but I imagine that will still be fairly large. One of the core elements of the algorithm is determining how many of your 8 neighbors are 'alive'.

Given 8 inputs, what is the easiest way to determine how many are set? Particularly I need an output that is high when 2 are set, and an output that is high when 3 are set.

My main idea now consists of a PISO shift register, a counter, and a 3:8 decoder, but I pretty much need a microcontroller to drive all of that. It does not seem like that complicated of a function. Maybe a 256×2 ROM would work as well, but my searches haven't turned up any of that kind of part.

I know that any pic with 10 IO could do this trivially, but I want to implement it in as minimal a way as reasonably possible.

You might find the various algorithms on Fast Bit Counting enlightening. The last two: Nifty Parallel Count and MIT HAKMEM Count might well be easy to convert into gates. See this page for a good explanation of how it works.

You could do this using gates hardware. Use four 1-bit adders to add pairs of bits together. This gives you four 3-bit numbers. Add these in pairs using two 3-bit adders. This gives you two 4-bit numbers to add using a single 4-bit adder. This leaves you with a 5-bit value, but you can ignore the top bit. Then use two 4-bit comparators to test for the values 2 and 3.

For minimal parts count, why not do it Analog?

Create a voltage divider with one resistor on top, and your 8 inputs connected to the bottom by 8 resistors in parallel. Then simply use two comparators set to detect the voltage levels that 2 or 3 bits will produce. That's only 6 parts: The 8-resistor network will produce a voltage between 0v (for 0-bits set) to 5v (for 8 bits sets). 2 bits will produce 0.5v. 3 bits will produce 1.56v.

• With 0 or 1 bits, the output will be 00.
• With 2 or 3 bits, the output will be 01.
• With 4 or more bits, the output will be 11. 