]>
<< 2.4 文字列s1から、文字列s2中に含まれる任意の文字を除去 | main | XHTML1.0 に準拠してみよう >>
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 )
となる。
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ビット左シフト
できた!
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もほぼ一緒みたいなので略。
http://www.panopticon.jp/mt/mt-tb.cgi/32
コメントする