13

ビットシフトまたはビットごとの演算子のみを使用して、整数を別の整数 (両方とも正) で割って剰余を取得する方法を知りたいです。/operator またはoperatorは%使用しないでください。

たとえば、除数が次の形式の剰余を取得するには2^k、次の操作で剰余が得られます。

m = Remainder

n = The number

d = The divisor

m = n & ( d - 1 )

ただし、このメソッドdは が の形式の場合にのみ機能し2^kます。の累乗以外の同様の方法を知りたいです2。私は現在問題に取り組んでおり、programming challengesプログラムの実行時間を短縮するためにそのような方法を採用したいと考えています

4

1 に答える 1

1

演算子を使用しない回答は%効率の悪い回答になりますが、演算子を絶対に使用できない場合は、ループを使用して n から d を繰り返し減算することが 1 つの解決策です。

m = n;
while (m >= d)
{
  m -= d;
}

整数が 32 ビットであると仮定すると、n から d の倍数を削除する最適化されたバージョンを検討できます。

m = n;
for (i = 31; i >= 0; i--)
{
  di = d << i;
  if (di > 0 && m >= di) m -= di;
}

この例では、整数が符号付きで、オーバーフロー、つまり のテストを監視していると想定していますdi > 0。

于 2012-11-25T23:08:29.360 に答える