Is it divisible by X?

Status
Not open for further replies.
R

Racheee

Newbie
Joined
Nov 24, 2021
Messages
4
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Activity points
46
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)
 

Sort by date Sort by votes
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!
 

Upvote 0 Downvote
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
Code: 
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
 

Upvote 0 Downvote
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.
 

Upvote 0 Downvote
betwixt said:
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.
Click to expand...
Yes, exactly.
(Binary_number) mod 3 == 0
 

Upvote 0 Downvote
Status
Not open for further replies.

Similar threads

Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…