2 の累乗でそれを行う方法を理解しているので、それは私の質問ではありません。
たとえば、整数除算の代わりにビット シフトを使用して数値の 5% を見つけたい場合、どのように計算すればよいでしょうか?
したがって、(x * 20 / 19) の代わりに (x * 100 >> 11) を実行できます。これは正しくありませんが、近いので、試行錯誤を重ねてこれにたどり着きました。使用する最も正確なシフトを決定するにはどうすればよいですか?
20739 次
7 に答える
22
最善の方法は、コンパイラに任せることです。あなたは単に書く
a/b
選択した言語で、コンパイラはビットいじりを生成します。
編集（気にしないでください。回答に補強を追加しています：
#include <stdio.h>
int main(int argc, char **argv) {
printf("%d\n", argc/4);
}
明らかに、最も速いのは ですargc>>2。しばらく様子を見てみましょう：
.file "so3.c"
.section .rodata
.LC0:
.string "%d\n"
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
andl $-16, %esp
subl $16, %esp
movl 8(%ebp), %eax
movl %eax, %edx
sarl $31, %edx
shrl $30, %edx
leal (%edx,%eax), %eax
sarl $2, %eax
movl %eax, %edx
movl $.LC0, %eax
movl %edx, 4(%esp)
movl %eax, (%esp)
call printf
leave
ret
.size main, .-main
.ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
.section .note.GNU-stack,"",@progbits
はい、そこです。sarl $2, %eax
EDIT 2（重ねて申し訳ありません20/19が、もう少し複雑です…）
私はちょうど代入argc*20/19しargc/4、これが出てくる数学です：
0000000100000f07 shll $0x02,%edi
0000000100000f0a movl $0x6bca1af3,%edx
0000000100000f0f movl %edi,%eax
0000000100000f11 imull %edx
0000000100000f13 sarl $0x03,%edx
0000000100000f16 sarl $0x1f,%edi
0000000100000f19 subl %edi,%edx
したがって、プロセスは
- 入力を 4 倍する (sll)
- (movl 0x...) をロードし、固定小数点小数を (imull) 乗算して 64 ビットの結果を取得します (これは 32 ビット コードです)。
- 結果の上位 32 ビットを 8 (sarl) で割ります。これが負の数をどのように処理するかに注意してください。
- 結果の下位 32 ビットを INT_MAX (sarl) で割り、0 または -1 を取得します。
- 必要に応じて 1 を加算 (-1 を減算) して、上位の結果を正しく丸めます。
于 2010-10-03T17:11:24.643 に答える
8
あなたがやろうとしていることは、結果として得られるプロセスを最適化しないため、意味がありません!!!
ねえ、私はあなたの質問のどこにも、あなたが最適化する意図があることを読んでいませんでした.
電工人は「役に立つ」とはいえ好奇心旺盛。私たちは、屋根裏部屋、地下室、寝室、リビングルームに、いつか役に立つと信じているがらくたを積み上げている、ニュースで読んだアイテムの強迫的な強迫的な買いだめのようなものです。少なくとも、私が 30 年弱前に Engg スクールに通っていたときはそうでした。あなたの人生やライフスタイルを最適化する可能性がほとんどないように見える「役に立たない」知識をため込むための探求を続けることをお勧めします. 手作業でコーディングされたアルゴリズムで実行できるのに、なぜコンパイラに依存するのですか?! ええ？少し冒険してくださいね。あなたの知識の追求に軽蔑を表明する人々を否定することはありません。
中学校で部活のやり方を覚えていますか? 437/24、例えば
_____
24|437
018
-----
24|437
24
-----
197
24
-----
5
割り算の対象となる数 437 は、被除数と呼ばれます。24 は除数、結果の 18 は商、5 は剰余です。税金を申告するときと同様に、株式の「配当」から得た利益を申告する必要がありますが、これは誤解です。納税フォームに記入するのは、配当の 1 つの巨大なチャンクの商の倍数です。配当を受け取ったのではなく、配当の一部を受け取りました。それ以外の場合は、株式の 100% を所有していたことになります。
___________
11000|110110101
000010010
-----------
11000|110110101
11000
----------
000110101 remainder=subtract divisor from dividend
11000000 shift divisor right and append 0 to quotient until
1100000 divisor is not greater than remainder.
110000 Yihaa!
----------
000101 remainder=subtract shifted divisor from remainder
11000 shift divisor right and append 0 to quotient until
1100 divisor is not greater than remainder.
----------
oops, cannot shift anymore.
上記は、すでにご存知かもしれませんが、真の除算です。これは、シフトされた除数を減算することによって達成されます。
あなたが望むのは、被除数をシフトするだけで同じことを達成することです。残念ながら、除数が 2 の指数乗 (2,4,8,16) でない限り、これを行うことはできません。これは、バイナリ算術の明らかな事実です。または、少なくとも、近似および内挿手法なしでそれを実行できる方法を知りません。
したがって、被除数シフトと真の除算を組み合わせて使用する必要があります。例えば
24 = 2 x 2 x 2 x 3
まず、バイナリ シフトを使用して 437 を 8 で除算して 010010 を取得し、次に真の除算を使用して 3 で除算します。
010010
--------
11|110110
11
-------
011
11
-----
0
これは 010010 = 18 になります。
出来上がり。
24 = 2^8 x 3 をどのように決定しますか?
1 になるまで 11000 を右にシフトします。
つまり、除数が 1 になるまで、除数をシフトするのと同じ回数、被除数をシフトできます。
したがって、明らかに、除数が奇数の場合、この方法は機能しません。たとえば、除数 25 では機能しませんが、除数 50 では少し機能します。
おそらく、13 のような除数を 2^3=8 と 2^4=16 の間に補間できる予測方法があります。もしあれば、私はそれらに精通していません。
調べる必要があるのは、数列を使用することです。たとえば、25 で割ると次のようになります。
1 1 1 1 1
__ = __ - ___ - ___ + ___ - ... until the precision you require.
25 16 64 128 256
級数の一般形は
1 1 b1 bn
_ = ___ + _______ + ... + ______
D 2^k 2^(k+1) 2^(k+n)
ここで、bn は -1、0、または +1 のいずれかです。
上記のバイナリ操作にエラーやタイプミスがないことを願っています。もしそうなら、何千もの謝罪。
于 2010-10-03T21:08:40.983 に答える
7
式があるとしますa = b / c。hroptatyr が述べたように、乗算は非常に高速です (そして除算よりもはるかに高速です)。したがって、基本的な考え方は、除算を : のような乗算に変換することですa = b * (1/c)。
ここで、 reciprical の計算にはまだ除算が必要な1/cので、これはcがアプリオリにわかっている場合にのみ機能します。浮動小数点の計算ではそれで十分ですが、整数では別のトリックを使用する必要がありcます。の値に関心があるため、最終結果を で割る必要があります。2 の累乗を選択した場合、最終分割は高速になります。some_big_number / ca2 = b * (some_big_number / c)some_big_number * b/cb/csome_big_number
元：
// we'll compute 1/20 of the input
unsigned divide_by_20(unsigned n){
unsigned reciprocal = (0x10000 + 20 - 1) / 20; //computed at compile time, but you can precompute it manually, just to be sure
return (n * reciprocal) >> 16;
}
編集: この方法の良い点は、修正を選択することで、除算の丸め方法を選択できることです (この場合は20 - 1、ゼロに丸めるためのものでした)。
于 2010-10-03T19:39:33.220 に答える
6
その背後にある数学に興味がある場合は、Henry S. Warren によるHacker's Delightを読んでください。
最適化されたコードに興味がある場合は、人間が最も読みやすいコードを記述してください。例えば：
int five_percent(int x) {
return x / 20;
}
を使用してこの関数をコンパイルするg++ -O2と、実際の除算は行われず、代わりに魔法の乗算、ビットシフト、および修正が行われます。
于 2010-10-03T22:09:48.580 に答える
3
すべてをシフトで行うことはできません。代わりに「魔法の」除数を使用する必要があります (ハッカーの喜びを参照)。魔法の除算は、ある数値に適切な大きさの別の数値を掛けて、除算の答えが得られるようにロールオーバーすることによって機能します (mul/imul は div/idiv よりも高速です)。魔法の定数は素数ごとにのみ一意であり、倍数にはシフトが必要です。たとえば、3 による符号なし除算は (32 ビットで) として表すことができx * 0xAAAAAAABます(x * 0xAAAAAAAB) >> 1。等比級数3 * (2 ^ x)、ここで 0 <= x < 32)
于 2010-10-03T20:22:38.050 に答える
2
yを掛けてnをシフトすることにより、xの5％を概算するとします。5％は1/20であり、a >> n = a / 2 nなので、解く必要があります
x/20≈x*y/ 2 n （記号「≈」は「ほぼ等しい」を意味します）
これは単純化して
y≈2n / 20
したがって、n = 11の場合、
y≈2n /20 = 2048/20 = 102 + 8/20
したがって、y = 102を設定できます。これは、試行錯誤で見つけた100よりも実際に優れています。
一般に、nで遊んで、より良い答えが得られるかどうかを確認できます。
私はこれを分数1/20で解決しましたが、同じ方法に従うことで、任意の分数p/qでこれを解決できるはずです。
于 2010-10-03T19:28:16.733 に答える
0
まあ一般的に：
- 数値の素因数分解を取得するには、N を 2^k * 残りに分解します。次に、2 乗でビット シフトを使用できます。例: 20 = 2^2 * 5 なので、20 を掛けるには、5 を掛けてからビット シフトを使用します。
<< 2 - 2 乗以外でビット シフトを使用するには、奇数について次のことを確認し
lます。a * l = a * (l - 1) + al - 1
除算も同様に構築できます。
于 2010-10-03T17:05:50.773 に答える