Двоичная делимость на 10

Сначала разделите число на нечетные и четные биты (я называю «четными» биты, соответствующие четным степеням числа 2):

100100110010110000000101101110 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 четный 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 нечетный

Теперь в каждом из них поочередно складываем и вычитаем цифры, как в стандартном тесте на делимость на 11 в десятичной дроби (начиная со сложения справа):

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

Теперь удвойте сумму нечетных цифр и прибавьте ее к сумме четных цифр:

2*1 + -2 = 0

Если результат делится на 5, как в этом случае, само число делится на 5.

Поскольку это число также делится на 2 (самая правая цифра — 0), оно делится и на 10.

http://mathforum.org/library/drmath/view/55908.html

Если вы говорите о вычислительных методах, вы можете выполнить тест на делимость на 5 и тест на делимость на 2.
Приведенные ниже числа предполагают беззнаковую 32-битную арифметику, но могут быть легко расширены до больших чисел.

Сначала я приведу код, а затем более текстовое объяснение:

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 )

Делимость на 2 проста: (n&1) == 0 означает, что n четно.

Делимость на 5 предполагает умножение на число, обратное 5, которое равно 0xcccccccd (потому что 0xcccccccd * 5 == 0x400000001, что равно 0x1, если вы усекаете до 32 бит).
При умножении n*5 на обратное 5, вы получите n * 5*(обратное 5), что в 32-битной математике упрощается до n*1 .

Теперь предположим, что n и q — 32-битные числа, и q = n*(обратно 5) по модулю 2³²< /em>.
Поскольку n не больше 0xffffffff, мы знаем, что n/5 не больше, чем (2^32-1)/5 (0x33333333). Следовательно, мы знаем, что если q меньше или равно (2³²-1)/5, то мы знаем n< /em> делит точно на 5, потому что q * 5 не усекается до 32 бит и поэтому равно n, поэтому n делит q и 5.