割る2

本稿では数学における割る2（）や半分（）について述べる.。古代エジプト以降..、この操作は他の数による乗除とは別に扱うようになった。は、割る2を1ステップと数えている.。16世紀末の数学者の中でもこれを別の演算として扱ったものもおり、現代のコンピュータ・プログラミングでも最適化の文脈で別個に扱うことがあ.る。この操作は、10進法でも、コンピューター・プログラミングで使われる2進法でも、その他の偶数基底でも簡単である。奇数を2で割るには、（(N-1)÷2）+0.5を使う。例えば、N=7の場合、((7-1)÷2)+0.5=3.5となり、7÷2=3.5となる。

 2進数 
サムネイル|23（0b10111）を2で割る際に、論理右シフトを使って商を11（0b1011）にする過程。
bit演算では、割る2はシフト演算によっても実装できる。これは演算子強度の最適化の一形態である。例えば、0b01101001（十進数の105）は、1つ右にシフトすると0b00110100（十進数の52）になる。この時、最下位の1は消える。同様に、二の冪による除算は、回右にシフトすることで実装できる。ビットシフトは除算よりもはるかに高速な演算であるから、大変な最適化が見込める.。しかし、コードの移植性と可読性のためには、除算演算を使ってプログラムを書き、この置換をのが最善であることが多い.。以下はRubyでの例である。number = 0b1101001 # => 105 (2進数リテラル)
number >> 1        # => 105 / 2^1 = 52
number >> 4        # => 105 / 2^4 = 6しかし、符号付き2進数の除算を扱う場合、上記の記述は常に正しいとは限らない。右へ1ビットシフトすると2で除算され、常に切り捨てられる。しかし、いくつかの言語では、符号付き2進数の除算は0に向かって丸められる（結果が負の場合、切り上げを意味する）。

Javaはそのような言語の1つで、Javaでは-3 / 2は-1と評価されるのに対し、-3 >> 1は-2と評価される。したがってこの場合、コンパイラは、配当が負になる可能性がある場合に、ビットシフトで置き換えることによって2による除算を最適化することはできない。

 浮動小数点数 
浮動小数点数の演算では、割る2は指数を1減らすことで実行できる（ただし、結果が非正規化数にならない場合に限る）。多くのプログラミング言語には、浮動小数点数を2の冪で除算するための関数が用意されている。例えば、Javaでは、2の累乗でスケーリングするためのメソッドjava.lang.Math.scalbが提供されており、C言語では、同じ目的で関数ldexp が提供されている, Section 7.12.6.6.。

 十進数 
以下のアルゴリズムは10進数のものである。しかし、偶数底の任意の数Nの半分を取るアルゴリズムを構築するためのモデルとして使用することができる。

 Nを書き出し、その左にゼロを置く。
 2桁ずつに分け、以下の表に従って結果の数を書き出す。

最初の桁が偶数偶数偶数偶数偶数奇数奇数奇数奇数奇数次の桁が0 or 12 or 34 or 56 or 78 or 90 or 12 or 34 or 56 or 78 or 9出力0123456789
例: 1738/2=?

「01738」と書ける。

 01: 偶数桁の後に1が続く場合、0。

 17: 奇数桁の後に7が続く場合、8。
 73: 奇数桁の後に3が続く場合、6。
 38: 奇数桁の後に8が続く場合、９。

結果: 0869.

この例から、0は偶数であることがわかる。

Nの下1桁が奇数の場合は、結果に0.5を加える。

 偶奇性 
代替文=キュイゼネア・ロッドを用いた偶奇性の説明|サムネイル|5と6の偶奇性をを使って描いたもの。5は同じ色/長さのどの2本の棒でも均等に2等分できないが、6は3本で均等に2等分できる。

整数の場合、分母が2の割り算は数の偶奇性に関係する。偶数（2そのものと0を含む）は2で割り切れるが、奇数は割り切れない。

 その他の用途 
 計算の簡略化 
5を掛けるには、まず2で割ってから10を掛ける。25を5倍する場合、まず25を2で割って12.5とし、次に10を掛けて125とすることで計算を簡略化できる。

 二分探索 

割る2は、計算機科学における二分探索にも利用されている。これは探索の目標と配列の中央に位置する要素を比較し、等しければその値を返す、等しくなければ目標が存在する可能性がない半分を除外し、残りの半分を同じ方法で探索するということを繰り返す探索アルゴリズムである。二分探索では最悪計算時間がとなり、これは線形探索のよりも高速である。

 脚注 
 出典 

 注釈 

 関連項目 
 1/2
 中央値：データ値の集合を2つの等しい部分集合に分割する値。
 二等分線：幾何学的対象を2つの等しい半分の部分に分割する線。
 マーシャリング：紋章学において、二つの紋章を結合する手法の一つで、そのデザインを半分に分割する方法。
 零除算：ゼロによる除算。一般には定義不可能とされる。
 ：一般には定義できないが、極限の文脈は意味を持つ。

Category:除法
Category:算数
Category:数学
Category:アルゴリズム
Category:コンピュータ