1

How to check if a binary number can be divided by 10 (decimal), without converting it to other system. For example, we have a number:

1010 1011 0100 0001 0000 0100

How we can check that this number is divisible by 10?

7
  • 4
    Do you mean 10 decimal or 10 binary?
    – Eric J.
    Sep 10, 2012 at 17:14
  • Every number (exuding 0) is divisible by 10
    – asawyer
    Sep 10, 2012 at 17:15
  • 10 decimal. I forgot to mention it in the post. Edit: post edited. Sep 10, 2012 at 17:16
  • 1
    @EricJ. What I was trying to get at was that the question was ambiguously worded.
    – asawyer
    Sep 10, 2012 at 17:22
  • 3
    @asawyer actually, the strict mathmatical definition of x being divisable by y means there exists some integer m such that ym = x that is it is divided without remainder -- so it was not at all ambiguous. I can understand how it can be confusing since we perform division on non-divisable numbers all the time, i.e. we get a result with a remiander/ a decimal -- which make no sense if you are careful with the definition of the word divisable.
    – gbtimmon
    Sep 10, 2012 at 17:28

3 Answers 3

3

First split the number into odd and even bits (I'm calling "even" the bits corresponding to even powers of 2):

100100110010110000000101101110 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 even 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 odd

Now in each of these, add and subtract the digits alternately, as in the standard test for divisibility by 11 in decimal (starting with addition at the right):

100100110010110000000101101110 +0-1+0-1+0-0+1-0+0-0+1-1+0-1+0 = -2 +1-0+0-1+0-1+1-0+0-0+0-0+1-1+1 = 1

Now double the sum of the odd digits and add it to the sum of the even digits:

2*1 + -2 = 0

If the result is divisible by 5, as in this case, the number itself is divisible by 5.

Since this number is also divisible by 2 (the rightmost digit being 0), it is divisible by 10.

Link

1
  • I found this; I thought that somebody has found an easier solution, that's why I created this question. Anyway, thanks ;) Sep 10, 2012 at 17:23
2

If you are talking about computational methods, you can do a divisiblity-by-5 test and a divisibility-by-2 test.
The numbers below assume unsigned 32-bit arithmetic, but can easily be extended to larger numbers.

I'll provide some code first, followed by a more textual explanation:

unsigned int div5exact(unsigned int n)
{
    // returns n/5 as long as n actually divides 5
    // (because 'n * (INV5 * 5)' == 'n * 1' mod 2^32

    #define INV5 0xcccccccd

    return n * INV5;

}

unsigned int divides5(unsigned int n)
{
    unsigned int q = div5exact(n);
    if (q <= 0x33333333) /* q*5 < 2^32? */
    {
        /* q*5 doesn't overflow, so n == q*5 */
        return 1;
    }
    else
    {
        /* q*5 overflows, so n != q*5 */
        return 0;
    }
}

int divides2(unsigned int n)
{
    /* easy divisibility by 2 test */
    return (n & 1) == 0;
}

int divides10(unsigned int n)
{
    return divides2(n) && divides5(n);
}


/* fast one-liner: */
#define DIVIDES10(n) ( ((n) & 1) == 0 && ((n) * 0xcccccccd) <= 0x33333333 )

Divisibility by 2 is easy: (n&1) == 0 means that n is even.

Divisibility by 5 involves multiplying by the inverse of 5, which is 0xcccccccd (because 0xcccccccd * 5 == 0x400000001, which is just 0x1 if you truncate to 32 bits).
When you multiply n*5 by the inverse of 5, you get n * 5*(inverse of 5), which in 32-bit math simplifies to n*1 .

Now let's say n and q are 32-bit numbers, and q = n*(inverse of 5) mod 232.
Because n is no greater than 0xffffffff, we know that n/5 is no greater than (232-1)/5 (which is 0x33333333). Therefore, we know if q is less than or equal to (232-1)/5, then we know n divides exactly by 5, because q * 5 doesn't get truncated in 32 bits, and is therefore equal to n, so n divides q and 5.

If q is greater than (232-1)/5, then we know it doesn't divide 5, because there is a one-one mapping between the 32-bit numbers divisible by 5 and the numbers between 0 and (232-1)/5, and so any number out of this range doesn't map to a number that's divisible by 5.

0

Here is the code in python to check the divisibilty by 10 using bitwise technique

#taking input in string which is a binary number eg: 1010,1110
s = input()
#taking initial value of x as o
x = 0
for i in s:
    if i == '1':
        x = (x*2 + 1) % 10
    else:
        x = x*2 % 10
#if x is turn to be 0 then it is divisible by 10
if x:
print("Not divisible by 10")
else:
print("Divisible by 10")

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.