問題タブ [integer-division]

2 の累乗でそれを行う方法を理解しているので、それは私の質問ではありません。

たとえば、整数除算の代わりにビット シフトを使用して数値の 5% を見つけたい場合、どのように計算すればよいでしょうか?

したがって、(x * 20 / 19) の代わりに (x * 100 >> 11) を実行できます。これは正しくありませんが、近いので、試行錯誤を重ねてこれにたどり着きました。使用する最も正確なシフトを決定するにはどうすればよいですか?

x86 または x86_64 アーキテクチャでの除算オーバーフロー エラーについていくつか質問があります。最近、整数オーバーフローについて読んでいます。通常、算術演算の結果が整数オーバーフローになると、FLAGS レジスタのキャリー ビットまたはオーバーフロー ビットがセットされます。しかし、どうやらこの記事によると、除算によるオーバーフローはオーバーフロー ビットを設定せず、0 で除算する場合と同様にハードウェア例外をトリガーします。

現在、除算による整数オーバーフローは、乗算よりもはるかにまれです。除算オーバーフローをトリガーする方法はわずかしかありません。1 つの方法は、次のようなことです。

この場合、符号付き整数の 2 の補数表現により、正の 32768 を符号付き 16 ビット整数で表すことができないため、除算演算がオーバーフローし、-32768 という誤った値が発生します。

いくつかの質問：

1) この記事の内容に反して、上記はハードウェア例外を引き起こしませんでした。Linux を実行している x86_64 マシンを使用しています。ゼロで除算すると、プログラムはFloating point exception. しかし、除算のオーバーフローを引き起こすと、プログラムは通常通り続行し、誤った商を黙って無視します。では、なぜこれがハードウェア例外を引き起こさないのでしょうか?

2) 他の算術オーバーフローとは対照的に、除算エラーがハードウェアによって非常に厳しく扱われるのはなぜですか? 乗算オーバーフロー (偶発的に発生する可能性がはるかに高い) がハードウェアによって暗黙のうちに無視されるのはなぜですか? 除算オーバーフローは致命的な割り込みをトリガーするはずです?

===========編集==============

わかりました、皆さん、回答ありがとうございます。基本的に、上記の 16 ビット整数除算は、商がまだレジスタ サイズよりも小さいため、ハードウェア障害を引き起こすべきではないという回答を受け取りました。私はこれを理解していません。この場合、商を格納するレジスタは 16 ビットです。これは符号付きの正の 32768 を格納するには小さすぎます。では、なぜハードウェア例外が発生しないのでしょうか?

よし、これを GCC インライン アセンブリで直接実行して、何が起こるか見てみましょう。

これは単に誤った値を出力します: -32768. 商 (AX) を格納するレジスタが小さすぎて商に収まらない場合でも、ハードウェア例外は発生しません。したがって、ここでハードウェア障害が発生しない理由がわかりません。

浮動小数点を使用せずに最も近い整数に丸める簡単なPythonの方法はありますか？次のことをしたいのですが、整数演算を使用します。

==============

@John：浮動小数点はプラットフォーム間で再現できません。コードが異なるプラットフォーム間でテストに合格するようにしたい場合は、浮動小数点を回避する必要があります（または、テストにハッキーなespilonを追加して、機能することを期待します）。上記は、ほとんど/すべてのプラットフォームで同じになるほど単純かもしれませんが、浮動小数点を完全に回避する方が簡単なので、その決定はしたくありません。それは「Pythonの精神ではない」のでしょうか。

コードのホット パスでいくつかの整数除算を実行する必要があります。プロファイリングとサイクル カウントによって、整数除算のコストがかかっていることを既に確認しています。部門をより安価なものに減らすためにできることがあるといいのですが。

このパスでは、2^n+1 (n は変数) で割ります。基本的に、この関数を最適化して除算演算子を削除したいと考えています。

2^n で除算する場合は、div を右シフト n に置き換えるだけです。定数で除算する場合、コンパイラの強度によってその特定の除算が削減され、おそらく乗算とシフトになります。

2^n+1 に適用される同様の最適化はありますか?

編集: a here は、任意の 64 ビット整数にすることができます。n は 10 から 25 までの数個の値しか取りません。確かに、各 n についていくつかの値を事前計算できますが、a についてはできません。

フロア除算とは、結果が0に向かってではなく、常に（-∞に向かって）フロアダウンされる場合です。

C / C ++でフロアまたはユークリッド整数除算を効率的に実装することは可能ですか？

（明らかな解決策は、配当の符号を確認することです）

リファレンス実装として、次のことを考慮してください。

64ビット整数型を必要としない実装（Cまたは擬似コード）に興味があります。

私は次のような概要を示す実装のスケッチを開始しました。

ただし、オーバーフローを回避し（（a / d1）*（b / d2）<= UINT32_MAX）、計算全体のエラーを最小限に抑えることができるd1とd2の値を選択するのは困難です。

何かご意見は？

iPhone アプリケーションでいくつかの数値を計算しようとしています。

この例では、o は 100 (ミリ秒) であると予想されますが、NSLog(@"%d", o) で表示されるように 0 に等しくなります。

これも 0 です。

これは 250,000 に等しく、左から右への単純な計算です。

ここで私の頭の上を飛んでいるのは何ですか？

ありがとう、
ニック

JavaScriptで、どのように取得しますか：

1. 与えられた整数が別の整数に入る回数全体？
2. 残り？

私はこの構造体を使用して128ビット整数を表します。

（高速の128ビット整数ライブラリを指定できない限り、変更することはできません）

ここで、を使用して、このような値を10進数で出力しprintfます。そのためにはおそらく10で除算する必要がありますが、除算はまだ実装されていません。

これどうやってするの？ソリューションが機能する限り、ソリューションは非常に効率的である必要はありません。

編集：私はあなたが思いついたすべての解決策が好きです。あなたは素晴らしいです。

C を学んでいて、Project Eulerの問題は楽しくて興味深い学習方法だと思っていました (数学についても考えさせられるので、1 石で 2 羽の鳥を殺すことになるでしょう) が、思わぬ障害にぶつかりました。

私は（私が思うに）数の最大の素因数を見つけるための（単純であれば）良いアルゴリズムを持っています。（私がテストした限り）動作しますが、PE の質問は最後の質問として 600851475143 を使用します。double などを使用しようとしましたが、モジュロ演算子と除算演算子の両方を見つけることができないようです。どんな助けでも大歓迎です。

添付のコードは、double (またはその他の型) で動作するようにする前のものです。