49725

[code]

    p (~0b1010).to_s(2)
    
[/code]

は

[code]

    "-1011"
    
[/code]

になりました。

[【ビット反転】 p ~0b1100 #=> -13になる理由がわかりませ... -
Yahoo!知恵袋](https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10140254400)

には

>
> ここで注意して頂きたいのが、負の数の管理方法です。一言で言うと、「その数にいくつ足すと0になるか」です。例えば~0b1100。2進数の部分に1101(2進数で13)を足すと  
>  (1) 000000000000000000000000000000

とあります。

なにか計算によって`0`が並ぶような数値がビット反転の答えになると推測しました。

しかし`1010 + 1011` は `10101`になるので、理解できません。どうして  
`(~0b1010).to_s(2)`は`"-1011"`になるのでしょうか？

追記：  
コメントで頂いたとおり

[code]

    p sprintf('%b', [0b1010].pack('L').unpack('L')[0])
    p sprintf('%b', [~0b1010].pack('L').unpack('L')[0])
    
[/code]

がそれぞれ

[code]

    "1010"
    "11111111111111111111111111110101"
    
[/code]

となって、名前のとおり反転していることがわかりました。

ここで、

[code]

    p (~0b1010).to_s(10)
    p (~0b1010).to_s(2)
    
[/code]

としてみたところ

[code]

    "-11"
    "-1011"
    
[/code]

となったので、  
10進数で-11  
2進数で-1011  
になることがわかりました。

`2進数で-1011`は`10進数で-11`ですので、質問はどうして`~0b1010`は`10進数で-11`になるのか？ とも言える気がしてきました。


CC BY-SA 4.0
2018-10-28T05:20:57.273
49721
2018-10-28T08:45:51.357
2018-10-28T07:22:01.167
30730
30730
question
ruby
rubyのビット演算子の反転について


ご質問に記載された挙動をきちんと理解しようと思うと、整数を2進数で表す場合の2の補数表現について正しく理解しておく必要があります。

### 【2の補数表現について】

例えば4桁の2進数では、10進表現で0〜15の16通り(=2^4 `^`はビット演算ではなくべき乗を表すものとする)の値を表現できます。

[code]

    2進  10進
    0000   0
    0001   1
    0010   2
    0011   3
    0100   4
    0101   5
    0110   6
    0111   7
    1000   8
    1001   9
    1010  10
    1011  11
    1100  12
    1101  13
    1110  14
    1111  15
    
[/code]

コンピュータ上で負の整数を表すやり方にはいろいろあるのですが、 **最上位ビットが1の場合が負数を表す**
ことにして次のように値を割り振るのを「2の補数表現」と言います。

[code]

    2進  10進
    1000  -8
    1001  -7
    1010  -6
    1011  -5
    1100  -4
    1101  -3
    1110  -2
    1111  -1
    0000   0
    0001   1
    0010   2
    0011   3
    0100   4
    0101   5
    0110   6
    0111   7
    
[/code]

初めてみると、何か不自然な並びに見えるかもしれませんが、(2進)`1111`に`1`を足すと(2進)`10000`になります。計算処理が固定長でしかできないことにして、桁あふれを無視すると結果は(2進)`0000`つまり`0`になります。

つまり **`1`を足すと`0`になる数を`-1`として使う** という表現方法を取っていることになります。

### 【Rubyの場合】

Rubyの場合は、無限多倍長整数が使えるので話がちょっとややこしくなるのですが、整数値の`0b1010`と言うのは正の数のはずですから最上位ビットは内部的には`0`でないといけません。つまり4ビットの2の補数表現で表せる範囲を超えているのです。Rubyの整数処理では必要なビット数をどんどん補ってくれるので、概念的に言うと`0b1010`は

[code]

    (2進)...0000000000001010
    
[/code]

と言うような感じで、上位ビットに延々と`0`が連なる整数を表していると思わないといけません。 **固定長の`1010`ではない** のです。

従って、それを反転した`~0b1010`は、こんな数を表していると言うことになります。

[code]

    (2進)...1111111111110101
    
[/code]

これは最上位ビット(?)が`1`ですから、負の数、値としては(2進)`...0000000000001010`(=`10`)を足すと`...1111111111111111`(=`-1`)になりますから、2の補数的には(10進)`-11`を表している、と考えられるのです。

(10進)`11`を2進法で表すと`1011`で、値が負なので、to_s(2)が作り出す「符号+絶対値表現」では`-1011`なんて表記になります。

`sprintf('%b',
[~0b1010].pack('L').unpack('L')[0])`なんてことをやると、結果の桁数が32桁になったり4桁になったりしてわかりにくいですが、Rubyの整数の2進表現では
**正の数の場合無限個の`0`が、負の数の場合無限個の`1`が前に連なっている**
と思って下さい。(「概念的には」と言うことで、内部的には「符号を表す1ビットまで含めて32ビットに収まるときには32ビットで表す」なんてことをしています。)

* * *

と言うわけでコメントに書かれていることをまとめ直しただけで、「どうして~0b1010は10進数で-11になるのか？」を説明したつもりなのですが、お分かりいただけましたでしょうか。何か分かりにくい部分があればコメントして下さい。


CC BY-SA 4.0
2018-10-28T08:27:57.377
49725
2018-10-28T08:27:57.377
13972
49721
answer


まずは整数がどのようなビット列として考えられているのかを理解する必要があります。

まずビット列とは何かです。始めに、Rubyのビット演算の基になったCでの場合を考えます。Cの`int`は環境依存の範囲の符号付き整数を表します。現在の多くの環境(Windows,Mac,Linuxでのx86,x86_64,arm等)では
231-1 ～ -231
で4バイト(1バイトは8ビット)、つまり、32ビットになっています(範囲やバイト数、1バイトあたりのビット数は環境依存であり、これにあてはまらない環境も存在することに注意してください)。実際の値はメモリ上のビットとして存在しており、0と1の列として表現されます。これがビット列です。数字の`42`を表現した場合は次のようになります。

[code]

    00000000 00000000 00000000 00101010 (42)
    
[/code]

メモリはバイト毎に管理するため、8ビット毎にまとめた形で記録されています(わかりやすいように8区切りにしたのはそのためです)。また、アーキテクチャによって、上位バイトから収める場合(ビッグエンディアン)と下位バイトから収める場合(リトルエンディアン)の二つがあります。これはメモリ上の配置の問題であり、ビット列としてはまとめて一つの列として扱われるため、どちらであっても関係ありません。

正の数は上のように2進数表記と同じになります。0は全て0になるだけですので、こちらも問題ありません。問題となるのは負の数の表現方法です。ビット列における負の数の表現には主に二つの方法があります。一つが1の補数、もう一つが2の補数です。

1の補数は単純に全てのビットを反転することで表現します。`-42`は次のようになります。

[code]

    00000000 00000000 00000000 00101010 (42)
    ↓↓ 各ビットを反転 ↓↓
    11111111 11111111 11111111 11010101 (-42の1の補数表現)
    
[/code]

しかし、ほとんどの環境では2の補数を採用しています(1の補数を採用している環境が現在も存在するかは不明ですが、Cの仕様上は1の補数もあり得ます)。2の補数は表現可能なビット列より1桁だけ大きい数からその数の絶対値を引いた数のビット列が負の数になります。

[code]

      1 00000000 00000000 00000000 00000000 (2の32乗、最大値を超えている)
    -   00000000 00000000 00000000 00101010 (42)
    =   11111111 11111111 11111111 11010110 (-42の2の補数表現)
    
[/code]

ここまでは整数値に範囲が存在する言語での話です。Rubyの整数値であるIntegerは(メモリが許す限り)無限の範囲を持っており、どこまでも大きくなります。そのため、ビット列というものも無限の大きさで考える必要があります。

Rubyのビット列の考えはCと同じです。負の数についても2の補数表現を使用します。しかし、無限の大きさになるため、無限に大きいビット列であると考える必要があります。

[code]

    ...0000 00000000 00101010 (42)
    
[/code]

`...`の部分はその後の部分の繰り返しが永遠に存在する、つまり、0または1が無限にあると考えてください。2の補数を考えるときは表現可能なビット列より1桁大きいと言うことでしたが、今回は無限の大きさです。そこで、無限遠の先に1があると想定して考えます。

[code]

      100...0000 00000000 00000000 (無限大の一つ先の数)
    -  00...0000 00000000 00101010 (42)
    =  11...1111 11111111 11010110 (-42)
    
[/code]

数学的には間違っていますが、イメージとしては上のような形です。無限と言うよりも「十分に大きい」という表現のほうが数学的には正確になると思います。

では、ここからビット反転を考えてみましょう。1の補数であれば負の数にするだけでしたが、2の補数ですのでそうはいきません。

[code]

    ...0000 00000000 00101010 (42)
    ↓↓ 各ビットを反転 ↓↓
    ...1111 11111111 11010101 (~42)
    
[/code]

この数がいくらになるかですが、符号を逆転させれば絶対値がわかります。符号を逆転する方法は負の数にした方法と同じです。

[code]

      100...0000 00000000 00000000 (無限大の一つ先の数)
    -  11...1111 11111111 11010101 (~42)
    =  00...0000 00000000 00101011 (43)
    
[/code]

つまり、`0b101011`の負の数、`-43`になります。2進数で表現すると"-101011"となるでしょうが、ビット列としては`42`を反転させた物になると言うことです。

長々と説明しましたが、2の補数表現におけるビット反転は「正負を反転させて-1した数」と同じになります。上では`42`で考えてみましたが、`10`(`0b1010`)の場合はどうなるかは自分で考えてみてください。

* * *

【補足】  
Ruby
2.3.xまではIntegerは実装上FixnumとBignumの二つに分かれていました。これは実装上の話であり、言語上は区別なく使用できました。2.4.0からはこの区別を無くし、言語上はIntegerに統合されています(
実装上は依然として二つ存在しますが)。30桁のビット列で考えるという解説を見ることがありますが、Fixnumの実装での話であり、全てを説明することはできません。言語仕様上はBignumのような無限の大きさの範囲で考える必要があります。


CC BY-SA 4.0
2018-10-28T08:40:48.070
49727
2018-10-28T08:45:51.357
2018-10-28T08:45:51.357
7347
7347
49721
answer