10進数を見たら分かる1ビット
83という数値が与えられたら、最初に分かることがあります。
それは83を2進表記したときに一番右のビットが1であるということです。
なぜ分かるかといえば、83が奇数だからです。
2進数にするとその数が偶数か奇数かという情報は一番右のビットに集約されます。
2進表記を10進表記にする際は、次のように計算するのはよく目にします。
1111 = 8 * 1 + 4 * 1 + 2 * 1 + 1 * 1
これはつまり、一番右以外のビットは必ず2の倍数であることを示しており、2進表記における奇数や偶数は一番右のビットが1(奇数)か0(偶数)かによって判断することができるということです。
10進数を2^xで割った商が偶数か奇数かで判明するビット
2進数のシフトとは
まずはシフトすることの意味を知る必要があります。
2進数に2を掛けると1ビット左にシフトします。
1111 → 11110
なぜかと言えば、10進数に置き換えて考えると分かりやすいのですが
10進数に10を掛けると一桁左にシフトするのはなぜ？と考えるようなもので、当たり前の現象だと納得してしまうのが早いです。
623 * 10 = 6230
気を付けるべきことは、2進数を2で割ったり10進数を10で割ったりするときに、一番右の桁が余りとして出てくるということです。
(10進)
623 / 10 = 62 あまり 3
7348 / 10 = 734 あまり 8
(2進)
1111 / 10 = 0111 あまり 0001
101101 / 10 = 010110 あまり 000001
※2進の10は十ではなく2です
つまり83は2進数でどうかくの？
83 = XXXXXXXXというブラックボックスが与えられたときに、83は奇数であるため、2進表記をしたときに一番右のビットが1であることは最初に述べました。
83 = XXXXXXX1
これを2で割るということは
(A) 83 / 2 = 41 あまり 1
(B) XXXXXXX1 / 10 = 0XXXXXXX あまり 00000001
というように、2進数を1ビット右にずらし、商とあまりに分けることを意味します。
(A)と(B)は10進か2進かの違いで数値は対応しています。
次に知りたいのは(B)の商の一番右の桁が0か1かということです。
つまり
83 / 2 = 41 あまり 1
の商である41が偶数であるか奇数であるかがわかれば0XXXXXXXの一番右のビットが1か0かが分かります。
41は奇数ですから、一番右のビットは1です。
これを順に繰り返していくと下のようになります。
83 / 1 = 83 あまり 0
83 / 2 = 41 あまり 1
83 / 4 = 20 あまり 3
83 / 8 = 10 あまり 3
83 / 16 = 5 あまり 3
83 / 32 = 2 あまり 19
83 / 64 = 1 あまり 19
商に着目してください。
商が偶数であるか奇数であるかが分かればいいので、商83, 41...と順番に見ていくと1100101となります。
これを反対から読んで1010011が83の二進表記になります。
2進数に置き換えると下記のようになります。
ABCDEFG / 2^0 = ABCDEFG あまり 0
ABCDEFG / 2^1 = 0ABCDEF (以下あまり略)
ABCDEFG / 2^2 = 00ABCDE
ABCDEFG / 2^3 = 000ABCD
ABCDEFG / 2^4 = 0000ABC
ABCDEFG / 2^5 = 00000AB
ABCDEFG / 2^6 = 000000A
83を2^xで割ることで2進表記をしたときにxビット右にシフトすることができます。
するとその商の偶奇を判断することで、2進表記の一番右のビットが0か1かが判断できますから、10進数から2進数へ変換することができるという仕組みになっています。
83 = ABCDEFG
41 = ABCDEF
20 = ABCDE
10 = ABCD
5 = ABC
2 = AB
1 = A
上記を見たらすべてのビットが分からなくても、最右ビットが0か1かは瞬間で分かります。
G→F→E→D→C→B→Aという順番で各桁のビットが0 or 1が判明していきます。
83 = ABCDEF1
41 = ABCDE1
20 = ABCD0
10 = ABC0
5 = AB1
2 = A0
1 = 1
よって83は2進表記で1010011。
もっと言えば、よく見る下の2進数変換方法は、2で割った余りで最右ビットを保存して、2で割った商が1ビット右シフトなので、下位の桁から順に余りとして出てきているだけです。
10進数が偶数なら2進表記をしたときに最右ビットが0,奇数なら1になるのは最初で述べました。
83 = 1010011 → 2で割った余り → 最右ビット保存 [1]
↓1ビット右シフト
41 = 0101001 [1]
↓
20 = 0010100 [0]
↓
10 = 0001010 [0]
↓
5 = 0000101 [1]
↓
2 = 0000010 [0]
↓
1 = 0000001 [1]
当たり前ではあるものの、これが本記事で伝えたかった事項です。