K&Rを読もう(31) 演習 2-6 - 2-8 ビット結合

GCC

この演習問題しんどかった。インラインアセンブラで死にそうに・・・。

演習 2-6

位置pから始まるnビットのyの右端のnビットにセットし,他のビットをそのままにしたxを返す関数setbits(x,p,n,y)を書け。

図にしてみる

setbits(0x55, 4 , 3, 0xFF)を例にする。

p   76543210

x = 01010101
y = 11111111

位置pの4,3,2を結合して

010 111 01

というビット列を作る。

  • pが位置。0から始まる。
  • nが個数。1から始まる。

なので要注意。

方針

まず、マスクをずらしながら作る。

11111111
 << 3
11111000
 反転
00000111
 << 4 - 3 + 1
00011100

x,yにマスクをかけて、or演算を用いて、結合する

010 000 01 | 000 111 00 = 010 111 01

という感じ。

ソース
#include <stdio.h>
#include <stdlib.h>

#define dump(type, bin)                               \
    do {                                              \
        int i;                                        \
        for (i = sizeof (type) * 8 - 1; i >= 0; i--)  \
            putchar('0' + ((bin) >> i & 0x01));       \
        puts("");                                     \
    } while (0)

unsigned char setbits(unsigned char x, int p, int n, int y);

int main(void)
{
    dump(unsigned char, setbits(0x55, 4 , 3, 0xFF));
    return EXIT_SUCCESS;
}

unsigned char setbits(unsigned char x, int p, int n, int y)
{
    unsigned char mask = ~(~0 << n) << (p - n + 1);
    return x & ~mask | y & mask;
}

マスク作りに手間取った。

ビット反転ってステキ。

演習 2-7

xの任意範囲をビット反転。

unsigned char invert(unsigned char x, int p, int n)
{
    unsigned char mask = ~(~0 << n) << (p - n + 1);
    return x & ~mask | ~x & mask;
}

2-6をクリアすれば簡単。

演習 2-8

右ビットローテート

unsigned char rightrot(unsigned char x, int n)
{
    return x >> n | x << sizeof (unsigned char) * 8 - n;
}

アセンブリ使った方がいい。

演習 2-8のインラインアセンブリで

x86アセンブラ入門20章を読みながら作った。

unsigned int ror(unsigned int x, unsigned int n)
{
    asm (
            "movl %1, %%edx;"
            "movb %2, %%cl;"
            "rorl %%cl, %%edx;"
            "movl %%edx, %0;"
            : "=m" (x) : "m" (x), "m" (n): "%edx", "%cl");
    return x;
}

(まんま載ってたのでほぼコピペ)

メモ
  • スタックからレジスタへ値をコピーしなきゃいけないのね・・・めんどい。
  • 入出力を含めた%0等は引数順。
  • レジスタ名は%%にエスケープする必要がある。
  • "m"にした%0は 8(%ebp)とかに書換えらえる。
  • 変更レジスタフィールドはコンパイラに"%edx", "%cl"を変更しました。と伝える。
  • rorにはclしか使えない。

インラインアセンブラはかなり慣れが必要らしい。修行しよう・・・。

まとめ

  • unsignedとsignedでは動作が違うので要注意。
  • ビット演算はよく使うので体に叩き込んでおこう。

(使わないって・・・)