2

ビット単位の除算に関する多くの投稿を見つけました。ほとんどのビット単位の使用法を完全に理解していますが、特定の除算は考えられません。与えられた数 (100 としましょう) を可能な限り 2 の倍数で割りたい (注意: 2 ビット倍数のべき乗で割りたくない!)
例: 100/2, 100/4, 100/ 6, 100/8, 100/10...100/100
またunsigned int、回答を使用すると、たとえば 100/52=0 のように丸められることもわかっていますが、これらの回答をスキップしたり、それらを印刷してください。問題ありません。私の関心事は、主に 6 や 10 など (2 の倍数) で割る方法です。あなたが私にくれたコードを Java から C に変換することができるので、C で行う必要があります。

4

3 に答える 3

2

3 による除算の質問に対する受け入れられた解に対して示された数学に従って、除算アルゴリズムの再帰を導き出すことができます。

(int)(X / Y)を計算するには

  • k を 2 k ≥ Y かつ 2 k-1 < Yと
    する (2 k = (1 << k))
  • d = 2 k - Yとする

  • 次に、A = (int)(X / 2 k ) および B = X % 2 kの場合、

    X = (1 << k) * A + B
  = (1 << k) * A - Y * A + Y * A + B
  = d * A + Y * A + B
  = Y * A + (d * A + B)

  • したがって、

    X/Y = A + (d * A + B)/Y

言い換えると、

ならS(X, Y) := X/Y、S(X, Y) := A + S(d * A + B, Y)。

この繰り返しは、単純なループで実装できます。ループの停止条件は、分子が 2 kを下回ったときです。この関数divuは、ビットごとの演算子のみを使用し、符号なしの型を使用して再帰を実装します。数学演算のヘルパー関数は実装されていませんが、それほど難しくはありません (リンクされた回答では、完全なadd実装が既に提供されています)。この関数は、入力rs()の符号拡張を行う「右シフト」用です。unsignedこの関数divは の実際の API であり、に委譲する前にintゼロ除算と負数をチェックします。2 の補数の否定を行います。ydivunegate

static unsigned divu (unsigned x, unsigned y) {
    unsigned k = 0;
    unsigned pow2 = 0;
    unsigned mask = 0;
    unsigned diff = 0;
    unsigned sum = 0;
    while ((1 << k) < y) k = add(k, 1);
    pow2 = (1 << k);
    mask = sub(pow2, 1);
    diff = sub(pow2, y);
    while (x >= pow2) {
        sum = add(sum, rs(x, k));
        x = add(mul(diff, rs(x, k)), (x & mask));
    }
    if (x >= y) sum = add(sum, 1);
    return sum;
}

int div (int x, int y) {
    assert(y);
    if (y > 0) return divu(x, y);
    return negate(divu(x, negate(y)));
}

signed intこの実装は、 2 の補数の使用に依存します。移植性を最大限に高めるために、divを呼び出す前に、負の引数を 2 の補数に変換する必要がありdivuます。次に、結果をdivu2 の補数から元の符号付き表現に変換する必要があります。

于 2013-06-17T07:58:04.063 に答える
-1

/できる限り整数除算の演算子を使用してください。

たとえば、100 を 6 または 10 で割りたい場合は、100/6orと書く必要があり100/10ます。ビット単位の除算について言及する場合、(1) 演算子の実装を意味します/か、それとも (2) 2 のべき乗による除算を指しますか。

(1) の場合、プロセッサには整数除算ユニットが必要です。そうでない場合、コンパイラは適切な実装を提供する必要があります。

100>>2(2)の代わりに使用できます100/4。コンパイル時に分子がわかっている場合、優れたコンパイラは自動的にシフト命令を使用する必要があります。

于 2013-06-16T23:27:43.973 に答える