剰余を得るためのビットシフト

Question

ビットシフト演算子またはビット演算子のみを使用して、整数を別の整数（正の両方）で除算して剰余を得る方法を知りたい。 /オペレータまたは%オペレータは使用しないでください。

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

m = Remainder

n = The number

d = The divisor

m = n & (d - 1)

dフォーム2^kである場合にのみ、しかし、この方法は機能します。私は2の非力のための同様の方法を知りたい。あなたは絶対に使用できない場合、私は現在、programming challengesから問題に取り組んで、オペレータ%を使用していない任意の答えはあまり効率的な答えになるプログラムの実行時間

Answer 1

を減らすために、このような方法を採用したいのですが、いオペレータ、そして、一つの解はnから繰り返しDを減算するループを使用することです：

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のテストを監視しているものとします。