工学じじいの縁側日記

工学じじいの縁側日記

引退間際の工学じじいがきままに、プログラミングやデバイス、工学について呟きます。

トップ > プログラミング

【python】pythonでゲームを作るって有りなのか真面目に考えた結果の選択肢

pygame python ゲームプログラミング プログラミング

pythonでゲームを作るって有りなのか真面目に考えた結果の選択肢

f:id:gomta777:20191203004356j:plain

pythonで使えるゲームライブラリ

最近のゲーム界隈のプログラミングの流行として、ゲームエンジンてのがあります。有名なものだと、Unityとか、UnrealEngineとかですね。こいつらは、ライブラリというよりは、ゲーム向けの統合開発環境のようなイメージですね。昔は、フレームワークって言ったりもしたけど、とりあえずゲームフレームワーク、ゲームエンジンってそんな明確な分類はしていないようです。
それに対して、ゲームに必要な画像の読み込みや表示、制御などのAPIを提供するのみのものを、ゲームライブラリと呼んでるっぽいですね。
python界隈ではゲームを作ろうとすると、フレームワークというよりはライブラリと呼ばれる分類のものを利用することになりそうです。


pythonで使えるゲームライブラリ

あちこちのページに書いてはありますがpythonで使えるゲームライブラリは主に以下のものがあります。



pygame

f:id:gomta777:20191202230350p:plain

ちょっと有名なゲームライブラリにSDLってやつがありまして、そいつをpythonでラッピングしたのがpygameってことになります。
XNAとか、enchant.jsとかよりは、優しくないですが、SDL自体はとてもメジャーなライブラリということになりますので、pythonでゲーム作ろうと思ったら、とりあえず一番手に上がってくるのではないでしょうか？

現在絶賛とん挫中のうちのテトリス作ってみた企画もpygameです。


初心者がpythonとpygameでテトリス風ゲームを作ってみた　＃０３

youtubeを見るとサンプルが何個かあります。


Helicopter shoot em' up game made with Python and PyGame

ただ、なんだかんだ「ちゃんと」ゲームの形に仕上げて、１個のまとまったゲームとして使えそうだな？と納得するサンプルには出会えないなという印象です。

また、ほかの言語界隈では、SDL2が現在の主流のため、SDLベースのpygameはソフトウェアレンダリングだし、なんか処理が遅いなぁって感じのようです。

もう少しで、SDL２に対応した新バージョンが出るようです。
期待して待ちましょう。

公式サイト：
https://www.pygame.org/

日本語ドキュメント：
westplain.sakuraweb.com

インストール：

pip install pygame

PySDL2

f:id:gomta777:20191202230650p:plain

一時期pygameのテンションが下がりまくって、SDL２対応も見送りされて、これからはpySDL2がpygameの後継になるでしょって言われていたライブラリです。
python用に作られたゲームライブラリというよりは、pythonによるAPIラッパーという感じなので、必要なものは自分で作る意気込みが必要そうです。

これでちゃんとゲーム作ったよっていう記事がそんなにみあたりません。。。これぐらいですかね？

lukems.github.io


公式サイト：
pysdl2.readthedocs.io

インストール：

pip install pysdl2

pyglet

f:id:gomta777:20191202230845p:plain

ディ〇ニーのピンクの豚さんではないです。
マルチプラットフォームのウィンドウイング、マルチメディアライブラリです。ゲームにとどまらず、リッチなUIのアプリケーションの開発もターゲットにしており、フルスクリーンのアプリ製作も可能です。
　ウィンドウ制御、イベントハンドリング、OpenGLグラフィックス、画像と動画の読み込み、サウンドと音楽の再生をサポートしています。画像や、音楽のサポート形式も豊富で、様々な形式のものを読み込むことができます。
また、依存ライブラリがなく単独で動作するという特徴があります。

pygletで作ったminecraftクローンです。

www.youtube.com


公式ページ：
pyglet.readthedocs.io


インストール

pip install pyglet

panda3D

https://camo.githubusercontent.com/db79e6ff5d67eb944e41a5629f9cd9c43cc701c7/687474703a2f2f692e696d6775722e636f6d2f664438385a4d552e706e67

3Dでゲームを作るなら、これが本命でしょうか？
ゲームライブラリというよりは、冒頭に話したゲームフレームワークに属するようです。というのも、
「THE OPEN SOURCE FRAMEWORK FOR 3D RENDERING AND GAMES」
と、公式でうたってますもんね。そして、ゲームのみならず３DCGレンダリングフレームワークとしても機能するので、３DCGシーンの構築などにも役に立ちそうです。UnityやUE4にならぶとまでは言わないまでも、python環境でのフレームワークといえばpanda3Dになるのではないでしょうか？

Panda３Dサンプル：
www.youtube.com

公式ページ：
www.panda3d.org

インストール

pip install Panda3D

kivy

f:id:gomta777:20191202235100p:plain

pythonでゲーム作れないかな？ということで検索すると必ず出てくるのがkivyです。
kivy自体はゲームライブラリではありません。
NUI（Natural User Interface）構築のためのUIライブラリという位置づけで開発されています。マルチタッチイベントに対応しており、マウス、キーボード、TUIO、OS固有の広範な入力をサポートしています。OpenGL ES 2のVertext Buffer Objectとshadersを使用したグラフィックライブラリ、マルチタッチ対応のさまざまなウィジェット
、カスタムウィジェットを容易にデザインするための中間言語Kvを持つ、などの特徴があります。
pythonでアプリにGUIを導入しようと思うとコレって感じですかね？
そういう感じなので、日本語の資料も多く公式のドキュメントもほとんど日本語化されています。

pyky.github.io

ユーザーによる解説ページも非常に豊富ですので使いやすいかと思います。

描画や画像読み込みなどの機能も豊富で、それらkivyの持つ様々な機能を使ってゲームを作ることも可能です。

kivyゲームサンプル：
www.youtube.com

公式ページ：
kivy.org

インストール：

  • 最新のpipとwheelを持っていることを確認します:
python -m pip install --upgrade pip wheel setuptools
  • 依存関係をインストールします（gstreamer（120MB)が必要ない場合はスキップできます、 Kivy’s dependencies(Kivyの依存関係) を参照してください）
python -m pip install docutils pygments pypiwin32 kivy.deps.sdl2 kivy.deps.glew
python -m pip install kivy.deps.gstreamer
  • Python 3.5の場合には、glewの代わりに使用できるangleを追加でインストールできます:
python -m pip install kivy.deps.angle
  • Kivyをインストールします:
python -m pip install kivy

Pyxel

f:id:gomta777:20191203000604p:plain

何気に、今回一押しのライブラリです。

Pyxel (ピクセル) はPython向けのレトロゲームエンジンです。

使える色は16色のみ、同時に再生できる音は4音までなど、レトロゲーム機を意識したシンプルな仕様で、Pythonでドット絵スタイルのゲームづくりが気軽に楽しめます。

ファミコン世代にはたまらんこだわりを感じるゲームライブラリです。
ファンタジーコンソールを参考に作られており、昔の８ビット機のようなゲームの製作をターゲットにしています。

製作者が日本人なことと、じわじわ人気が出てきているので資料も増え続けています。
そして、ゲーム制作時に無駄に高機能なものを突き付けられ途方に暮れることもないです。まずは、このライブラリでじっくり本来の「ゲーム」ってなんだ？というところを学んでみるのに最適ではないでしょうか？

公式ページ：
pyxel/README.ja.md at master · kitao/pyxel · GitHub

インストール：

pip install -U pyxel

所感

足りないものは、何でも作ればいいじゃん、って人はSDL系のものを使うのもいいですが、やっぱり、初心者だし簡単にちょっと〇〇してみたいなぁみたいなときに使えるライブラリがなくて困ってましたが、これからはちょっと規定できるのかなって思います。
やたら、pygameおすすめされてますが、そのページをよく見てみてください。ゲーム作ってないんで(笑)
～してみた、で終わってるページ多くないですか？


第3回　チキチキ　プログラミング初心者のための型に関する考察　～pythonで基数変換してみるよ～

情報処理技術者試験 自分学習 プログラミング python C言語

第3回　チキチキ　プログラミング初心者のための型に関する考察　～pythonで基数変換してみるよ～

f:id:gomta777:20191028111136j:plain



はじめに

1回目で、型ってなんだ、2回目で整数型の中身と正負の整数のメモリ表現を見てみました。

ko-gaku-jiji.hatenablog.jp
ko-gaku-jiji.hatenablog.jp

2回目でも紹介した通り、pythonでは、組み込み関数binを使うことによって、整数を2進数に変換することができます。
また、表示のみだけであればprint関数の書式設定で何とかなります。

ですが、

num = int(input())
print(bin(num))
print(bin(-num))

これで、入力を150とすると

150
0b10010110
-0b10010110

0bは2進数表記であることを表します。なので、150を表すビット列は10010110となります。pythonの型にはCやjavaの型（＝メモリサイズ＋表現形式の決まり）と違って決まったサイズがありませんので、150をそのまま2進数に変換した10010110が表示されています。
これが例えば、CやJavaのshort型だったとすると

型 メモリサイズ
short 16ビット(2byte)
int 32ビット(4byte)

なので、
150(10進数) => 0000000011010110(2進数)
となります。
（pythonは、これが普通の世代から見るとなんか気持ち悪いｗ）

そして負の数のビット表現は2の補数を取って、

10進数 2進数
150 0000000011010110
-150 1111111100101010

となるはずですが、まさかの、-0b10010110となります。

よろしい、ならば自作関数だ

10進数と2進数を変換する関数を作る

引数に10進数と整数ｎ（2<=n<10)を与えると、それをｎ進数に変換して返す関数

def base_conv(number, n):

を考えます。
与えられたｎｕｍをｎ進数へ変換するには、前回説明した通り

ko-gaku-jiji.hatenablog.jp

  • num>0の間以下を繰り返す。
  1. 与えられた整数numをnで割って、商q、余りrを記録
  2. num=q

記録したrを逆順に並べるとn進数で表現されたnumとなります。

pythonで表現してみる

上の処理をpythonで書きます。

ちゃんと動いてそうですね！
実行結果もあってそうな気がします。

2，8，16進数のはなし

コンピュータの世界では、2の乗数と、それに関連して8の倍数を使うことが多いです。
例えば、

8bit = 1byte
1024(=2^10) bit = 1Mbit

0と1の2進数の世界でデータや命令ができているので自然といえば自然なことですね。
また、2進数でデータを表記していると、どんどん長くなってしまいます。

0011101001010110(2進数）
035126(8進数）
3A56(16進数）

2進数だと16bit必要だったものが8進数だと7桁、16進数だと4桁で済んでしまいました。
また、2進数、8進数、16進数は2の乗数が基数となっているため比較的簡単に相互変換可能です。なので、結構多くのプログラミング言語に2進数、8進数、16進数表記が使える機能が備わっています。

ちなみにｎ進数は０～（ｎー１）の数字を使って表すというルールがありました。（8進数なら０～７の数字で表される）
16進数を考えてみるとちょっと面白いことになります。

f:id:gomta777:20191112232742p:plain
図：16進変換

3797（10進数）を16で割っていって余りを下から並べると、

１４　１３　５

となってしまします。１桁あたりに2つの数字が入ってしまいます。
そりゃそうですよね。16進数なんで０～１５の数字を一けたに使うんだもん。でも、このままだと、繋げて書いたときに、14135と区別がつきません。困りました。
っということで、16進数の１０～１５の数字が出てきてしまったときは、桁で使える数字（０～９）は売り切れてもうないのでアルファベットを使います。

10 A
11 B
12 C
13 D
14 E
15 F

3797（10進数）=> 14 13 5(16進数）=> ED5(16進数）

10進数を2，8，16進数に変換する関数

10進数の数字と、基数（２，８，１６）を入力すると指定された基数に変換して返す関数を作ります。
２，８，１６以外の基数が指定されたときは、Ｎｏｎｅを返します。

print(base_conv(3797, 16))
を試すと、ちゃんと
ED5(16)
が表示されます。

そして負の数

(bin)だと２の補数に変換できないよねってこと

はじめに書いたとおり、組み込み関数bin()で整数をビット列に変換できます。しかしながら、負の数には対応しておらず、2の補数が表示されるわけではありません。これは、pythonが動的に型を扱う言語であることの特徴であって、別に欠点であるわけでも、バグでもありません。
ただし、静的に型を扱う言語は多数あり、型についての知識も大事かなと思います。という理念のもとに、型についてグダグダと語ってきました（笑）
話を戻して、2進数の負の数を2の補数で表示してみたい！という願望をかなえる関数を書いてみます。

型＝メモリサイズ＋表現方法

でしたね。ＪａｖａやＣ言語では、整数型はメモリサイズによってchar(byte)、short、int、longなどと名前が変わっていきます。

ちょっと中身で比べてみます。
pythonで、
print(bin(3))
を実行すると
0b11
が表示されます。

しかし、例えばＣ言語では
char c=3;
とすると中身は
00000011
となります。
short c=3;
だと、
0000000000000011
です。
charは8ビット、shortは16ビットの固定幅でデータが用意されるというわけです。

これを、Ｃ言語の場合で負の数（－３）にしてみます。
char c=-3の場合：
00000011　(元の2進数）
11111100　(1の補数（ビット反転））
11111101　(2の補数（1の補数＋１））　←　これがー3の8ビット表現

short c=-3野場合：
0000000000000011　(元の2進数）
1111111111111100　(1の補数（ビット反転））
1111111111111101　(2の補数（1の補数＋１））　←　これがー3の8ビット表現

となります。pythonの場合は、ビット幅が決まっていないので内部表現はこうなっているとは限らないです。

pythonで表現してみる

今度は、この処理を、関数にしてみます。

def plus_one(binarr):
は、2進数で一番右のビットに1を足した結果を得る関数

def bit_reverse(binarr):
は、すべてのビットをビット反転する関数です。

結果も、ちゃんと動いているっぽいですね。

所感

pythonで基数変換する処理を書いてみました。
たまには、こういうプログラムも楽しいかもしれない（笑）


↓よかったら押してほしいです！
にほんブログ村 科学ブログ コンピュータサイエンスへ
にほんブログ村

【python】第２回　チキチキ　プログラミング初心者のための型に関する考察　～負の整数～【学習】

情報処理技術者試験 自分学習 プログラミング python C言語

第２回　チキチキ　プログラミング初心者のための型に関する考察　～負の整数～

f:id:gomta777:20191028111136j:plain



はじめに

第１回では、正の整数と２進数の関係、、２進数とビット数の関係、オーバーフローなどについて考えてみました。

ko-gaku-jiji.hatenablog.jp

  • 型
    • 型とはメモリ内での数値表現のこと
    • 大きく分けて、整数、実数、文字型などがある
    • 整数型は２進数で表現され、その表現できる範囲はbit数で決まる
    • 整数型の型の違いは主に、bit数の違い
    • 桁あふれが起こると、あふれた桁は捨てられる
  • 型変換
    • ｎ進数について
    • １０進数とｎ進数の変換方法
    • ｎ進数から１０進数に変換する方法

などを、実例を交えて考えてみました。
今回は、整数型の負の数について考えてみたいと思います。
おそらくpythonプログラマにはあまり必要ない知識かと思いますが、その表現法や仕組みは情報処理技術者試験に頻出ですので、すこし掘り下げてみましょう！

応用情報技術者平成２５年秋期 午前　問３

負の整数を表現する代表的な方法として，次の3種類がある。
a. 1の補数による表現
b. 2の補数による表現
c. 絶対値に符号を付けた表現(左端ビットが0の場合は正，1の場合は負)
　4ビットのパターン1101を a～c の方法で表現したものと解釈したとき，
値が小さい順になるように三つの方法を並べたものはどれか。



    

    ア
     a, c, b 
    

    

    イ
     b, a, c 
    

    

    ウ
     b, c, a 
    

    

    エ
     c, b, a

こんな感じの問題が基本除法技術者試験や、応用情報技術者試験にぽろぽろと出題されます。

符号付と符号なし整数

pythonでは、符号あり、符号なしの指定を整数につけることはできません。また、bit数による範囲の制限がないため、pythonコーダーの皆さんは、特に整数の型について意識することなくコーデイング出来るということは、前にも書きました。
しかしながら、世の中のこれまでの主流プログラミング言語（C/C++，C#，Javaなど）でのコーデイングの際には、コーダーはそのデータの型の値域を考えて、また、メモリ使用量をなるべく少なくするために適切な型を考えながら書いていくのが通常でした。
（最悪、浮動小数点数よりも整数の方が計算が何倍も速いということで、小数点数を整数で計算するギミックなんかを作ったり。。。）

ということで、整数型では、同じビット幅で同じビット列でも２種類の読み方ができてしまいます。

10001000 136 符号なし
10001000 -120 符号あり

pythonでは、ほとんど考えに及びませんが、Cプログラマなどは、この差を考えながらコーデイングしているってわけです。
実際には、例えばC言語の場合は変数を宣言するときに、以下のように宣言することになっています。

signed/ unsigned 型 変数名 ; 実際の宣言文（全部繋げたやつ）
signed int bar ; signed int bar;
unsigned int bar ; unsigned int bar;
signed char cbar ; signed char cbar;
unsigned char cbar ; unsigned char cbar;

signedが符号あり、unsignedが符号なしを表します。
(実数型では、その表現法の内容からsigned,unsignedの区別が持てません)
signed, unsignedは整数型の修飾子ということになります。
また、デフォルトでは変数はsignedとして宣言されることになっているので、signedとあえて書くことはあまりありません。

符号ありと、符号なしの整数値

前回の、説明で以下のような表がありました。

型名 種類 サイズ 範囲 備考
int 整数 4byte -2147483648 〜 2147483647 負数は２の補数表現
short 整数 2byte -32768 〜 32767 負数は２の補数表現
char 整数 1byte -128~127 負数は２の補数表現

これは、すべてsignedの時の表となっています。それでは、unsignedの時はどうなるのでしょうか？

型名 種類 サイズ 範囲(signed) 範囲(unsigned) 備考
int 整数 4byte -2147483648 〜 2147483647 0 ～ 4,294,967,295 負数は２の補数表現
short 整数 2byte -32768 〜 32767 0 ～ 65,535 負数は２の補数表現
char 整数 1byte -128~127 0 ～ 255 負数は２の補数表現

実際の詳しいビット数とデータ範囲の関係については、MSDocsにまとまっています。
データ型の範囲 | Microsoft Docs


次は、実際にメモリ内で負の数がどう表現されているか見てみます。

３つの負数表現

負の数の表現には大きく分けて、３種類あります。
初めに貼った、応用情報技術者試験の問題ではその３つがフル出題されています。
詳しくは以下の３つです。

  • 負数の表現
    • 符号付絶対値表現
    • １の補数表現
    • ２の補数表現

それぞれの表現法を見ていきましょう。

負の数の表現：符号付絶対値表現

数値を符号と絶対値に分けて表現する方法です。
算数などで習う計算法と同じ表現法なので、非常にわかりやすいです。
符号：（＋、－）
絶対値：（０～９の数字の羅列）

  1. 100, -100など

これはわかりやすいですね、ただ、（型にうるさい）コンピュータの世界では、０と１しか使えずビット数が決まっています。
例えば８ビット整数（char)で、１０進数の-15を表すときに、

１０進数 ２進数 16進数
-15 -00001111 -0F

と出来ればいいですが、＋、－という符号はプログラミング言語（高級言語）では使えても、CPUの命令のレベルでは使えません。
そこで、８ビット中の上位の１ビットを符号として犠牲にして、残りの７ビットで絶対値を表します。

符号 数値
+ 0
- 1

絶対値は7ビットですので、0～127（２^7 - 1)まで表せます。

  1. 105と-105を作ってみましょう

まず、絶対値として、7ビットで10進数の105を作ります。

105(10進数）→　1101001（2進数）

10進数 符号 絶対値 符号付絶対値表現
+105
0
1101001
01101001
-105
1
 1101001
11101001

と、表現するのが符号付絶対値表現です。わかりやすいですよね。

しかし、10進数の0を表現するときに、

10進数 符号 絶対値 符号付絶対値表現
0 + 0000000 00000000
0 - 0000000 10000000

＋０と、－０が出てきます。
さらに、

+105
01101001
+ -105 +
11101001
0
101010010

10進数は足すと0になるのに、2進数では足しても0になりません。

人間にはわかりやすい表現法ですが、コンピュータが計算を行うためにはいろいろ工夫が必要そうです。

負の数の表現：１の補数表現

次は、補数を使う方法です。
一般的にn進数には、2つの補数があります。ｎの補数と（ｎ－１）の補数です。
10進数なら10の補数と9の補数があり、2進数なら2の補数と1の補数がある。
8進数なら8の補数と、7の補数がある。
ってな感じです。

nの補数
(n-1)の補数
足したときにぎりぎりすべての桁が桁上げされる数 足したときにぎりぎりすべての桁が桁上げしない数

10進数の場合は、

元の数 10の補数 9の補数
456 544 543

10の補数：456+544 = 1000
9の補数：456+543 = 999

8進数の場合は

元の数 8の補数 7の補数
456 322 321

8の補数：456+322 = 1000
7の補数：456+321 = 777

2進数の場合は

元の数 2の補数 1の補数
1001 0111 0110

2の補数：1001+0111 = 10000
1の補数：1001+0110 = 1111

となります。どの補数も　ｎの補数＝（ｎ－１）の補数＋１とな

っています。
2進数の場合数字のバリエーションが０と１しかないのでとても簡単で、
1の補数→元の数のすべてのビットをビット反転
101001 → 010110

2の補数→1の補数＋１
101001 -(1の補数)-> 010110 -(1の補数＋1)-> 010111

となります。

ここでやっと、負の数の話に戻りますが、このうち元の数を1の補数に変換したものを負の数として使うものが１の補数表現です。（＝ビット反転したらその数の負の数バージョン）
10進数の59で考えてみます
59の2進表現は　00110011
このとき-59は　00110011 -(ビット反転)-> 11001100

となります。また、最左ビットが１のものを負の数、０のものを正の数として扱います。
つまり、
00001101 => 最左ビットが0なので正の数なので、そのまま10進数に変換して+13を表している。
11110010 => 最左ビットが1なので負の数、 ビット反転してからマイナス符号をつけて10進数に直すと
11110010 -(ビット反転)-> 00001101 -> -13
ということになります。
ただし、この方法でも、

00000000 -> +0
11111111 -> - 0

のプラスマイナスの２つの0が存在してしまします。
つぎに、+13 と -13 を足してみます。

00001101
+11110010
11111111

  • 13は+13をビット反転したものなので、当たり前のように全ビット１になりますが、これは1の補数表現では -0 なので、計算上は正しく計算できているということになります。

1の補数の世界で、正確に足し算を行うためには、普通に足し算を行って、

最上位で桁上りがない場合　＝　そのまま答え
最上位で桁上りがある場合　＝　桁上りを最右ビットに足す

例１）桁上りなしの場合
10進数：　13 + 8 = 21
２進数：　00001101 + 00001000 = 00010101 => 10進数で 13 + 8 = 21


例２）桁上りありの場合
10進数：　13 + (-8) = 5
２進数：　00001101 + (11110111) = 100000100
　　　　　桁上り1　(1)(00000100)
　　　　　最右に桁上りを足す　00000101 => 10進数で 13-8 = 5


このように、演算的に比較的簡単に正しい結果を導けるので、一昔前のコンピュータでは１の補数を使って負の数を表すものもありました。近年では、次に説明する２の補数表現のものが多いと思います。

負の数の表現：２の補数表現

２の補数の作り方については、上で説明したとおりです。１の補数に１を足してできた２の補数を元の数の負の数バージョンとして使う方法です。

先ほどと同様に、10進数の59で考えてみます。

59の2進表現は　00110011
このとき-59は　00110011 -(ビット反転)-> 11001100 -(+1)-> 11001101

となります。また、最左ビットが１のものを負の数、０のものを正の数として扱います。
つまり、１０進数との対応を考えると
00001101 => 最左ビットが0なので正の数なので、そのまま10進数に変換して+13を表している。
11110010 => 最左ビットが1なので負の数、 ビット反転してからマイナス符号をつけて10進数に直すと
11110010 -(-1)->11110001 -(ビット反転)-> 00001101 -> -13
この方法では、0は 00000000 のみです。
また、2つの数の足し算の結果は以下のように求められます。

最上位で桁上りがない場合　＝　そのまま答え
最上位で桁上りがある場合　＝　桁あふれを捨てると答え

例１）桁上りなしの場合
10進数：　13 + 8 = 21
２進数：　00001101 + 00001001 = 00010101 => 10進数で 13 + 8 = 21


例２）桁上りありの場合
10進数：　13 + (-8) = 5
２進数：　00001101 + (11111000) = 100000101
　　　　　桁上り1　(1)(00000101)
　　　　　最右に桁上りを捨てる　00000101 => 10進数で 13-8 = 5

第1回でも説明しましたが、桁上りではみ出てしまったビットは自動的に捨てられます。
つまり、2の補数表現では負の数が混じっても、通常の足し算を行うだけで計算の結果が得られる。
ということです。
ここまでくれば、初めに提示した、応用情報技術者試験の問題解けますよね？


ちょっと問題解いてみる

応用情報技術者平成２５年秋期 午前　問３

負の整数を表現する代表的な方法として，次の3種類がある。
a. 1の補数による表現
b. 2の補数による表現
c. 絶対値に符号を付けた表現(左端ビットが0の場合は正，1の場合は負)
　4ビットのパターン1101を a～c の方法で表現したものと解釈したとき，
値が小さい順になるように三つの方法を並べたものはどれか。



    

    ア
     a, c, b 
    

    

    イ
     b, a, c 
    

    

    ウ
     b, c, a 
    

    

    エ
     c, b, a

ここで出てくる３つの負の数の表現法は、前の節の通りの3つですね。
そのうえで、4ビットのビット列１１０１を3つのパターンで解釈したときに、その示す値がちいさい順に並べたのはどれか、って問題です。

値を実際に計算してみます。
a. 1の補数による表現：1101 ->最左ビット１なので負の数 -(bit反転)-> 0010 -> -2
b. 2の補数による表現：1101 ->最左ビット１なので負の数 -(-1)-> 1100 -> (bit反転) -> 0011 -> -3
c. 符号付絶対値表現だった場合：1101 ->最左ビット１なので負の数 -> (符号)(絶対値) =(1) (101) -> -5

a -2
b -3
c -5

なので、c, b, aとなり、答えは「エ」ですね。


pythonと整数型のビット列

pythonでは、整数値のビット列を得るのに

bin(x)

とするとxのビット列が得られますが、

f:id:gomta777:20191110181508p:plain
図　負の数のビット列

こうなるので、2の補数を得るためには工夫が必要なようでした。



所感

情報処理技術者試験で頻出の、2進数で負の数を表現する3つの方法を解説しました。
実は、pythonでビット列ベースの基数ソートを実装しようと思ったんですが、ちょっとひっかかるところがあったので、この話をしてみました。
次は、ソートの話しできればいいね！
へば、またねー！

↓よかったら押してほしいです！
にほんブログ村 科学ブログ コンピュータサイエンスへ
にほんブログ村

初心者がpython３でソートアルゴリズムを実装してみる【バケットソート＆基数ソート】

algorithm python プログラミング 自分学習

初心者がpython３とpygameでソートアルゴリズムを可視化してみる【バケットソート＆基数ソート】

バケットソート

バケットソートは、ソートのアルゴリズムの一つ。バケツソート、ビンソート（backetとbinでそのままですね）などともいわれる。
データ数ｎに対して、バケツ数ｎを用意すると、O（n）でソートが完了するはずの最強ソートに一瞬見えてしまうソートアルゴリズムです。
ただし、データの値の範囲のバケツを必ず用意しなければならないので、実用的ではない場面の多いアルゴリズムです。
似た仕組みのものに、度数分布を記録していきソートを行う数え上げソートや、桁ごとにバケットソートを行う基数ソートがあります。

アルゴリズム

データに重複がない場合、アルゴリズムはとても単純です。

データ：[ 3, 1, 5, 4, 2 ]

バケツ B[1] B[2] B[3] B[4] B[5]
データ 　

①左から順番にデータを取り出します
データ：[1, 5, 4, 2 ] → 3

バケツ B[1] B[2] B[3] B[4] B[5]
データ 　

②バケツの3番に3を格納
データ：[1, 5, 4, 2 ]

バケツ B[1] B[2] B[3] B[4] B[5]
データ 　 　 ３ 　 　

③１をとりだしバケツに
データ：[5, 4, 2 ]

バケツ B[1] B[2] B[3] B[4] B[5]
データ １ 　 ３ 　 　

④以下繰り返しで、
データ：[2 ]

バケツ B[1] B[2] B[3] B[4] B[5]
データ １ 　 ３ ４ ５

④２を取り出しバケツに入れ、ソート完了
データ：[ ]

バケツ B[1] B[2] B[3] B[4] B[5]
データ １ ２ ３ ４ ５

データの入れ替えや、比較なしにソートが完了してしまう、謎アルゴリズムです。

実装・結果

実装は、特に何の工夫もなく初心者丸出しでやってみました。
もっと効率の良い書き方はあると思います。


[3, 9, 5, 1, 2, 4, 8, 6, 7, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

並べ替えられてますね（笑）

基数ソート（Radix sort）

バケットソートを、桁ごとに行う方法です。バケットソートでは、値の最大値から、最小値の範囲でバケツを用意しなければなりませんでした。
基数ソートでは、基数の桁ベースでソートを行うので、１０進数ならバケツは１０こ、２進数なら、２ビット区切りなら４つ、３ビット区切りなら８つのバケツでソート可能です。

アルゴリズム

下の桁から上の桁に向けて、桁ごとにバケットソートを行います。
１の位でソート

データ：[56, 89, 12, 45, 78, 105, 23, 26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ

①まず、１の位でバケットソートを行います。
データ：[89, 12, 45, 78, 105, 23, 26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 56

データ：[12, 45, 78, 105, 23, 26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 56 89

データ：[45, 78, 105, 23, 26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 56 89

データ：[78, 105, 23, 26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 45 56 89

データ：[105, 23, 26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 45 56 78 89

データ：[23, 26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 45, 105 56 78 89

データ：[26, 33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23 45, 105 56 78 89

データ：[33, 63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23 45, 105 56,26 78 89

データ：[63]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23, 33 45, 105 56,26 78 89

データ：[]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23, 33, 63 45, 105 56,26 78 89

②データを、順番に取り出します。
データ：[12, 23, 33, 63, 45, 105, 56, 26, 78, 89]

③１０の位でソート
データ：[12, 23, 33, 63, 45, 105, 56, 26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ

データ：[23, 33, 63, 45, 105, 56, 26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12

データ：[33, 63, 45, 105, 56, 26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23

データ：[63, 45, 105, 56, 26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23 33

データ：[45, 105, 56, 26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23 33 63

データ：[105, 56, 26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 23 33 45 63

データ：[56, 26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 105 12 23 33 45 63

データ：[26, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 105 12 23 33 45 56 63

データ：[78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 105 12 23, 26 33 45 56 63

データ：[89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 105 12 23, 26 33 45 56 63 78

データ：[]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 105 12 23, 26 33 45 56 63 78 89

④データを、順番に取り出します。
データ：[105, 12, 23, 26, 33, 45, 56, 63, 78, 89]

⑤１００の位でソート
データ：[105, 12, 23, 26, 33, 45, 56, 63, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ

データ：[12, 23, 26, 33, 45, 56, 63, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 105

データ：[23, 26, 33, 45, 56, 63, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12 105

データ：[26, 33, 45, 56, 63, 78, 89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12,23 105

（省略）
データ：[89]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12,23, 26, 33, 45, 56, 63, 78 105

データ：[]

バケツ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9]
データ 12,23, 26, 33, 45, 56, 63, 78, 89 105

⑥データを、順番に取り出します。
データ：[12, 23, 26, 33, 45, 56, 63, 78, 89, 105]
ソート完了！

実装・結果

なんか、うまく表現できなかった気がします（笑）

一応ちゃんと動いてはいるようです。

[249, 100, 466, 596, 715, 360, 630, 627, 797, 762]
[100, 249, 360, 466, 596, 627, 630, 715, 762, 797]


所感

バケットソートと、基数ソートを実装してみました。メモリさえあれば早く動くソートですが、余り実用されているところは見ない気がします。
可視化もやろうかなと思ったのですが、数値をバケツに移動するところをどう表現しようか悩んでちょい保留しました。Javaかjavascriptなら簡単なのになぁと思ったりもしたけど、ちょいと考えてみます。


【python】第1回　チキチキ　プログラミング初心者のための型に関する考察　～pythonで基数変換できるかな？～【学習】

情報処理技術者試験 自分学習 プログラミング python C言語

第1回　チキチキ　プログラミング初心者のための型に関する考察　～pythonで基数変換できるかな？～

f:id:gomta777:20191028111136j:plain

はじめに

こんな記事を見たんですよ。

Sum of three cubes for 42 finally solved – using real life planetary computer

要は、 x^3+y^3+z^3=n となる n（１～１００の自然数） (x, y, z)の組を求める問題です。
３３と４２以外のほとんどの整数については、解かれているか、解がないことが証明されていました。
今年に入って、３３の解がスパコンで解かれて、最近４２の解が５０万台のコンピュータをネットワークで接続し、アイドル時間を借りて計算を行う方式の分散コンピューティングで解かれました。（SETIプロジェクトみたいなもんかな？）
分散コンピューティングにより、今までの探索範囲よりも桁の範囲を広げて計算することができたのが勝因のようです。
ちなみに、答えは。。。

-80538738812075974^3 + 80435758145817515^3 + 12602123297335631^3 = 42

となります。
ちょっと確認してみますね。

ほんとだｗ
それで思ったんですよ。pythonって、こんなでかい値計算できるわけで、んでpythonって、いわゆる型推論してるけど、整数の大きさってどこまで使えるの？

型って？

むかしながらの、FORTRAN, pascal, Cなどのプログラミング言語には、確実に型ってのが存在しています。
簡単には、データを入れるための箱の形式＝コンピュータがデータの形式を判断し、正確に処理を行うための仕組みなのかなと思います。

C言語の主な型

C言語の例を見ると（一部処理系依存の部分がありますので、悪しからず）

型名 種類 サイズ 範囲 備考
int 整数 4byte -2147483648 〜 2147483647 負数は２の補数表現
short 整数 2byte -32768 〜 32767 負数は２の補数表現
char 整数 1byte -128~127 負数は２の補数表現
float 実数 4byte 1.17549e-38 〜 3.40282e+38（±10-38 〜 1038） IEEE754浮動小数点形式
double 実数 8byte 2.22507e-308 〜 1.79769e+308（±10-308 〜 10308） IEEE754浮動小数点形式

つまり、型はそのデータがメモリ上でどう表現されているか、ということになります。

C言語の演算にかかわる型の扱われ方

C言語では変数を使うときは型同士のやり取りに細心の注意を払ってソースを書かなければなりません。
例えば、

#include <stdio.h>
int main(void){
    // Your code here!
    int x=3;
    int y=5;
    
    printf("%lf", x/y);
}

出力は　「０．００００」　になります。
C言語では、整数を整数で割った余りは整数で返ってきます。
また、char型（8bit:-128~127)の整数をカウントアップしていき（そもそも１２７以上カウントアップできないのでintの変数を作ってそれをchar型に代入します）、どのように値が変化するか観察する処理を書いてみます。

#include <stdio.h>
int main(void){
    // Your code here!
    char c = 0;
    int i;
    
    for(i=0;i<300;i++)
    {
        c = i;
        printf("%04d ", c);
        if(i%25 == 0)printf("\n");
    }
}

実際の出力は、

0000 
0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023 0024 0025 
0026 0027 0028 0029 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 0040 0041 0042 0043 0044 0045 0046 0047 0048 0049 0050 
0051 0052 0053 0054 0055 0056 0057 0058 0059 0060 0061 0062 0063 0064 0065 0066 0067 0068 0069 0070 0071 0072 0073 0074 0075 
0076 0077 0078 0079 0080 0081 0082 0083 0084 0085 0086 0087 0088 0089 0090 0091 0092 0093 0094 0095 0096 0097 0098 0099 0100 
0101 0102 0103 0104 0105 0106 0107 0108 0109 0110 0111 0112 0113 0114 0115 0116 0117 0118 0119 0120 0121 0122 0123 0124 0125 
0126 0127 -128 -127 -126 -125 -124 -123 -122 -121 -120 -119 -118 -117 -116 -115 -114 -113 -112 -111 -110 -109 -108 -107 -106 
-105 -104 -103 -102 -101 -100 -099 -098 -097 -096 -095 -094 -093 -092 -091 -090 -089 -088 -087 -086 -085 -084 -083 -082 -081 
-080 -079 -078 -077 -076 -075 -074 -073 -072 -071 -070 -069 -068 -067 -066 -065 -064 -063 -062 -061 -060 -059 -058 -057 -056 
-055 -054 -053 -052 -051 -050 -049 -048 -047 -046 -045 -044 -043 -042 -041 -040 -039 -038 -037 -036 -035 -034 -033 -032 -031 
-030 -029 -028 -027 -026 -025 -024 -023 -022 -021 -020 -019 -018 -017 -016 -015 -014 -013 -012 -011 -010 -009 -008 -007 -006 
-005 -004 -003 -002 -001 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 
0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 0040 0041 0042 0043

となります。
char型の変数の範囲は-128~127までですので、127までは順調にカウントアップしています。
127の次は、-128,-127,...と負の数が登場して１ずつ増えてゆき-2,-1の後、0,1,2,3とカウントアップになっています。
C言語は声高らかに、自分の使うデータ型を宣言して、プログラマの理解の範疇で適切な処理を施していくプログラミング言語ですので、別の型同士の演算などはC言語で決められているルールをプログラム製作者が正確に理解していないと、データ表現の違いによるバグを引き起こしてしまいます。
pythonなどの言語は、その辺はシステムの方が推定して適切な型を内部で使ってくれるのでこのようなことは起こりにくい？と思われます。

ちょっと型の中身をのぞいてみる

ちょっと細かい話になるのですが、基本情報処理技術者試験や応用情報処理技術者試験のテクノロジ系でよく出てくる話ですので、知ってるといいことあるかもしれないよ。
型のある言語C/C++, JAVA, C#等では大体同じような型が使われており、中身も共通する部分が多いです。
一番簡単な整数型に関して、考えてみます。
よく言われるように、コンピュータの内部データはすべて、０と１でできています。（皆さんの書いたソースコード自体も内部では０と１で表される命令群に変換されます）
０と１は、電気的にはONかOFFの信号を表しています。電気的にONかOFFかの羅列でプログラムやデータを読んだり書いたり、加工していったりするんですね。
よく考えてみると面白くないですか？

図：メモリ内のイメージ

２進数の数値表現

前にも書いたのですが、pythonでは、細かいことをやらない限りプログラム製作者はこんなこと気にすることはないのかもしれませんが、知っているとバグの原因の特定が早かったり、ほかの言語への対応が簡単になるかもです。（まぁ、私自身がpython初心者なんですが。。。）
それではさっそく。
整数型は、「プログラム上の処理で扱う変数の入れ物として、整数を表すもの」です。大きさが決まった整数を入れる箱だと思うといいかも。
内部では２進数で値を表します。
２進数は、いわゆるコンピュータの中で使われているとされる０と１しかない値の表現です。１０進数は０，１，２。。。８，９で１０、１１と１０ごとに桁が上がっていきます。
ちなみに、このように、桁が上がるベースとなっている数を「基数（radix)」といいます。
２進数は、

0 1 2 3 4 5 6 7 8 …
０ １ １０ １１ １００ １０１ １１０ １１１ １０００ …

と、２進数だと２ごとに桁が上がっていきます。
何とか進数（ｎ進数）には、２進数以外にも、４進数、５進数・・・と無限に進数があります。
コンピュータの世界では、２，８，１６進数を覚えておけば間違いないです。
１０進数と１～９進数までの数字の並びの対応表を以下に示しておきます。

10進数 2進数 3進数 4進数 5進数 6進数 7進数 8進数 9進数
0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
2 10 2 2 2 2 2 2 2
3 11 10 3 3 3 3 3 3
4 100 11 10 4 4 4 4 4
5 101 12 11 10 5 5 5 5
6 110 20 12 11 10 6 6 6
7 111 21 13 12 11 10 7 7
8 1000 22 20 13 12 11 10 8
9 1001 100 21 14 13 12 11 10
10 1010 101 22 20 14 13 12 11
11 1011 102 23 21 15 14 13 12
12 1100 110 30 22 20 15 14 13
13 1101 111 31 23 21 16 15 14
14 1110 112 32 24 22 20 16 15
15 1111 120 33 30 23 21 17 16

この表を見てわかる通り、ｎ進数には０～（n-1)の数字しかでてきません。
だから２進数は、０と１なんですね。

１０進数と２進数の変換

１０進数をｎ進数に変換するときは、以下の図のように目的の数をｎで割っていき、余りを並べるとｎ進数に変換できます。

f:id:gomta777:20191028121228p:plain
図：１０進数からｎ進数への変換

実際に、１０進数の１３を２進数に変換してみます。

f:id:gomta777:20191028121323p:plain
図：１０進数から２進数への変換

１０進数の１３は２進数では１１０１であることがわかりました。
ほかの進数でも同じようにできます。１０進数の２４を５進数に変換します。

f:id:gomta777:20191028121855p:plain
図：５進数への変換

１０進数の１４は５進数では２４であることがわかりました。

２進数と１０進数の変換

２進数を１０進数に戻すときのイメージを考えるために、１０進数を基数をベースに分解してみます。

1978 =1000+900+70+8 = 1\times10^3+9\times10^2+7\times10^1+8\times10^0 \\ここで (n^0=1)

\begin{array}{l|l|l|l|l} 基数 & 10^3 & 10^2 & 10^1 & 10^0 \\ \hline 値 & 1 & 9 & 7 & 8 & \\ \end{array}

桁の仕組みってこうなってたんですね、ｎ桁目＝基数のｎ乗桁目になっていて、すべての桁の基数の重みｘその桁の数をかけて足したものが、元の数値になる（よくわからない説明ｗ）
多分２進数で同じことをやってみるとすぐわかります。
２進数は、基数２なので桁の重みは2^0,2^1,2^2,…,2^nと増えていきます。（2進のときは桁のことをビット(bit)と呼びます、知ってますよね？）

２進数の1011で考えてみると
\begin{array}{l|l|l|l|l} 基数 & 2^3 & 2^2 & 2^1 & 2^0 \\ \hline 値 & 1 & 0 & 1 & 1 & \\ \end{array}

1\times2^3+0\times2^2+1\times2^1+1\times2^0 = 1\times8+0\times4+1\times2+1\times1 = 8+2+1=11

2進数の１０１１は10進数では１１です（1と0しかない数字選んじゃって分かりづらくなってしまったｗ）

どんな基数の時もこのルールは一緒です。
8進数の765を10進数に変換してみます。

\begin{array}{l|l|l|l} 基数 & 8^2 & 8^1 & 8^0 \\ \hline 値 & 7 & 6 & 5 \\ \end{array}
7\times8^2+6\times8^1+5\times8^0 = 7\times64+6\times8+5\times1 = 448+48+5=501

これで、ｎ進数⇔10進数の変換ができるようになりましたね！

２進数と整数型

整数型は、コンピュータの内部形式では２進数で表すことはわかりました。現実世界ではほとんどのものが１０進数で表されていますので、普段は２進数やほかのｎ進数について考えることもないと思います。
実際プログラミングをしていても、pythonを使っている分にはそんなに気にならないのかなと思います。
（でも、実質C言語と絡むと、ちゃんと理解してるしかないし、基本情報では基礎事項として入ってるし。。。）
コンピュータの回路には、一度にデータをやり取りできる数が決まっています。

f:id:gomta777:20191028123327j:plain
図：昔のCPU

CPUの裏側を見ると細かい足がたくさん生えています、このうちの何本かがデータをやり取りする配線になっています。
CPUの何ビットCPUというのは一度にメモリとのやり取りをするのに使えるビット数のことです。(正確にはレジスタの幅かな？）
大体、データや命令が２進数で表されることもあって、８の倍数（乗数）で増えていきます。
一度にやり取りできる命令やデータのビット数が決められているということは、先ほどの計算のようにただ１０進数を２進数に変換したものを使うと、ビット数が足りなくなったり、余ったりと、いろいろ不都合が出てきます。８ビットしか使えないのに２ビットだけ使ってるとか、８ビットしか使えないのに、データが１５ビットとか、多くても、少なくてもめんどくさいことになりそうですよね。
そこで型の登場なのですが、もう一度型とデータサイズ（ビット幅）の関係を見てみます。

型名 種類 サイズ
int 整数 4byte
short 整数 2byte
char 整数 1byte
float 実数 4byte
double 実数 8byte

一番小さいchar型で1byte=8bitですね。
このときに、1ってデータはどのように入っているのでしょうか？箱が8ビットでできているんで、当然１のみってことはあり得ません。
正解は、

\begin{array}{l|l|l|l|l|l|l|l|l|l} ビット & 7 & 6 & 5 & 4 & 3& 2& 1 & 0\\ \hline 値 & 0 & 0 & 0 & 0 &0 & 0 &0 & 1 \\ \end{array}

00000001でした。箱の何も入っていないところは0で埋めます。
それでは、すべて1で埋まった数はいくつでしょうか？


\begin{array}{l|l|l|l|l|l|l|l|l|l} ビット & 7 & 6 & 5 & 4 & 3& 2& 1 & 0\\ \hline 値 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array}

1\times2^7+1\times2^6+1\times2^5+1\times2^4+1\times2^3+1\times2^2+1\times2^1+1\times2^0 \\ = 1\times128+1\times64+1\times32+1\times16+1\times8+1\times4+1\times2+1\times1\\ = 128+64+32+16+8+4+2+1\\ =255

8ビットの整数では０～２５５の範囲があらわされることがわかりました。
さて、この11111111に1足しちゃったらどうなるでしょう？
数学的には、
11111111+00000001=100000000
です。9ビットの100000000になりますね。でも、今用意している箱は8ビットしかありません。

\begin{array}{l|l|l|l|l|l|l|l|l|ll} ビット & [] & 7 & 6 & 5 & 4 & 3& 2& 1 & 0\\ \hline 値 & 1 & 0 & 0 & 0 & 0 &0 & 0 &0 & 0 \\ \end{array}

型のある言語では、この場合、あふれた1ビットは捨てられます。
結果残った00000000が答えとなります。なので、11111111+1は０です(笑)
この現象を桁あふれ(Overflow：オーバーフロー)と呼びます。
聞いたことはありますよね。

pythonと整数型

さて、pythonの話に戻りますが、pythonでは整数型は多倍長型と呼ばれる記録できるメモリ量が許す限りの大きさが使える整数型を採用してます。つまり、C言語のintやchar型とちがって、型としてビット長がきまっていないのでオーバーフローが起こらない仕様ということになります（それが計算速度が速いかどうかは別）
なので、冒頭のような、-８京とかいう数値の計算をさせても何事もなく計算できるんですね。おもしろいｗ

所感

Sum of three cubes 問題を発端に、pythonの整数の扱いについて、いろいろ考えてみました。
今回は正の整数についてのみ考えましたが、次回は負の数や小数についても考えてみたいと思います。
気づく人は気づいたと思いますが、途中に出てきた表の整数範囲と、今回導き出した範囲は異なっています。この違いについても次回には触れようと思います。
へば、またねー！