binary - 10 で割り切れる 2 進数

Question

2 進数を他のシステムに変換せずに 10 (10 進数) で割り切れるかどうかを調べる方法。たとえば、次のような数値があります。

1010 1011 0100 0001 0000 0100

この数が 10 で割り切れることをどのように確認できますか?

Answer 1

まず、数値を奇数ビットと偶数ビットに分割します (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 奇数

次に、これらのそれぞれで、10 進数で 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 倍にして、偶数桁の合計に追加します。

2*1 + -2 = 0

この場合のように、結果が 5 で割り切れる場合、数値自体は 5 で割り切れます。

この数は2でも割り切れる(右端が0)ので、10でも割り切れる。

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

Answer 2

計算方法について話している場合は、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であるため、32 ビットに切り捨てると 0x1 になります)。n*5に 5の逆数
を掛けると、 n * 5*(5 の逆数)が得られます。これは、32 ビット演算ではn*1に単純化されます。

ここで、 nとqが 32 ビットの数値で、q = n*(5 の逆数) mod 2 ³²であるとします。nは 0xffffffff 以下である
ため、 n/5は(2 ³² -1)/5 (0x33333333) 以下であることがわかります。したがって、 qが(2 ³² -1)/5以下であるかどうかがわかれば、 q * 5は 32 ビットで切り捨てられないため、 nは正確に 5 で除算されることがわかり、したがってnに等しくなります。したがって、nはqと 5 を割ります。

qが(2 ³² -1)/5より大きい場合、5 で割り切れる 32 ビットの数値と 0 ～(2 ³² -1)/5であるため、この範囲外の数値は 5 で割り切れる数値にはマップされません。