2の補数

簡単なケース

正の数の表現

桁数が固定された2進数の加算を考える。たとえば4桁(4 bits)の場合に1ずつ加える。

 \begin{array}{cc} 0000 + 0001 = 0001 & (1)\\ 0001 + 0001 = 0010 & (2)\\ 0010 + 0001 = 0011 & (3)\\ 0011 + 0001 = 0100 & (4)\\ 0100 + 0001 = 0101 & (5)\\ 0101 + 0001 = 0110 & (6)\\ 0110 + 0001 = 0111 & (7) \end{array}

負の数の表現

一方、-1は0から1を引いた値として計算される。最初の計算だけ、上位桁から1を借りてこられるとして、以下の様な計算になる。

 \begin{array}{cc} 0000 - 0001 = 1111 & (-1)\\ 1111 - 0001 = 1110 & (-2)\\ 1110 - 0001 = 1101 & (-3)\\ 1101 - 0001 = 1100 & (-4)\\ 1100 - 0001 = 1011 & (-5)\\ 1011 - 0001 = 1010 & (-6)\\ 1010 - 0001 = 1001 & (-7)\\ 1001 - 0001 = 1000 & (-8) \end{array}

上の足し算の結果と下の引き算の結果をを見ると、以下のことがわかる。

  • 正の数(0~7)と負の数(-8~-1)の合計15個で、4ビットの全てのパターンが網羅されている
  • 正の数の最上位ビットは0、負の数の最上位ビットは1

引き算と補数の足し算

たとえば上の例で、正の数と負の数を加えてみる。

 \begin{array}{cl} 0101 + 1110 = 0011 & (5-2=3) \\ 0011 + 1001 = 1100 & (3-7=-4) \\ 1111 + 1100 = 1011 & (-1-4=-5) \end{array}

2の補数を計算したときに0からその数を減じているので、当然の結果ではある。いずれにしても、負数を2の補数で表現することで、減算を加算で代えることができる。

2の補数を得る方法

2の補数を得るのに、いちいち0から引かなくても、以下の方法で可能。

  1. 整数のビットパターンを反転
  2. 1を加える

4ビットの例では以下のとおり。

 \begin{array}{cc} 0001 \rightarrow 1110 \rightarrow 1111 & (-1)\\ 0010 \rightarrow1101 \rightarrow 1110 & (-2)\\ 0011 \rightarrow1100 \rightarrow 1101 & (-3)\\ 0100 \rightarrow1011 \rightarrow 1100 & (-4)\\ 0101 \rightarrow1010 \rightarrow 1011 & (-5)\\ 0110 \rightarrow1001 \rightarrow 1010 & (-6)\\ 0111 \rightarrow1000 \rightarrow 1001 & (-7)\\ 1000 \rightarrow0111 \rightarrow 1000 & (-8)\\ \end{array}

すなわち、固定長の整数の場合、ビット反転と加算機能があれば、減算を実現できる。

典型的なビット数の整数範囲

8ビット

byte型でよく見る値。

 \begin{array}{lllr} 0111\:1111 = &2^7 - 1 &=& 127 \\ 1000\:0000 = &-2^7 &=& -128 \end{array}

16ビット

short型でよく見る値。

 \begin{array}{lllr} 0111\:1111\:1111\:1111 = &2^{15} - 1 &= &32767 \\ 1000\:0000\:0000\:0000 = &-2^{15} &= &-32768 \end{array}

32ビット

一般的なint型で絶対値が約21億。

 \begin{array}{llr} 2^{31} - 1 &=& ‭2,147,483,647 \\ -2^{31} &=& -‭2,147,483,648‬ \end{array}

64ビット

long型、絶対値が約920京(!)

 \begin{array}{llr} 2^{63} - 1 &=& ‭9,223,372,036,854,775,807 \\ -2^{63} &=& -‭9,223,372,036,854,775,808‬ \end{array}

 

Python3 – 数値と文字列の相互変換

数値から文字列への変換

10進数(str関数)

str関数で引数の数値を文字列化。

整数の場合、桁数が多くてもそのまま文字列化される。

実数の場合は有効数値で丸められる。

浮動小数点で与えると、桁数が収まる範囲で固定少数表示の文字列になる。

2進数、8進数、16進数

組み込み関数を使う方法

bin、oct、hex関数を使った場合、プレフィックス’0b’、’0o’、’0x’がついた文字列になる。

format関数を使う方法

format関数の第2引数に基数に対応した文字を指定する。

第2引数で、桁数を指定して空いた上位桁を0で埋めることができる。

書式文字列を使う方法

書式文字列と%演算子を使っても、数値を文字列化できるが、2進数には対応していない。

文字列から数値への変換

10進数

整数(int関数)

int関数は整数の文字列を数値化するが、実数形式の文字列を与えるとエラーになる。

実数(float関数)

float関数は実数の文字列を数値化する。固定小数点/浮動小数点のどちらの表現でもかまわない。

2進数、8進数、16進数

int関数の第2引数で基数を指定する。

第2引数には2~36まで指定可能で、0~9とA~Zまで使った36進法まで変換可能。

‘0b’、’0o’、’0x’のプレフィックスを付けた文字列を変換するときは、第2引数を0にする。この場合、10進数も変換可能。

 

Python3 – 数値

int型

整数型はintで表される。

桁数が多くなってもint型として扱われる。

int型のチェック

float型

数値リテラルに小数点を付けるとfloat型として扱われる。float型はCやFORTRANの倍精度の精度。

‘/’による除算の結果は常にfloat型になる。

‘//’による除算では商が整数化される(整数除算と剰余を参照)。

 

Python3 – 書式設定~format

format関数

一つの数値・文字列の書式を設定する場合、format組み込み関数が使える。引数はリテラルでも変数でもよい。

formatメソッド

文字列に対するformatメソッドでも数値・文字列の書式を設定できる(書式設定の書き方は後述)。引数はリテラルでも変数でもよい。

formatメソッドは複数の数値・文字列を扱える。

位置引数として整数を指定し、繰り返して利用することが可能。

キーワード引数として文字列を指定可能。

リストを引数にするときは整数の位置引数とリスト内の引数で指定する。複数のリストを指定するときは位置引数を0、1…と対応させていく。

辞書を引数にするときは整数の位置引数とキーで指定する。キーはクォートで囲まない。

書式設定する場合は、[位置引数]:[書式設定文字列]の形式にする。位置引数を指定しない場合でも':'は必要。

書式設定文字列

formatメソッド

位置引数を省略して書式設定文字列を各場合{:[書式設定文字列]}のように':'を省略することができない。

文字列

{:[</^/>][width]}で左寄せ/中央ぞろえ/右寄せと、全体の幅widthを指定。

{:[char][</^/>][width]}で空白部分をcharの文字でパディング

整数

整数の書式は幅の値に'd'を続けて書く。

整数を2進数、8進数、16進数で表現できる。

基数を指定するとき、'#'を前置すると0b、0o、0xが前に付加される。以下の例では、同時に幅も指定している。2進数表現の場合は0bを付加すると設定幅を超えるので、そのまま表示されている。

浮動小数点

浮動小数点形式の実数の書式は、小数部の桁数だけ指定するときは".3f"のように、幅を設定するときは"10.3f"のように指定する。

固定小数点

固定小数点形式の実数の書式は、小数部の桁数だけ指定するときは".5e"のように、幅を指定するときは"15.5e"のように指定する。

符号の表示方法

正の数値に対して'+'を表示させるときは、数値書式の前に'+'をつけ、正の時にスペースを表示させるときには' 'をつける。

 

指定した幅の先頭に符号等を表示し、右寄せの数値との間をパディングする方法。

format関数

基数表示

数値の基数を指定して、10進数、2進数、8進数、16進数を表示。16進数は英文字の大文字/小文字を選択可能。

位置揃え

文字列や数値を固定幅の中で左寄せ、センタリング、右寄せ(センタリングで左右幅が異なるときは、左に1桁寄せられる)。

パディング

数値を固定幅で表示した場合のデフォルトは右寄せ。'[任意の文字]=’で空白をパディング。特にゼロで埋める場合は’=’を省略できる。

2、8、16の基数に対して固定幅で0でパディングする例。

+符号

‘+’を指定すると、正の値の時に+記号がつく。

カンマ区切り

3桁ごとのカンマ区切り指定。

固定小数点実数

固定小数点の小数部の桁数を’.[桁数]f’で指定する。

浮動小数点実数

浮動小数点の小数部の桁数を’.[桁数]e’で指定する。

実数全体の桁数

小数部の桁数ではなく全体の桁数を’.[桁数]g’で指定する。全体の桁数が整数部の桁数以上のときは、固定小数点で表示される。

 

Python3 – 整数除算と剰余(//, %)

//演算子

//演算子は、切り捨て除算と言われることが多いが、正確には小数部の切り捨てではなく、除算値を超えない最大の整数となる。これは実数の除算結果にfloorを適用した値と同じで、除算結果が負の時に注意を要する。

なお、被除数・除数の何れがマイナスかは問わず、計算結果がマイナスかどうかだけによる。

%演算子

%演算子は、引数の剰余(mod)を与える。除数の正負によって挙動が異なる点に注意。

除数が正のとき剰余は正となり、除数が負のときは剰余は負となる。

 \begin{array}{lcl} 13 \% 3 = 1 & \Rightarrow & 13 = 3 \times 4 + 1 \\ -13 \% 3 = 2 & \Rightarrow & -13 = 3 \times (-5) + 2 \\ 13 \% (-3) = -2 & \Rightarrow & 13 = -3 \times (-5) - 2 \\ -13 \% (-3) = -1 & \Rightarrow &  -13 = -3 \times 4 -1 \end{array}

 

Python3 – range関数

概要

Python3のrange関数は引数で指定した範囲の整数列をrangeオブジェクトで返す。rangeオブジェクトを表示するには、list関数でリスト化する必要がある。

書式

range(end)
0から始まり、1ずつ増加してendに達しない範囲の数列
range(start, end)
startから始まり、1ずつ増加してendに達しない範囲の数列
range(start, end, step)
startから始まり、stepずつ増加してendに達しない範囲の数列

引数は整数である必要があり、そうでなければエラーとなる。

共通なのは、開始値からステップ値ずつ変化させ、終了値に達する直前までの数列を返す、というもので、ステップ値が正の場合にはstart ≤ 値 < endを、ステップ値が負の場合にはstart ≥ 値 > endを要素とする数列となる。

実行例

引数を1つだけ指定した場合は、0から引数未満の整数列となる。

引数を2つ指定すると、第1引数以上、第2引数未満の整数列となる。

引数を3つ指定すると、第1引数から第3引数ずつ増加して第2引数を超える手前までの整数列となる。

第3引数を負の数とすると、降順の数列になる。このとき、第2引数の終了値以下になる前までの数列となっていることに注意。

なお、2つだけ引数を指定して、第1引数>第2引数としても、降順の数列は得られず、空となる。

 

ユークリッドの互除法

概要

ユークリッドの互除法(Euclidean Algorithm)は、2つの自然数の最大公約数を求める手順。

2つの自然数a, b \; (a \ge b)の最大公約数(GCD: greatest common divisor)は、bと剰余r = a \mod bの最大公約数に等しいという性質を利用。数を順次割り込んでいき、剰余がゼロとなったときの除数が最大公約数となる。

(1)   }\begin{align*}a \mod b &= r_1 \quad (a \ge b) \\b \mod r &= r_2 \\&\vdots \\r_{n-1} \mod r_n &= 0 \\&\Downarrow \\\gcd(a, b) &= r_n\end{align*}

証明

以下の余りあり除算を考える。

(2)   \begin{gather*}a \mod b = r \Rightarrow a = bd + r\end{gather*}

a, bの公約数をmとすると、上式は以下のように変形され、mbrの公約数でもあることがわかる。

(3)   \begin{gather*}a = mp , \quad b = mq \\r = mp - mqd = m(p - qd)\end{gather*}

一方、b, rの公約数をnとすると、nabの公約数であることがわかる。

(4)   \begin{gather*}b = ns , \quad r = nt \\a = nsd + nt = n(sd + t)\end{gather*}

これより、a, bの公約数の集合とb, rの公約数の集合は等しく、最大公約数も等しくなる。

(5)   \begin{equation*}a = bd+r \Rightarrow \gcd(a, b) = \gcd(b, r)\end{equation*}

計算例

143と91の最大公約数を求める。

(6)   \begin{align*}&143 \mod 91 = 52 \\&91 \mod 52 = 39 \\&52 \mod 39 = 13 \\&39 \mod 13 = 0 \\&\therefore \gcd(143, 91) = 13\end{align*}

再帰関数による実装

PythonとCLispの再帰関数による実装例は以下の通り。ただし、第1引数>第2引数を前提としており、エラー処理はしていない。

Python

CLisp

 

最大公約数・最小公倍数

約数

約数の定義

整数Nの約数(divisor, factor)とは、Nを割り切る整数(余りが生じない除数)。

整数mNの約数であるとき、m|Nと表し、ある整数aに対してN=maが成り立つことでもある。一般には自然数あるいは0以上の整数で考える。

通常はm \ne 0の条件を課すが、0も含める場合は、N=0の時に限り0が約数になる。

例えば12の約数は、以下の6個。

(1)   \begin{align*}&12 \div 1 = 12 \\&12 \div 2 = 6 \\&12 \div 3 = 4 \\&12 \div 4 = 3 \\&12 \div 6 =2 \\&12 \div 12 = 1\end{align*}

効率的な約数の求め方

m|Nであるとき、\frac Nm|Nである。これよりm = \frac Nmとして、\sqrt N以下の約数m_iを求め、あとはN/m_iを計算すれば、手間が半分で済む。

Nが平方数の場合は\sqrt Nも約数となり、約数の総数は奇数個、平方数でない場合は偶数異なる。

0、1の約数

0の約数は0 = maとなる整数mであり、0以上の全ての整数である。

1の約数は1 = maとなる整数mであり、1のみ。

1は全ての整数の約数。

素数の約数

素数の定義が「1と自身以外に約数を持たない数」なので、約数は2個。

公約数

2つの数の公約数は、それらの最大公約数の約数。

0、1との公約数

aと1の公約数は1のみ。

aと0の公約数は、aの約数全て(0の約数は0以上の全ての整数)。

公約数と剰余

a \mod b = rのとき、a, bの公約数はb, rの公約数でもある。

最大公約数

2つの数の最大公約数(greatest common divisor)を、\gcd(a, b)のように表す。

最大公約数を求める手順として、にユークリッドの互除法がある。

0、1との最大公約数

(2)   \begin{gather*}\gcd(a, 0) = a \\\gcd(a, 1) = 1\end{gather*}

最大公約数と剰余

被除数と除数の最大公約数は、除数と剰余の最大公約数でもある。

(3)   \begin{equation*}a \mod b = r \Rightarrow \gcd(a, b) = \gcd(b, r)\end{equation*}

倍数

倍数(multiple)とは、ある数a(整数に限らない)を整数倍した数である。

(4)   \begin{gather*}\cdots \; -3a,\; -2a,\; -a,\; 0,\; a,\; 2a,\; 3a,\; \cdots\end{gather*}

  • 0の倍数は0のみ
  • 0はすべての数の倍数
  • すべての数は自分自身の倍数
  • すべての整数は1と-1の倍数

最小公倍数

最小公倍数(least common multiple)とは、2つの整数の公倍数のうち、正で最小のもの。

たとえば36と56の最小公倍数は504。

最大公約数と最小公倍数の積

2つの数a, bの積は、それらの最大公約数と最小公倍数の積に等しい。

(5)   \begin{equation*}ab = \gcd(a, b) \cdot \operatorname{lcm}(a, b)\end{equation*}

 

Python3 – mathモジュール

使い方

数学関数を使うためのモジュールで、importし、各定数・関数について、math.[定数名・関数名]として使う。

関数群

主なもの

定数

pi, e
円周率、自然対数の底
inf
浮動小数点の正の無限大。負の無限大は-math.inf。
nan
浮動小数点の非数NaN。

数論関数

ceil(x)
xの天井(x以上の最小の整数)。
floor(x)
xの床(x以下の最大の整数)。
fabs(x)
xの絶対値。
fmod(x, y)
x \mod yを返す。浮動小数点の場合はx % yよりこちらを使う。
gcd(x, y)
xとyの最大公約数。gcd(0.0, 0.0)は0を返す。
isfinite(x)
xが無限でもNaNでもない時にTrueを返す。
ifinf(x)
xが正の無限大か負の無限大の時にTrueを返す。
isnan(x)
xがNaNの時にTrueを返す。

指数・対数関数

sqrt(n)
nの平方根
pow(x, y)
xのy乗(x^y)。pow(1.0, x)、pow(x, 0.0)は常に1.0を返す。
exp(x)
e^x
expm1(n)
e^x - 1。桁落ちに対して最大精度で計算。
log2(x), log10(x), log(x [,b])
それぞれ2、10、bを底とする対数関数。3番目の関数でbを省略した場合は自然対数\ln x
log1p(x)
1+\log x

を返す。ゼロに近いxに対して正確になるよう計算される。

三角関数

sin(x), cos(x), tan(x)
三角関数。
asin(x), acos(x), atan(x)
逆三角関数
atan2(y, x)
[latex]\tan^{^1}を返すが、4つの象限に対する符号から、[latex]-\pi \sim \pi[/lates]の値を返す。
degrees(r), radians(d)
ラジアンから度、度からラジアンへの変換。