C言語の研究・演習編2
第2章 ビット操作
C言語の特徴としてビット単位の処理が出来ることをあげられる。ビット演算子が6種類用意されていることは基本編で述べたが、ここでは有意義なビット操作を見て行こう。
1 ビット操作による乗算
整数型のデータを1ビット左へシフトすることは、2進数を基本とするコンピュータにとっては2をかけることであり、逆に1ビット右へシフトすることは2で割ることになる。
こんなことは誰でも知っていることだろう。しかし実用するにはどうしたらいいかちょっと考えてみよう。
乗算をいま、かけられる数a × かける数b として表示したとしよう。
最初にかける数が偶数か奇数かをまず判断する必要がある。
これについては、第0ビット(LSB)が0の場合は偶数、1の場合は奇数となるから簡単に判断できる。
例として11×11の場合を考えよう。
11×11=(11×10)+11として、かける数を偶数にしておいて、後で11を加算すればよい。
問題は11×10をどうするかだが、これをちょっと工夫して、
(11×2)×(10÷2) として、かけられる数aを1ビット左シフトし、かける数bを１ビット右シフトする。
すると、22×5ということになる。かける数が奇数になったので、
(22×4)+22と書き換えて、あとで22を足すこととして、22×4をまた
(22×2)×(4÷2) として、かけられる数aを1ビット左シフトし、かける数bを１ビット右シフトする。
すると、44×2ということになる。これをまた、かける数bが1になるまで、
(44×2)×(2÷2)として、かけられる数aを1ビット左シフトし、かける数bを１ビット右シフトする。
すると、88×1=88となる。
ここで、赤字で書いた後で足す数を加えよう。すると、
88+22+11=121となって、11×11の答えとなる。
この方法でうまく行くかちょっとテストしてみよう。
#include <stdio.h>
void main()
{
int a, b;
int save_a, save_b;
int odd = 0;
printf("かける数aとかけられる数bをスペースで区切って入れてください
: ");
scanf("%d %d",&a, &b);
save_a = a;
save_b = b;
while(b > 1){
if((b & 1) == 0){ /*かけられる数bが偶数の場合*/
a <<= 1;
b >>= 1;
}
else{ /*かけられる数bが奇数の場合*/
odd += a; /*後で加える数*/
b--;
}
}
a += odd;
printf("-----Result-----\n");
printf("%d × %d = %d\n",save_a, save_b, a);
}
どうだろうか、うまく掛け算されただろうか。
2 パックｎ進数
整数型のデータを10進数で記憶させる場合、数字の0〜9は4ビットあれば表示できるから、32ビットコンピュータには8桁の10進数を入れることが可能である。
正負の判断のため、LSBから4ビットを正負判断用に使用するとしても、1記憶単位で7桁が表示できる。もっと桁を増やしたければ、記憶単位を配列にすればいい。
この方法をパッキングといい、パッキングされた10進数をパック10進数と呼んでいる。
これのテストをしてみよう。
最下位4ビットは正負符号の桁として、正は16進数のEつまり1110、負はFつまり1111で表示させることとして、最大10桁までパッキングすることとしてみよう。
結果は16進数表示で確認しよう。
#include<stdio.h>
#define MAX 2 /*パッキング配列の最大値*/
#define BITS 32 /*32ビットコンピュータ*/
void pack(long int, int *);
void main()
{
long int in;
int su[2];
int *p;
int i;
p = su;
for(i=0; i < MAX; i++) *(p+i) = 0x0;
printf("パッキングする10桁までの整数を入力してください
:");
scanf("%ld",&in);
pack(in, p);
printf("-----Result-----\n");
for(i=0; i < MAX; i++)
printf("%8.8X\n",*(p+i));
}
void pack(long int in, int *p)
{
int i, j;
int i_max;
int temp;
i_max = BITS / 4; /*1配列に最大何桁入れられるか*/
*p = 0xe; /*LSBから4桁を正のとき1110、負のとき1111とする*/
if(in < 0L){
*p |= 1;
in *= -1;
}
for(j =0; in > 0L; j++){ /*inが0になると終了*/
for(i = 0; i < i_max && in > 0L;
i++){ /*1配列の最大桁になるまで*/
if(i != 0 || j != 0){ /*符号の桁は飛ばす*/
temp = in % 10;
in = in / 10;
temp <<= i * 4;
*(p +j ) |= temp;
}
}
}
}
いかがだろうか、符号の桁は飛ばす部分がちょっとややこしいかも知れない。jは配列の添字であるから、jが次の配列を指したとき、つまりj が0ではなくなった場合でi が0のときは、次の配列になっているから符号の桁はないので、シフトさせずに2番目の配列の頭から入れることとなる。
このように、ちょっとだけの処理で全体のアルゴリズムは大きく変わってくるから面白いね。
それでは最後に情報処理技術者試験の問題を見てみよう。
なお、原題はint型を2バイトつまり16ビットとするかなり古いコンピュータをイメージしているようなので現実的な、intを32ビットの型に変えた。
与えられた32ビットのビット列に対し、奇数パリティを求め、これをMSB(第31ビット)に付加してビット列データを得るプログラムである。
奇数パリティとは、32ビットのビット列中の1の数が必ず奇数になるようにビットを設定するものである。
つまり、1100101のビット列データについては、11100101のようにする。
なお、ビット列データはint型データとしてscanf関数により入力させる。さっそく見てみよう。
#include<stdio.h>
int parity(int *, int);
void main()
{
int in;
int i ,n;
printf("奇数パリティを付加する整数を入力してください
:");
scanf("%ld",&in);
n = sizeof(in) * 8;
printf("このサイズは%dビットです\n",n);
for(i = n-1; i >=0; i--){
if( (1 << i ) & in) printf("1");
else
printf("0");
}
printf("\n");
parity(&in, n);
printf("-----Result-----\n");
for(i = n-1; i >=0; i--){
if( (1 << i ) & in) printf("1");
else
printf("0");
}
printf("\n");
}
int parity(int *in, int n)
{
int i;
int cnt = 0;
for(i = 0; i < n; i++){
if( (*in & (1
<< i) ) != 0) cnt++;
}
if ((cnt & 1) == 0){
*in |= (1 << n-1);
}
return *in;
}
いかがだろうか、2進数表示の部分を作ったのでオリジナルな問題とはかなり異なるが、概ね赤色の部分を穴埋めするような問題であった。
scanf関数で与えられた整数値のビット列を1を左シフトしてビット論理積が奇数か偶数かを判断し、偶数の場合はMSBに1を論理和する問題である。