c++ - 2 進数が 13 で割り切れるかどうかを調べる

Question

ユーザーが最上位から最下位まで数字を入力した場合、2進数が13で割り切れるかどうかを確認する方法は?

ビット数は非常に大きくなる可能性があるため、10 進数に変換して割り切れるかどうかを確認しても意味がありません。

私は従来の方法でそれにアプローチしました。nuber のビット範囲は最大 10^5 であるため、10 進数に変換する際にオーバーフローが発生します。

これにアプローチする方法は？例：

110010000100100 13で割る

111111111111111 13で割り切れない

Answer 1

O(N) アルゴリズムは次のとおりです。

ビットを左から右にトラバースします。位置を追加するたびに、現在の値に 2 を掛けてから 0 または 1 を加算するのと同じです。これは、モジュロ 13 演算にも当てはまります。最後のビットに到達したら、最終値が 0 に等しいかどうかを確認します。0 である場合、元の数値は 13 で割り切れます。