[フレーム]
はてなブックマークアプリ

サクサク読めて、
アプリ限定の機能も多数!

アプリで開く

気に入った記事をブックマーク

  • 気に入った記事を保存できます
    保存した記事の一覧は、はてなブックマークで確認・編集ができます
  • 記事を読んだ感想やメモを書き残せます
  • 非公開でブックマークすることもできます
適切な情報に変更

エントリーの編集

loading...

エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。

タイトルガイドライン

このページのオーナーなので以下のアクションを実行できます

タイトル、本文などの情報を
再取得することができます
コメントを非表示にできます コメント表示の設定

ブックマークしました

ここにツイート内容が記載されます https://b.hatena.ne.jp/URLはspanで囲んでください

Twitterで共有

ONにすると、次回以降このダイアログを飛ばしてTwitterに遷移します

406users がブックマーク コメント 49

ガイドラインをご確認の上、良識あるコメントにご協力ください

0 / 0
入力したタグを追加

現在プライベートモードです 設定を変更する

おすすめタグタグについて

よく使うタグ

2で割ることと3で割ること - Qiita

406 users qiita.com/saka1_p

ガイドラインをご確認の上、良識あるコメントにご協力ください

0 / 0
入力したタグを追加

現在プライベートモードです 設定を変更する

おすすめタグタグについて

よく使うタグ

はてなブックマーク

はてなブックマークで
関心をシェアしよう

みんなの興味と感想が集まることで
新しい発見や、深堀りがもっと楽しく

ユーザー登録

アカウントをお持ちの方はログインページへ

記事へのコメント49件

  • 注目コメント
  • 新着コメント
mozukuyummy
大昔にマイコンで16bitのitoaを自作した時は、10の累乗で割るよりも、「これ以上引けなくなるまで10000を引く」「これ以上引けなくなるまで1000を引く」...をベタベタに書く方が早かったなあ。

その他
yife
"じゃあ除算はというと...なんと最大 97クロックかかります。メモリアクセスの方が速くなりかねないぐらいの遅さです。" 3で割るっていうシンプルな題材と、現実の泥臭い実装の差が面白かった

その他
magicalboy
画像処理は2^n - 1の定数で割る処理が結構あるのでこういう乗算+シフトをよく使っていた。

その他
theatrical
3のマジックナンバーなんて、なんでこんなの思いつけるんだよ。と言う感じがあるけど、理屈を聞けば意味がわかるし、ちゃんと知識と考え続ける能力があればたどり着けるものだと考えると、やる気がでる

その他
mominis
これを考えつく発想力がやばい

その他
kamocyc
" 『ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか』に載っている内容です。" そのうち読みたい

その他
h3poteto
2で割るのをビットシフトにするのは知ってたけど,3はすごいな

その他
terazzo
この記事は誤差の正当性の証明が核だな。/宴会の割り勘で14人で割るときに総額を7倍するとかしてた(誤差はまあ愛嬌)。5人なら2倍して10で割る(こっちは誤差なし)。

その他
greenbow
なるほど面白い。 "発想は「もう3で割られている」大きな整数Mを作ることです。"

その他
wrss
3は知らなかった!!

その他
efcl
除算命令は遅いため、乗算で表現する話。 2の倍数と3の倍数。

その他
tasshi820
"割る対象の数にMMMをかけ、かけた値に右ビットシフトをして???の部分を除去すると、割る3部分だけが残るはずだ、というのが方針です。"

その他
mrkn
32ビット整数除算を64ビット固定小数点乗算に置き換える話

その他
zyzy
ひえー、こんな事してたのか。2の倍数と3の倍数がハックできれば、かなりの計算が楽できるよな。

その他
manaten
なるほどなと思いつつ、乗算部分でオーバーフローしても期待通りに動くんだろうかとおそらく初歩的なところで躓いている自分

その他
knok
こういう最適化の積み重ねがコンパイラ技術には投入されてるのがすごい。歴史もあるけど

その他
honma200
おー、なるほど。あとは7ができれば良い感じ?(素数全般そうなっちゃうけど・・・)

その他
kamei_rio
四則演算として同列に並べるには、割り算って難しすぎるよね。やはり逆元がある体は偉大

その他
Nyoho
3で割るところの謎の整数1431655766は、読みながらmod 2^32での3の逆数をかけているのかなあと予想したけど、その2倍だった。

その他
yarumato
"除算は圧倒的に遅い。x86 CPUだと、加算・シフト演算は1クロック。乗算は4クロック。除算は最大97クロック。だからコンパイラは除算命令の生成を極力避け、定数2で割る場合シフト使い、定数3で割る場合も乗算でやる"

その他
maghrib
"ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか"

その他
richard_raw
なるほど、3の場合はこうなるのか。

その他
h3poteto
h3poteto 2で割るのをビットシフトにするのは知ってたけど,3はすごいな

2020年12月09日 リンク

その他
sytkm
前どこかで読んだ気がしたけど多分参考資料にあるやつだと思う。やっぱり面白い。

その他
fukurou112
逃げ出さないこと信じ抜くこと

その他
Guro
いままで知らずにプログラマやってたわ。。

その他
cu39
地道な積み重ねの跡が見えて面白い。

その他
natu3kan
2の補数とビットシフトで手早く割り算をする。10進法の1431655766は2進法で1010101010101010101010101010110で16進法で55555556。ウィキペによると1431655766/2の715827883はワグスタッフ素数で2^31+1/3。

その他
kamocyc
kamocyc " 『ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか』に載っている内容です。" そのうち読みたい

2020年12月09日 リンク

その他
theatrical
theatrical 3のマジックナンバーなんて、なんでこんなの思いつけるんだよ。と言う感じがあるけど、理屈を聞けば意味がわかるし、ちゃんと知識と考え続ける能力があればたどり着けるものだと考えると、やる気がでる

2020年12月09日 リンク

その他
tettekete37564
3の割り算のやつあとで読む。8ビット時代にアセンブラで整数の割り算実装した事あるはずだけどもう全然覚えてない。

その他
terazzo
terazzo この記事は誤差の正当性の証明が核だな。/宴会の割り勘で14人で割るときに総額を7倍するとかしてた(誤差はまあ愛嬌)。5人なら2倍して10で割る(こっちは誤差なし)。

2020年12月09日 リンク

その他
naoya2k
3で割るやつの実装、さもすごいことのように書かれているけど、学校では「割り算は遅いので、除数が定数の場合は一般的に逆数の乗算で実装されます」の1行で説明完了してたしみんなそれで理解できてたで。

その他
kujoo
"1431655766 という謎のマジックナンバー"

その他
hatest
10進数の世界の常識と2進数の世界の常識の違い

その他
oktnzm
32.768 kHzを連想した。謎定数好き。

その他
sharaku3eyes
すごい。こういう人と働きたい

その他
Sampo
除算を乗算に変換するアイディア、どうも学部の授業でやってたらしいんだけどおれの取った講義では習わなくて、院に行ったあと学部の後輩の勉強みてやってたときに出てきてなんだこの神テクはってなった思い出。

その他
higamma
やばい...

その他
kirakking
理論上の除算とくらべて、数値の精度に限度があるからこそできるハックを感じて面白い。

その他

注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています

リンクを埋め込む

以下のコードをコピーしてサイトに埋め込むことができます

プレビュー
アプリのスクリーンショット
いまの話題をアプリでチェック!
  • バナー広告なし
  • ミュート機能あり
  • ダークモード搭載
アプリをダウンロード

関連記事

usersに達しました!

さんが1番目にブックマークした記事「2で割ることと3で...」が注目されています。

気持ちをシェアしよう

ツイートする

2で割ることと3で割ること - Qiita

この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高... この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除

ブックマークしたユーザー

  • techtech05212023年05月06日 techtech0521
  • poppyhi2021年02月07日 poppyhi
  • wktk_msum2021年01月12日 wktk_msum
  • mjtai2021年01月01日 mjtai
  • questbeat2021年01月01日 questbeat
  • Toge2020年12月29日 Toge
  • efcl2020年12月27日 efcl
  • odangosan2020年12月27日 odangosan
  • tasshi8202020年12月23日 tasshi820
  • kazoo_oo2020年12月21日 kazoo_oo
  • lugecy2020年12月20日 lugecy
  • mhag2020年12月16日 mhag
  • k0yoshitsugu2020年12月16日 k0yoshitsugu
  • igrep2020年12月16日 igrep
  • thotentry_hatebu1972020年12月13日 thotentry_hatebu197
  • sterope2020年12月11日 sterope
  • rryu2020年12月11日 rryu
  • shirokurostone2020年12月11日 shirokurostone
すべてのユーザーの
詳細を表示します

ブックマークしたすべてのユーザー

同じサイトの新着

同じサイトの新着をもっと読む

いま人気の記事

いま人気の記事をもっと読む

いま人気の記事 - テクノロジー

いま人気の記事 - テクノロジーをもっと読む

新着記事 - テクノロジー

新着記事 - テクノロジーをもっと読む

同時期にブックマークされた記事

いま人気の記事 - 企業メディア

企業メディアをもっと読む

はてなブックマーク

公式Twitter

はてなのサービス

Copyright © 2005-2025 Hatena. All Rights Reserved.
設定を変更しましたx

AltStyle によって変換されたページ (->オリジナル) /