Given a binary number a, how would you find if they are divisible by other numbers?
Divisibility by 2:
a & (a-1) = 0
Divisibility by 3:
Starting from MSB or LSB, add the first digit, subtract 2nd digit, add the 3rd, subtract the 4th...so on. If result = 0, then its divisible by 3.
+ - + - + - .... = 0
Divisibility by 4:
a & 3 = 0
Divisibility by 2^x:
a & (2^x - 1) = 0
Divisibility by 2:
a & (a-1) = 0
Divisibility by 3:
Starting from MSB or LSB, add the first digit, subtract 2nd digit, add the 3rd, subtract the 4th...so on. If result = 0, then its divisible by 3.
+ - + - + - .... = 0
Divisibility by 4:
a & 3 = 0
Divisibility by 2^x:
a & (2^x - 1) = 0
No comments:
Post a Comment