ソフトウエア入門演習
オンラインテキスト目次

mizutani@rsch.tuis.ac.jp

数のビット表現 (1)

この話題に関する詳細な説明はPDFファイルにあります。
計算機内部で数を表すときには 2進数を使用する。 2進数表現では数を 0 と 1 で表すために、これをビット列とみなして、数の2進数表現をビット表現ともいう。

補数表現

ビット列が与えられたとき、2 の補数表現とは、ビット列の各桁の 0 と 1 を入れ換えた後、最下位ビットに 1を加えたものである。

例えば [0110] の2 の補数は、まず 0 と 1 を入れ替えて [1001] を得、最下位ビットに 1 を加えてて桁上がりすることによって[1010] となることがわかる。 また、 [001011000] の補数表現は [110101000] である。

さて、数を表すとき普通は、当然、正負の符号も考える必要がある。 以下に見るように、正負の数をビット列で表すために2の補数表現を使う。 いま、次のような n 桁 のビット列

[an-1, an-2, ...... ,a1, a0]

において、最左端の最上位ビット an-1(= 0 または 1 ) を符号ビットとして、これに次のように数

a= - an-12n + k=0n-2 ak 2k

を対応させるのである。 このように、その最上位ビットが符号ビットであるような整数のビット表示を補数表示という。

補数による正および負の整数表現

したがって、 (n-1) 桁ビットで表される正整数

[an-2, an-3, .... , a1, a0]

に対しては、符号ビットとして 0 をつけて、n 桁ビット

[0, an-2, an-3, .... , a1, a0]

で表せばよい。

一方、負の整数 -b (b > 0) のときには、その絶対値 |-b|=b の(n-1) 桁ビット表示

|-b| = b = [0, bn-2, .... , b0]

に対する 2の補数表現

2n - b = [1, 1 - bn-2, 1 - bn-3, .... ,1 - b1, 1-b0 + 1]

によって負整数 -b の n桁ビット表示が与えられる(2nは (n-1) 桁ビットで表すことができないために消滅したと考える)。 つまり負の数 ( -b, b > 0 )の n 桁ビット表示は、 2n-1 - b 、つまり 2n-1 からその数の絶対値 ( b )を引いた数を (n-1) 桁ビットで表示し、さらに最左端に符号化ビット 1 を付加たものに等しい。

例えば、8ビット(1バイト)からなる [11111111] を調べよう。 これは、先頭の符号化ビットを 0 にした [01111111] に対応する正の数

k=06 2k = 127

を 27=128 から引いた数 である 1 にマイナスをつけた -1 に等しい。実際、補数表現の定義

[11111111] = -27 + k=06 2k = -128 + 127

から -1 となる。 一方、このビット列 [11111111] の補数表示は定義から [00000001] = +1 となり、上の説明とつじつまが合っている。

8 ビットを使って符号付きの整数を補数表示で表現するとすれば、[10000000] = -27 = -128 から [01111111] = 127 までの全ての整数を表現することができる。

一般に、全体がn ビットで表される符号付き整数 N の数の範囲は,

-2n-1 <= N <= + 2n-1 -1

である。 実際、たとえば2バイト型(16 ビット)の整数(Javaでは short 型)では補数表現として 16 ビット長で表される整数だけを、4バイト型(32ビット)の整数(Javaでは int 型)は補数表現として 32 ビット長で表される整数だけを表すことができる。 つまり、それぞれ表せる整数の範囲は以下のようになる:
2バイト型
-215 = -32768 <= N = 32767<= +215-1
4バイト型}
-231= -2147483648 <= N = <= 2147483647 <= + 231 - 1

となる。 例えば 2バイト型整数では

              [ 0000000000000000 ] =     0 
              [ 0000000000000001 ] =     1
              [ 0000000000000010 ] =     2
              [ 0000000000000011 ] =     3
              [ 0000000000000100 ] =     4
              [ 0000000000000101 ] =     5
              [ 0000000000000110 ] =     6
               ...........................
                   ............
               ...........................
              [ 0111111111111110 ] = 32766
              [ 0111111111111111 ] = 32767
のように整数が表わされる。 もし最後の整数 32767 に 1 が加えらたとすれば、そのビット表現は
              [ 1000000000000000 ]
となり、これは補数表示では数 -32768 = - 215 と表示されてしまう。

整数のビット表示の簡単なプログラム

Java教科書 p26, p52
Javaの整数(Integer)は4バイト型で、整数は符号ビットを含めて32ビットで取り扱われる。

入力した整数のビット列を表示する次のように動作するプログラムを作成しよう。

% java BitTest 45
入力した整数 = 45 のビット表現
Integer.toBinaryString() = 101101

% java BitTest -45
入力した整数 = -45 のビット表現
Integer.toBinaryString() = 11111111111111111111111111010011

この例のように、プログラムの本体 BitTest に与えている 45 や -45 をプログラムの引数という。 この引数はプログラムには文字列として渡されるため、プログラム内で文字列 "45" や "-45" から数 45 や 45 に変換する必要がある。 具体的には、次のように書く。
┏━━━━━━━━━ BitTest.java ━━━━━━
/*
BitTest.java
	入力した整数のビット操作

usage:
> java BitTest -45↓
入力した整数 = -45 のビット表現
Integer.toBinaryString() = 11111111111111111111111111010011
*/

public class BitTest {

	public static void main(String[] args) {
		int n = Integer.parseInt(args[0]); // 文字列扱いの最初の引数を整数に変換

		System.out.println("入力した整数 = " + n + " のビット表現");
		System.out.println("Integer.toBinaryString() = " + Integer.toBinaryString(n));
	}
}
┗━━━━━━━━━━━━━━━━━━━━━━━━

演習

  1. 上のJavaプログラム BitTest.java を書いて、コンパイルして実行せよ。 その際に、引数にさまざまな整数を与えて、そのビット表示を観察せよ。
  2. ビット表現が 101101011 で与えられる整数を計算して求めよ(計算式も添えよ)。
  3. ビット表現 101101011 の(4バイト表示における)補数表示を求めよ。
  4. 4バイト整数で表示可能な整数の範囲を計算式で表し、さらにその値を書け。
  5. 整数 2 と -2、および 101 と -101 のビット表示をプログラムから求めて、4バイト表示として、その2つのビット表示を加えたビット列結果を求めよ。

数のビット表現 (2)


計算機内部では数は 0 と 1 の 2進数で表現されている。 Javaを含むプログラム言語はこれををビットパターンとみなして、2つのビットパターンに対してビットごとのビット演算と,1つのビット列を左右にずらすシフト演算を行うことができる。

Javaで使えるビット演算子とシフト演算子には次がある:

ビット演算子
演算子 意味
 & 論理積  a & b 
 | 論理和  a | b 
 ^ 排他的論理和  a ^ b 
 ~ 否定(反転)  ~a 
シフト演算子
演算子 意味
 << 左シフト  a << n 
 >> 符号付右シフト  a >> n 
 >>> 符号なし右シフト  a >>> n 

ここではビットシフトの様子を理解する。 とくに符号付右シフトと符号なし右シフトの差異を理解することが大切である。

整数のビットシフトの簡単なプログラム

次のように1つの整数を引数としてプログラムを起動して、入力した整数のビット列を表示し、0〜4個だけ左右にビットシフト <<, >>, >>> した結果を表示する次のプログラムを作成しよう。

% java BitRepresentation0 整数↓

┏━━━━━━━━━ BitRepresentation0.java ━━━━━━
/* BitRepresentation0.java 入力した整数のビット操作 usage: java BitRepresentation0 整数↓ */ public class BitRepresentation0 { public static void main(String[] args) { int n = Integer.parseInt(args[0]); // すべて文字列扱いの引数を数に変換 int i; System.out.println("入力した整数 = " + n + " のビット表現"); System.out.println("Integer.toBinaryString() = " + Integer.toBinaryString(n)); System.out.print("\n"); for(i = 0; i < 5; i++){ System.out.println("n << " + i + " = "+ Integer.toBinaryString(n << i) + ": " + (n << i)); } System.out.print("\n"); for(i = 0; i < 5; i++){ System.out.println("n >> " + i + " = "+ Integer.toBinaryString(n >> i) + ": " + (n >> i)); } System.out.print("\n"); for(i = 0; i < 5; i++){ System.out.println("n >>> " + i + " = "+ Integer.toBinaryString(n >>> i) + ": " + (n >>> i)); } } }
┗━━━━━━━━━━━━━━━━━━━━━━━━

演習

  1. 上のJavaプログラムBitRepresentation0.java を書いて、コンパイルして実行せよ。 引数にさまざまな整数(正や負の整数)を与えて、その結果を観察せよ。
  2. ビットシフト << を整数に行うことはどのような結果をもたらしているかを述べよ。
  3. ビットシフト >> を整数に行うことはどのような結果をもたらしているかを述べよ。
  4. ビットシフト >> と >>> の違いはどこにあるかを正と負の整数について確かめて、その結果を述べよ。

2つの整数同士のビット演算の簡単なプログラム

次のように2つの整数を引数としてプログラムを起動して、入力した2つの整数に対するビットごとの演算を行う次のプログラムを作成しよう:

% java BitRepresentation1 整数1 整数2↓

┏━━━━━━━━━ BitRepresentation1.java ━━━━━━
/* BitRepresentation1.java 入力した2つ整数のビット操作 usage: java BitRepresentation1 整数1 整数2↓ */ public class BitRepresentation1 { public static void main(String[] args) { int n1 = Integer.parseInt(args[0]); int n2 = Integer.parseInt(args[1]); System.out.println("整数 n1 = " + n1 + " のビット表現: "+ Integer.toBinaryString(n1)); System.out.println("整数 n2 = " + n2 + " のビット表現: "+ Integer.toBinaryString(n2)); System.out.println("n1 & n2 = " + Integer.toBinaryString(n1 & n2)); System.out.println("n1 | n2 = " + Integer.toBinaryString(n1 | n2)); System.out.println("n1 ^ n2 = " + Integer.toBinaryString(n1 ^ n2)); System.out.println("~n1 = " + Integer.toBinaryString(~n1)); System.out.println("~n2 = " + Integer.toBinaryString(~n2)); System.out.println("~n1 & n2 = " + Integer.toBinaryString(~n1 & n2)); System.out.println("n1 | ~n2 = " + Integer.toBinaryString(n1 | ~n2)); } }
┗━━━━━━━━━━━━━━━━━━━━━━━━

演習

  1. 上のJavaプログラムBitRepresentation1.java を書いて、コンパイルして実行せよ。 2つの引数にさまざまな整数(正や負の整数)を与えて、その結果を観察せよ。
  2. 2つの整数のビット表現が与えられたときに、これらのビット演算結果を自分で計算して、プログラム結果を同一になることを確認せよ。
  3. 否定演算子 ~ の優先順序は高いために、~n1 & n2 を計算するために (~n1) & n2 とカッコを使う必要がないことに注意せよ。 では

    n1 & n2 | n1 と (n1 & n2) | n1 および n1 & (n2 | n1)

    の計算結果を実行するプログラムを書いて、演算子の優先順序について検討せよ。 このように、計算の表現が曖昧になるおそれがある場合には、躊躇せずにカッコをつけて計算意図を明確にすることが非常に大切である。

整数のビット表示をするプログラム

先に書いたプログラムのように、整数 n を Integer.toBinaryString(n) を使って表示すると

Integer.toBinaryString(5) ---> 101

のようにしか出力しないが、実際には整数 5 は8バイト(32ビット)幅で

5 ---> 00000000000000000000000000000101

のように表されているはずである。 整数のビット表をこのように32ビット幅で表示するプログラムを次のように段階的に考えよう。

  1. Javaでは整数情報は4バイト(32ビット)で収納されている。 したがって、正の整数 1 は 00000000000000000000000000000001 (1の左に0が31個ある)のように表されているはずである。 整数 1 を左に (32 - 1) = 31 ビットだけシフトさせると

    1 << 31 ---> 10000000000000000000000000000000

    となるはずである(これを整数の補数表示として考えれば、Java整数で表される最小の整数となる)。 これを

    sh31 = 1 << 31;

    のように整数変数 sh31 に格納しておく。
  2. ある整数 x と sh31 のビットごとの論理積演算 x & sh31 の結果から、整数 x の最左端(符号ビット)が 1 または 0 かを知ることができる。 一方、左端以降の31ビット分は 0 との論理和をとるのですべて 0 となる。 整数 x の最左端ビットを表示するには、数 x & sh31 を31個分「符号なし右シフト >>>」(右にシフトされたときには左から 0 で埋められる)したもの (x & sh31) >>> 31 を表示 つまり、

    (x & sh31) >>> 31);

    すればよい。
  3. n を32桁でビット表示したい整数とする。 整数 i を 0, 1, 2, ..., 31 とすると、整数 ( n << i ) の最左端ビットは n の左から数えて ( 32 -i ) 桁のビットになっているはずである。 したがって、( n << i ) の最左端ビットを表示するには、上の x を ( n << i ) と考えて

    System.out.print( ( (n << i ) & sh31 ) >>> 31 );

    とすればよい。カッコの使い方に十分注意すること。
  4. こうして整数 n の32桁のビットをすべて表示するには、上の i を変化させて 0 から 31 まで繰り返せばよい、つまり、

    for (i = 0; i < 32; i++) {
        System.out.print(((n << i) & sh31) >>> 31));
    }
    

演習

  1. 次のように1つの整数を引数としてプログラムを起動して、入力した整数に対するビット表示をするプログラム BitRepresentation2.java を上で説明した方針にそって書け。

    % java BitRepresentation2 整数↓
    

  2. そのプログラムをコンパイルして、様々な整数を与えて実行せよ。

ソフトウエア入門演習
オンラインテキスト目次

mizutani@rsch.tuis.ac.jp