]> Panopticon :: K&R in Python :: 2.6 2.7 2.8 ビット演算

<< 2.4 文字列s1から、文字列s2中に含まれる任意の文字を除去 | main | XHTML1.0 に準拠してみよう >>

2.6 2.7 2.8 ビット演算

プログラミング言語C ANSI規格準拠

2.6 in C 位置pからはじまるnビットを右端にセット。他はそのまま。

unsigned setbits(unsigned x, int p, int n){
	//return (x & (~0 << n)) | (x >> (p+1-n)) & ~(~0 << n);
	return x^((x^(x >> (p+1-n))) & ~(~0 << n));
}

最下位ビットを0番目とする。

戻り値の論理式は
X & MASK | Y & ~MASK = Y ^ ( (Y ^ X) & MASK )
から。

これは、各ビットに対して
MASK == 1 のとき、Y ^ ( Y ^ X ) = X
MASK == 0 のとき、Y ^ 0 = Y
なので成り立つ。同様にMASKをひっくり返すと

X & ~~MASK | Y & ~MASK = X ^ ( (X ^ Y) & ~MASK )
となる。

2.7 in C 位置pからはじまるnビットを反転。他はそのまま。

unsigned invert(unsigned x, int p, int n){
	return x ^(~(~0 << n ) << p-n+1);
}

反転させたいビットを1にしたマスクを作って、XORをとってやればよい。
たとえば4ビット目から数えて3ビット分のマスクを作る場合、
11111111 全て1のビット列を用意し
11111000 3ビット左シフト
00000111 反転
00011100 4-3+1ビット左シフト
できた!

2.8 in C nビット右へ回転シフト

unsigned rightrot(unsigned x, int n){
	int i = 0;
	unsigned mask = ~(~0U >> 1);
	for (; i<n;i++){
		if(x & 1 == 1){
			x = (x >> 1) | mask;
		} else {
			x = x >> 1;
		}
	}
	return x;
}

語調と独立な実装を考えると、1ビットずつシフトさせる方法しか思いつかなかった。
1ビット回転右シフトするときには、最も右端のビットがぐるっとまわって左端に入る。
つまり最下位ビットが0の場合は普通にシフトすればよく、1となっているときは左端に1をいれてやる。
そのためには最上位ビットのみを1にしたビット列とORをとってやればよい。

ビット演算子はPythonもほぼ一緒みたいなので略。

カテゴリ

Trackback URI

http://www.panopticon.jp/mt/mt-tb.cgi/32

Trackbacks(0)

コメントする