「日経ソフトウェア2013年3月号」の連載「プログラミング復習塾」を勉強してみた。

先月から購読を始めた「日経ソフトウェア」ですが、読み途中で放置してたのを引っ張りだしてきて、続きを読んでみました。

日経ソフトウエア 2013年 03月号 [雑誌]

日経BP出版センター

Amazon

第4回ビット演算とシフト演算

まずは用語について調べてみたのでザザザっと書いてみますよ。

正直、今の段階ではサッパリわかりません（笑）

「ビット演算」

整数に対してビット単位で論理演算を行う演算子

「シフト演算」

ビット演算子の一つで数値の各ビットを左または右へシフトさせるための演算子

「排他的論理和」

2つの真偽値のうち、「真」同士もしくは「偽」同士であれば「偽」を、それ以外は「真」を返す論理演算

「ビット否定（反転・NOT）」

あるビットが 0 ならば 1 に、1 なら 0 にすること（ビットを反転させることを「1の補数を求める」と言う）

「絶対値」

ある数値の正の数値。正の場合はそのままの値で負の場合には-1を掛けた値が絶対値

数値を2の累乗に丸める処理（C言語）

・ビット/シフト演算とインクリメント/デクリメントで実装

unsigned int func(unsigned int n){
 if(n <= 1){ return 2; }
 n--;
 n |= n >> 1;
 n |= n >> 2;
 n |= n >> 4;
 n |= n >> 8;
 n |= n >> 16;
 n++;
 return n;
}

・ループとpow関数（累乗を計算する関数）で同じ処理を実装

unsigned int func(unsigned int n){
 unsigned int i = 0, m;
 if( n <= 1){ return 2; }
 while(n > (m = pow(2, i))){
  i++
 }
 return m;
}

基本的なテクニック

ビット演算を使ったフラグ変数の値の切り換え。

・排他的論理和で値を切り替える（C言語）

int flag = 0;
flag = ^= 1; // flag =1
flag = ^= 1; // flag =0
flag = ^= 1; // flag =1

・ビット否定で同じ処理（C言語）

int flag = 0;
flag = ~flag; // flag =-1
flag = ~flag; // flag =0
flag = ~flag; // flag =-1

ループする変数

0〜15をループする処理。

・普通にifを使用（C言語）

n++;
if (n > 16){;
 n = 0;
}

・ビット演算のANDを使用（C言語）

n = (++n) & 15;

絶対値を計算する

abs()といった関数ではなく、XORとシフト演算を利用。

絶対値を計算（C言語）

int a = -100;
a = (a ^ (a>>31)) - (a>>31); // a = 100

int b = 100;
b = (b ^ (b>>31)) - (b>>31); // b = 100

XORの性質＝「2回同じ演算をすると元に戻る」

XORを使った簡易暗号化・複号プログラム（C言語）

#include

int main(int argc, char *argv[]){
 FILE *fp_in, *fp_out;
 int c;
 
 fp_in = fopen(argv[1]), "rb");
 fp_out = fopen(argv[2], "wb");
 
 while（(c = fgetc(fp_in)) != EOF){
  c = c ^ atoi(argv[3]);
  fputc(c, fp_out);
 }
 
 fclose(fp_in);
 fclose(fp_out);

 return 0;
}

Xorshiftで乱数を生成する

XORと乱数を駆使した疑似乱数の生成アルゴリズム（C言語）

#include

unsigned long xor128(void){
 static unsigned long x = 123456789;
 static unsigned long y = 362436069;
 static unsigned long z = 521288629;
 static unsigned long w = 88675123;
 unsigned long t;
 t = (x ^ (x << 11));
 x=y; y=z; z=w;
 return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

int main(void){
 int i;
 for(i=0; i<10; i++){
  printf("%d¥n", xor128());
 }

 return 0;
}