除算を行わずに剰余を求めたい

質問

http://www.tensyo.com/urame/date/dayTips.htm#MOD
によると、除算を行わずに剰余を求める方法として、

-------------------------------------------------------
2^N>=b となるNを求める(2^N == 1<<N)
B=2^N-b
C=2^N-1
while(a>=2*b){ B *(a>>N) + a&C };
最後に１回 if(a>=b)a-=b ; と計算する
-------------------------------------------------------

とありますが、これの実装はおそらく誤植です。
というのも、4行目B *(a>>N) + a&Cは代入操作等をしていないため、
実質何もしていないからです。

そこで、a=B *(a>>N) + a&Cのように変更するなどやってみましたが、
5回に1回ぐらい異なる値が現れます。

このアルゴリズムはどのように変更したらよいでしょうか？
また、他の方法でも結構ですので、教えてください。

回答No.2

f272 · ベストアンサー

a=B *(a>>N) + a&C;
じゃなくて
a=B *(a>>N) + (a&C);
だろう。

お礼

なるほど、ありがとうございます。
明日試してみます。

回答No.1

oooioi

言語は何だ?
%演算子を使うのはダメなのか?

お礼

回答ありがとうございます。
言語はC++を想定してますが、
%を明示的には使わず（計算の途中で使うのはOK）に
結果を出力したいです。