# Boolean circuit - 4 bits divisible by 3

I need to draw a circuit taking a number on 4 bits that will return 1 only if that number is divisible by 3.

My initial steps were to draw a truth table from which I got a Boolean expression that cannot be simplified. I then drawn a Karnaugh Map, same result. It seems as though such Boolean expression would be really annoying to draw as is, I'm pretty sure they're an easier way.

My second thought was to use 4 "1 bit adder" in series, outputting the alternating sums; the last sum must be 0 in order to be divisible by 3. How would that work exactly? Would I need to carry the result of the addition even though it is pretty irrelevant to the whole circuit?

• This is an interesting question as perhaps I don't know the answer either. However, we can try to think about this, firstly, on a software perspective because at the end of the day, all software eventually leads to logic gates and 1's and 0's. I know for software, there exists a mathematical operation called, modulo, where you take value and find the remainder. So for instance, 6 mod 3 = 0 because if you divide 6 by 3, you get 2 but there's no remainder. But 5 mod 3 would be 2 because there's two left over. Hence if you say "NUMBER mod 3 = 0", it means the number is divisible by 3.
– user103380
Commented Dec 18, 2018 at 16:48
• Where I'm going with this is that it would be good if you could research how to implement modulo into logic design and see how it's done. I know with binary subtraction, it requires a binary adder (which seems contradictory but it's true!)
– user103380
Commented Dec 18, 2018 at 16:50
• It seems as though such Boolean expression would be really annoying to draw as is, I'm pretty sure they're an easier way. - No. Circuits are implementing functions. If you can't get simpler function, you won't get a simpler circuit. Commented Dec 18, 2018 at 16:58
• Can you use a MUX? Then the ask is trivial. Commented Dec 18, 2018 at 17:10

## General approach for $$\m\$$ bits

The general solution for a test for division by 3 is to sum up the even-numbered bits and separately sum up the odd-numbered bits, take the difference between these sums, and then see if the difference itself is divisible by 3. (There are a variety of approaches for this operation, but the one encountered first is usually via carry-save adders.)

For a binary value with $$\m\$$ bits, where $$\m\$$ is even, the difference will require at most $$\\lceil\operatorname{ln}_2\frac{m}{2}\rceil\$$ bits. For a binary value with $$\m\$$ bits, where $$\m\$$ is odd, the difference will require at most $$\\lceil\operatorname{ln}_2\frac{m+1}{2}\rceil\$$ bits. This difference result could itself then be submitted to a much smaller tier for, once again, computing the difference between the sums of even and odd numbered bits. (And repeat.)

## Specific case where $$\m=4\$$

At this point it is pretty easy to see that the even and odd sums can be computed using a simple half-adder, each. The resulting table is:

$$\begin{smallmatrix}\begin{array}{r|cccc} &\overline{C_\text{odd}}\:\overline{S_\text{odd}}&\overline{C_\text{odd}}\:S_\text{odd}&C_\text{odd}\:\overline{S_\text{odd}}\\ \hline \overline{C_\text{even}}\:\overline{S_\text{even}}&Y&N&N\\ \overline{C_\text{even}}\:S_\text{even}&N&Y&N\\ C_\text{even}\:\overline{S_\text{even}}&N&N&Y \end{array}\end{smallmatrix}$$

In this case, there is no need to worry about "divisibility by 3" of the difference. Instead, it's sufficient to compare the two sums for "equal," as shown in the above table.

This should be very easy to implement:

simulate this circuit – Schematic created using CircuitLab

The half-adders are easily recognized above. In addition, their associated outputs are directly compared using a pair of XORs. The results of these two comparisons are then considered using a NOR for the final output.

• Just to remove a possible confusion one might have - this solution is equivalent to the one that is derived using the straightforward approach through truth table and Boolean algebra. It can be derived from the same truth table and formula by performing certain transformation to get the XOR and NOR operations. Commented Dec 18, 2018 at 21:41
• Good expansion of my idea. I'm glad to see this resulted in a much more efficient answer than the brute force methods. Commented Dec 18, 2018 at 22:05
• @bxk21 As I said in my previous comment - it is not more efficient. It is the same. Commented Dec 18, 2018 at 22:09
• @EugeneSh. This flows from a very powerful generalization towards an implementation that is easily understood in a specific case here. I think the "brute force" words used by bxk21 would be well understood by any mathematician. An infinite-input mux can be used to solve many problems. Of course. But it provides no insight about those problems. I think that's all that bxk21 meant. Your solution says nothing about understanding broader cases of this kind of problem. (Not that it needed to do so.)
– jonk
Commented Dec 18, 2018 at 22:21
• Don't know how I could have missed the pattern, but that's a really nice answer. Wondering if this is the way a modulo operation is implemented in an FPGA? Commented Dec 19, 2018 at 7:52

The other answers are just brute-forcing the answer by writing all the true cases. It will get much more complex the more bits you add (approximately doubles the amount of cases every bit).

Alternatively, you could think of it as a modulo cycle

0->1->2->0


The first bit, if true adds 1, therefore moves it right by 1

The second adds 2. (+2 / -1)

Continuing this, you have

|bit|num|mod|
| 1 | 1 |+1 |
| 2 | 2 |-1 |
| 3 | 4 |+1 |
| 4 | 8 |-1 |


So, you have the answer as

A-B+C-D=0


or

A+C=B+D


This solution is much easier to expand to an arbitrary amount of input bits.

• It's not my background, so I don't really know how to write my answer as a boolean expression. If anyone wants to edit it in, feel free. Commented Dec 18, 2018 at 17:32
• I don't see what you are proposing. Is it a sequential circuit? Commented Dec 18, 2018 at 17:33
• I guess it's not really a full answer right now. I'm just shortening the logic to a very simple check: A+C=B+D Commented Dec 18, 2018 at 17:36
• That's actually an interesting observation. Do you mind if I write another answer based on it? Update: actually I won't... it's more complicated than I though initially Commented Dec 18, 2018 at 17:50
• @bxk21 Great observation. It generalizes as follows: "If the number of even bits minus the number of odd bits is a multiple of three then the number is divisible by three."
– jonk
Commented Dec 18, 2018 at 20:25

Your function can be easily written as a sum of products notation:

$$F(A,B,C,D) = \Sigma(0,3,6,9,12,15)$$

Such a representation is trivially converted to a MUX implementation, which I assume you are allowed to use (as you mention using adders). Just connect all of the inputs corresponding to the listed numbers to logical 1, and the others to 0:

simulate this circuit – Schematic created using CircuitLab

I cannot come up with anything else but the boolean expression $$\bar{A}\bar{B}\bar{C}\bar{D} + AB\bar{C}\bar{D} + \bar{A}BC\bar{D} + \bar{A}\bar{B}CD + A\bar{B}\bar{C}D + ABCD$$

This implementation requires 12 AND, 6 NAND and 5 OR Gates. Don't think that's too complicated to build. The good thing is that it linearly scales with the input size as in case of modulo 3 you can compute it bytewise. So for a 8 Bit number you'd need twice the amount of gates altough your input range has been multiplied by 16.

• This misses two values: 0x0 and 0xC Commented Dec 18, 2018 at 17:03
• ... thanks for that! ... 0xC was there Commented Dec 18, 2018 at 17:10
• I like this overview because it is close to my initial results and that'd be the most coherent solution to give at this time in my training. How would you go about designing such though? I tried to draw that but I am not sure how to optimize the drawing, is there a good resource I could read from? Commented Dec 18, 2018 at 17:40
• @Humpawumpa should I have tagged you here Commented Dec 19, 2018 at 8:31
• To me, the implementation suggested by jonk seems to be way more practical than mine. But if you like to implement it that way it depends on the size of your logic gates. Assuming you have 2-input gates just combine them pairwise e.g. if you start from the left it would be A and B to a NAND and C and D to a NAND and the two outputs combined with an AND. Commented Dec 19, 2018 at 8:56

A 4 bit number divisible by 3 implementation is pretty simple. I found a direct way as shown in the image:

I used 2 XOR gates and 1 XNOR gate.

• Hi, you should try to explain where MSB (most significant bit) and LSB (least significant bit). If you put MSB and LSB at the uppermost and lowermost pins and vice-versa, your circuit won't work as it is going to output 1 for a "0101" input which is 5. That would be a false trigger. Commented Aug 21, 2022 at 13:01
• This circuit delivers high for 8 of the 16 possible input pattern but there are only 6 numbers divisible by 3. So there is no possible input assignment, that can solve the job.
– Jens
Commented Aug 22, 2022 at 3:37