LoginSignup
0
0

More than 5 years have passed since last update.

@7of9

C > bit演算 > 20bitの数値から任意の開始、終了位置の値を読取る

Last updated at Posted at 2017-07-26
動作環境
C

仕様

  • 20bitの数値がある
  • MSBのインデックスを0とする
    • LSBはインデックスは19となる
  • 開始,終了のインデックスを与えた時、その部分の値を取得したい

v0.1

  • 終了位置まで右シフトする
  • ビット数で&演算をする

#include <stdio.h>

#define OUT_OF_RANGE (-1)
#define MAX_BITS (20)

int getBitFilled(int bitnum)
{
    bitnum--;
    return ((2 << bitnum)-1);
}

int extractBits(int start, int end, int bit20val)
{
    if (start < 0 || end > MAX_BITS) {
        return OUT_OF_RANGE; // error
    }
    int work = bit20val;
    int numbit = (end - start + 1);
    if (end > 0) {
        work >>= (20 - end - 1);
    }
    return work & getBitFilled(numbit);
}

void Test_extractBits(int start, int end, int bit20val)
{
    int res = extractBits(start, end, bit20val);
    printf("%d\n", res);
}

int main(void) {
    int res;

    Test_extractBits(18, 19, /*bit20val=*/0b11);   // 3
    Test_extractBits(17, 18, /*bit20val=*/0b1011); // 1
    Test_extractBits(16, 17, /*bit20val=*/0b1011); // 2
    Test_extractBits(0, 4, /*bit20val=*/(2<<15));  // 2
    return 0;
}
run
3
1
2
2

Windowsの電卓で確認したところ、大きく間違えてはいないよう。

テストが網羅されていないが、とりあえず。

v0.2

(追記 2017/07/27)

  • getBitfilled()の処理を訂正
  • OUT_OF_RANGE判定の間違い訂正 (MAX_BITS関連)

#include <stdio.h>

#define OUT_OF_RANGE (-1)
#define MAX_BITS (20)

int getBitFilled(int bitnum)
{
    return ((1 << bitnum)-1);
}

int extractBits(int start, int end, int bit20val)
{
    if (start < 0 || end >= MAX_BITS) {
        return OUT_OF_RANGE; // error
    }
    int work = bit20val;
    int numbit = (end - start + 1);
    if (end > 0) {
        work >>= (20 - end - 1);
    }
    return work & getBitFilled(numbit);
}

void Test_extractBits(int start, int end, int bit20val)
{
    int res = extractBits(start, end, bit20val);
    printf("%d\n", res);
}

int main(void) {
    int res;

    Test_extractBits(18, 19, /*bit20val=*/0b11);   // 3
    Test_extractBits(17, 18, /*bit20val=*/0b1011); // 1
    Test_extractBits(16, 17, /*bit20val=*/0b1011); // 2
    Test_extractBits(0, 4, /*bit20val=*/(2<<15));  // 2
    return 0;
}

テストはまだ足りない。

v0.3

  • print_binary()追加
  • assert()追加
  • テストを増やした
  • end=-1の場合、LSBまで読むように変更

Tool: テストデータ(748118)は http://calc.50x.eu/ にてランダムにビットをON/OFFして作成

#include <stdio.h>
#include <assert.h>

#define OUT_OF_RANGE (-1)
#define MAX_BITS (20)

void print_binary(int number, int num_digits) {
    int digit;
    for(digit = num_digits - 1; digit >= 0; digit--) {
        putchar(number & (1 << digit) ? '1' : '0');
        if (digit > 0 && digit % 4 == 0)
            putchar(' ');
    }
}

int getBitFilled(int bitnum)
{
    return ((1 << bitnum)-1);
}

int extractBits(int start, int end, int bit20val)
{
    if (start < 0 || end >= MAX_BITS) {
        return OUT_OF_RANGE; // error
    }
    int work = bit20val;
    int numbit;
    if (end >= 0) {
        numbit = (end - start + 1);
    } else {
        numbit = (MAX_BITS - start + 1);        
    }
    if (end > 0) {
        work >>= (20 - end - 1);
    }
    return work & getBitFilled(numbit);
}

void Test_extractBits(int start, int end, int bit20val, int answer)
{
    int res = extractBits(start, end, bit20val);
    printf("%7d:", res);
    print_binary(res, 20);
    printf("\n");
    assert(res == answer);
}

int main(void) {
    int res;

    //            (start, end, bit20val, answer)
    Test_extractBits(18, 19, 0b11, 3);
    Test_extractBits(17, 18, 0b1011, 1);
    Test_extractBits(16, 17, 0b1011, 2);
    Test_extractBits( 0,  4, (2<<15), 2);
    printf("\n");
    Test_extractBits(-1,  4, (2<<15), -1); // (OUT_OF_RANGE)
    Test_extractBits( 0, 20, (2<<15), -1); // (OUT_OF_RANGE)
    printf("\n");
    //             0123 4567 8901 2345 6789
    // 748118: (0b 1011 0110 1010 0101 0110)
    Test_extractBits( 0,  2, 748118, 5); // 0b101
    Test_extractBits( 3,  8, 748118, 45); // 0b101101
    Test_extractBits( 9, 15, 748118, 37); // 0b0100101
    Test_extractBits( 16, 19, 748118, 6); // 0b0110
    printf("\n");
    Test_extractBits( 0, -1, 748118, 748118);
    Test_extractBits(17, -1, 748118, 6); // 0b110
    return 0;
}
run
      3:0000 0000 0000 0000 0011
      1:0000 0000 0000 0000 0001
      2:0000 0000 0000 0000 0010
      2:0000 0000 0000 0000 0010

     -1:1111 1111 1111 1111 1111
     -1:1111 1111 1111 1111 1111

      5:0000 0000 0000 0000 0101
     45:0000 0000 0000 0010 1101
     37:0000 0000 0000 0010 0101
      6:0000 0000 0000 0000 0110

 748118:1011 0110 1010 0101 0110
      6:0000 0000 0000 0000 0110

用意したテストは全assertを通った。

20bitを超える値がbit20valに入った場合は、&演算で最大20bitまでしか扱われないので、特に対処していない。

v0.4 > 修正

  • fix bug > extractBits()においてend=-1の時のnumbit計算が間違い
  • テストを変更した

#include <stdio.h>
#include <assert.h>

#define OUT_OF_RANGE (-1)
#define MAX_BITS (20)

void print_binary(int number, int num_digits) {
    int digit;
    for(digit = num_digits - 1; digit >= 0; digit--) {
        putchar(number & (1 << digit) ? '1' : '0');
        if (digit > 0 && digit % 4 == 0)
            putchar(' ');
    }
}

int getBitFilled(int bitnum)
{
    return ((1 << bitnum)-1);
}

int extractBits(int start, int end, int bit20val)
{
    if (start < 0 || end >= MAX_BITS) {
        return OUT_OF_RANGE; // error
    }
    int work = bit20val;
    int numbit;
    if (end >= 0) {
        numbit = (end - start + 1);
    } else {
        numbit = (MAX_BITS - start); // fix     
    }
    if (end > 0) {
        work >>= (20 - end - 1);
    }
    return work & getBitFilled(numbit);
}

void Test_extractBits(int start, int end, int bit20val, int answer)
{
    int res = extractBits(start, end, bit20val);
    printf("%7d:", res);
    print_binary(res, 20);
    printf("\n");
    assert(res == answer);
}

int main(void) {
    int res;

    //              0123 4567 8901 2345 6789
    // 1048575: (0b 1111 1111 1111 1111 1111)
    //            (start, end, bit20val, answer)
    // 1. out of range case
    Test_extractBits(-1,  4, 1048575, -1); // (OUT_OF_RANGE)
    Test_extractBits( 0, 20, 1048575, -1); // (OUT_OF_RANGE)
    printf("\n");
    // 2. in range case
    Test_extractBits( 0,   2, 1048575, getBitFilled(3));
    Test_extractBits( 3,   10, 1048575, getBitFilled(8));
    Test_extractBits( 11,   19, 1048575, getBitFilled(9));
    Test_extractBits( 0,   19, 1048575, getBitFilled(20));
    printf("\n");
    // 3. end=-1 case
    Test_extractBits( 0,  -1, 1048575, getBitFilled(20));
    Test_extractBits( 17, -1, 1048575, getBitFilled(3));

    //              0123 4567 8901 2345 6789
    //  986895: (0b 1111 0000 1111 0000 1111)
    // 4. in range case
    Test_extractBits( 0,  4, 986895, getBitFilled(4) << 1);
    Test_extractBits( 3,  8, 986895, 0b100001);
    Test_extractBits( 9, 17, 986895, 0b111000011);
    return 0;
}
run
     -1:1111 1111 1111 1111 1111
     -1:1111 1111 1111 1111 1111

      7:0000 0000 0000 0000 0111
    255:0000 0000 0000 1111 1111
    511:0000 0000 0001 1111 1111
1048575:1111 1111 1111 1111 1111

1048575:1111 1111 1111 1111 1111
      7:0000 0000 0000 0000 0111
     30:0000 0000 0000 0001 1110
     33:0000 0000 0000 0010 0001
    451:0000 0000 0001 1100 0011
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0