0

特定の n ビットの 2 進数に対してこれを実装するアルゴリズムを考えようとしています。多くの例を試しましたが、パターンを見つけることができません。では、どうすればよいのでしょうか？

4

5 に答える 5

2

これはどう：

数値を基数 4 に変換します (これはビットのペアを組み合わせるだけで簡単です)。基数 4 の 5 は 11 です。基数 4 で 11 で割り切れる値は、11、22、33、110、121、132、203 など、おなじみの値です。

11 で割り切れる規則は、すべての奇数桁とすべての偶数桁を足し、一方を他方から引くことです。結果が 11 で割り切れる場合 (覚えているのは 5 です)、結果は 11 で割り切れます (覚えているのは 5 です)。

例えば：

123456d = 1 1110 0010 0100 0000b = 132021000_4

The even digits are 1 2 2 0 0 : sum = 5d
The odd digits are   3 0 1 0  : sum = 4d

Difference is 1, which is not divisble by 5

または別のもの：

123455d = 1 1110 0010 0011 1111b = 132020333_4

The even digits are 1 2 2 3 3 : sum = 11d
The odd digits are   3 0 0 3  : sum = 6d

Difference is 5, which is a 5 or a 0

これは、ほとんどがビットスライスであり、その後に N/2 加算器が続くため、かなり効率的な HW 実装が必要です。ここで、N は関心のある数値のビット数です。

数字を足して引いた後、最大値は 3/4 * N であることに注意してください。したがって、最大 16 ビットの数値がある場合、結果として最大 12 を取得できるため、0、±5 のみを確認する必要があります。明示的に±10。32 ビットの数値を使用している場合、結果として最大 24 を取得できるため、結果が ±15 か ±20 かどうかも確認する必要があります。

于 2013-08-27T20:07:38.533 に答える
1

5 で割り切れる各ビットの寄与は、4 ビット パターン 3421 です。任意の 2 進数を一度に 4 ビットずつシフトし、正のビットに対応する値を追加できます。

例：

100011

テイク 0011 パターン 0021 サム 3 を適用

次の 4 ビット 0010 パターン 0020 を適用 合計 = 5

于 2014-08-20T21:16:13.603 に答える
1

まあ、私はちょうど考え出した... number mod 5 = a0 * 2^0 mod 5 + a1 * 2^1 mod 5 +a2* 2^2 mod 5 + a3 * 2^3 mod 5 + a4 * 2^4 mod 5 + .... = a0 (1) + a1(2) +a2 (-1) +a3 (-2) +a4 (1) 繰り返し ...

したがって、奇数桁の差 + 偶数桁の差の 2 倍 = 5 で割り切れる

たとえば ... 110010
奇数桁の差 = 0-0+1 = 1 または 01 偶数桁の差 = 1-0+1 = 2 または 10

奇数桁の差 + 偶数桁の差の 2 倍 = 01 + 2*(10)=01 + 100 = 101 は 5 で割り切れます。

于 2013-08-30T11:39:51.410 に答える
0

これが答えであったであろう割り当ては、1年後には大幅に遅れるはずです
.5で割り切れる自然数のバイナリ表現では、ビット4nと4n+2のパリティは等しく、ビット4n+1のパリティも等しくなります。と 4n+3 です。
(これは、JoshG79、notsogeek、または james の回答と完全に同等です: 4≡-1(mod 5), 3≡-2(mod 5) (引数の再帰についての手を振ることが減少し、キャリーの不要な処理はありません)回路内))

于 2014-08-21T05:36:01.240 に答える