Binary divisibility
is there any ways to check binary divisibility without using modulo like (p%5==0) but rather using decrease and conquer algorithm.
i already now that to check whether a binary number is divisible by 5 for example we have to take the number of even bits minus the number of odd bits and if it is a multiple of 3 (e.g. -3,0,3,6, etc) then the number is divisible by three.
But i can't think of a way to solve it with a decrease and conquer algorithm
through research it suggested to use bitwise shift but i don't know how it is related to this problem or how to use it.
i already now that to check whether a binary number is divisible by 5 for example we have to take the number of even bits minus the number of odd bits and if it is a multiple of 3 (e.g. -3,0,3,6, etc) then the number is divisible by three.
But i can't think of a way to solve it with a decrease and conquer algorithm
through research it suggested to use bitwise shift but i don't know how it is related to this problem or how to use it.
| i already now that to check whether a binary number is divisible by 5 for example we have to take the number of even bits minus the number of odd bits and if it is a multiple of 3 (e.g. -3,0,3,6, etc) then the number is divisible by three. |
Huh?
You check to see whether a number is divisible by 5 and find out whether it is divisible by 3?
5 = 0x101. odd bits: 2. even bits: 1. even - odd = -1.
6 = 0x110. odd bits: 2, even bits: 1. even - odd = -1.
Both of these numbers have the same difference. One is divisible by 5 and the other is divisible by 3. Padding the numbers out to additional higher order 0-bits will make no difference.
In base 10 there are certain tricks for determining whether numbers are multiples of 3 or 9 repeatedly summing the digits of the number. These tricks are based on number theory, but the tricks cannot be used for all targets. The trick you "know" about divisibility by 5 or 3, if it does exist, is not necessarily applicable to all numbers.
Are you trying to solve this for a general case, e.g. m % n for any positive integers, but only using bitwise operations? Are you allowed to use / (division) [idiv in x86]? Just as there isn't a general rule for this in base-10, there isn't a general rule in binary as well. You just have to do the division/remainder algorithm.
Last edited on
yes i am allowed to use division but not modulo, as i have mentionned earlier it has to be in a form of decrease and conquer algortihm. takes an integer or hexadecimal as input convert it into binary and check if it is divisible by 3, 5 , or 15.
Topic archived. No new replies allowed.