Is it divisible by X?

[Racheee]

Hello,
How can I make a formula by logic gates (XOR, NAND,...)
to find out whether a n-bit binary number (kn.....k3k2k1k0)
is divisible by 3 or not?

For example if we have a 6-bit binary number:
input: 000111
output:0 (it is not divisible by 3)
------------------
input: 101010
output:1 (it is divisible by 3)

 

[nand_gates]

The formula to check for divisibility by 3 exists for decimal numbers. In decimal numbers if the mod 3 sum of
digit is 3 or 9 the number is divisible by 3. To find if a binary number is divisible by 3 or not you first need to
convert the number to its BCD equivalent and perform digit additions. This is general solution. If number of digits
are less you can just decode the number and OR all the decoded outputs corresponding to 3,6,9,12 and so on...
Hope this helps!

 

[FvM]

An algorithm is given here https://stackoverflow.com/questions/39385971/how-to-know-if-a-binary-number-divides-by-3

The logic can be generated by a synthesis tool, it's apparently a bit more complex than using a few basic logic gates.

The 6 bit test e.g. fully utilizes a 6-Bit LUT

result =DATAE & DATAF & ( !DATAA & (!DATAB & (!DATAC $ (!DATAD)) # DATAB & (!DATAD
#DATAC)) # DATAA & (!DATAB & (!DATAC # DATAD) # DATAB & (!DATAC $ (!DATAD))) ) # !DATAE & DATAF &
( !DATAA & (!DATAB & (!DATAD # DATAC) # DATAB & (!DATAC # DATAD)) # DATAA & (!DATAB & (!DATAC $
(!DATAD)) # DATAB & (!DATAD # DATAC)) ) # DATAE & !DATAF & ( !DATAA & (!DATAB & (!DATAC # DATAD)
# DATAB & (!DATAC $ (!DATAD))) # DATAA & (!DATAB & (!DATAD # DATAC) # DATAB & (!DATAC # DATAD)) )
# !DATAE & !DATAF & ( !DATAA & (!DATAB & (!DATAC $ (!DATAD)) # DATAB & (!DATAD # DATAC)) # DATAA
& (!DATAB & (!DATAC # DATAD) # DATAB & (!DATAC $ (!DATAD))) )



DATAA = num[3]~input:O
DATAB = num[2]~input:O
DATAC = num[4]~input:O
DATAD = num[5]~input:O
DATAE = num[1]~input:O
DATAF = num[0]~input:O

 

[betwixt]

Any number that is 3 or greater is divisible by 3. A simple comparator or logic array can do that.
Do you mean divisible by 3 with no remainder '( n % 3) = 0' ?

Brian.

 

[Racheee]

Any number that is 3 or greater is divisible by 3. A simple comparator or logic array can do that.
Do you mean divisible by 3 with no remainder '( n % 3) = 0' ?

Brian.

Yes, exactly.
(Binary_number) mod 3 == 0