やるしかなっちゃん

やるしかない!

この時代にK&Rを解く(3)

第2章
問題数が少ないのでサクサクと行きたい

演習2-1

各型の範囲を調べる(標準ヘッダの記号定数を使うのと自分で計算して求めるの2通りやれとのこと)
これは前回勝手に調べちゃったので簡単に計算はcharだけで

  // 標準ヘッダ
  printf("SINED_CHAR_MIN    ~ SINED_CHAR_MAX:    %d ~ %d\n", CHAR_MIN, CHAR_MAX);
  printf("UNSINED_CHAR_MIN  ~ UNSINED_CHAR_MAX:  %u ~ %u\n", 0, UCHAR_MAX);
  printf("SINED_SHORT_MIN   ~ SINED_SHORT_MAX:   %d ~ %d\n", SHRT_MIN, SHRT_MAX);
  printf("UNSINED_SHORT_MIN ~ UNSINED_SHORT_MAX: %u ~ %u\n", 0, USHRT_MAX);
  printf("SINED_INT_MIN     ~ SINED_INT_MAX:     %d ~ %d\n", INT_MIN, INT_MAX);
  printf("UNSINED_INT_MIN   ~ UNSINED_INT_MAX:   %u ~ %u\n", 0, UINT_MAX);
  printf("SINED_LONG_MIN    ~ SINED_LONG_MAX:    %ld ~ %ld\n", LONG_MIN, LONG_MAX);
  printf("UNSINED_LONG_MIN  ~ UNSINED_LONG_MAX:  %u ~ %lu\n", 0, ULONG_MAX);

  // 計算編 めんどくさいのでcharのみ
  int max = 1;
  for (int i = 0; i < sizeof(char) * 8; i++) {
    max *= 2;
  }
  printf("SINED_CHAR_MIN    ~ SINED_CHAR_MAX:  -%d ~ %d\n", max / 2, (max / 2) - 1); // 0からなので1を引く
  printf("UNSINED_CHAR_MIN  ~ UNSINED_CHAR_MAX: %d ~ %d\n", 0, max - 1); // 0からなので1を引く

演習2-2

↓のループの条件式を&&もしくは||を使わない形で等価なループにする

for (i = 0; i < limit - 1 && (c = getchar()) != '\0' && c != EOF)

これは普通に条件式どれか一つだけ残してループの中でif文書けばいいんじゃないの?

演習2-3

16進数の文字列を同値な整数値へ変換するhtoi(s)

int htoi(char s[]) {
  char buf[1024];
  int len = 0;

  if (s[0] == '0' && (s[1] == 'x' || s[1] == 'X')) {
    for (int i = 2; s[i] != '\0'; i++) {
      buf[i - 2] = s[i];
      len++;
    }
  } else {
    for (int i = 0; s[i] != '\0'; i++) {
      buf[i] = s[i];
      len++;
    }
  }

  int n = 0;
  for (int i = 0; s[i] != '\0'; i++) {
    if (buf[i] >= '0' && buf[i] <= '9')
      n += (buf[i] - '0') * (int)pow(16, len - 1 - i);
    if (buf[i] >= 'a' && buf[i] <= 'f')
      n += (buf[i] - 87)  * (int)pow(16, len - 1 - i);
    if (buf[i] >= 'A' && buf[i] <= 'F')
      n += (buf[i] - 55) * (int)pow(16, len - 1 - i);
  }

  return n;
}

最初の配列のプレフィクスを削除&長さを取得している部分がイケてないけどまぁ仕方ない

演習2-4

相変わらず問題文が難しい
文字列s1の中から文字列s2を削除しろことかな

void squeeze(char s1[], char s2[]) {
  int i, j, k;
  for (i = j = 0; s1[i] != '\0'; i++) {
    if ((s1[i] != s2[0]) && (s2[0] != '\0')) {
      s1[j++] = s1[i];
    } else {
      int tmp = i;

      for (k = 0; s2[k] != '\0'; k++)
        if (s1[i++] != s2[k]) break;

      if (s2[k] != '\0') {
        while(tmp <= i)
          s1[j++] = s1[tmp++];
      } else {
        i--;
      }
    }
  }
  s1[j] = '\0';
}

よくもまぁここまで汚いコードを書けたもんだ
でも取り敢えずこれで正しく動作はするはず
時間があったらもっと綺麗に書き直したい
まぁ要するに文字列s1に対して2つの添字を使ってコピーしていき、部分文字列が一致したらその分飛ばすし出てこなかったら飛ばさないってだけでしょ

演習2-5

文字列s2の任意の文字と等しい文字列s1の最初の文字位置を返す関数any(s1, s2) 一致しなければ-1を返す
2-4よりこっちの方が簡単じゃない? いや、2-4を解いたから簡単だと思えるのか
これが噂の伸びしろか

int any(char s1[], char s2[]) {
  int i, j, k;
  for (i = 0; s1[i] != '\0'; i++) {
    if (s1[i] == s2[0]) {
      j = i;
      for (k = 0; s2[k] != '\0'; k++)
        if (s1[j++] != s2[k]) break;
      if (s2[k] == '\0')
        return i;
    }
  }
  return -1;
}

演習2-6

位置pから始まるnビットをyの右端のnビットにセットし, 他のビットはそのままにしたxを返す関数setbits(x, p, n, y)
意味が本当にわからない この日本語でわかる人いたら名乗りでて欲しい
勝手に汲み取るとxの位置pからnビットをyの位置pからnビットの値にするってこと?

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

これで問題の意味が違ったらそれはそれで面白い

演習2-7

xのビット位置pからnビットを反転し, 他のビットはそのままのxを返す関数invert(x, p, n)

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

定番な問題も気がするけど結構な時間悩んだ
普通にXORするだけでよかったと気がついた時には自分の頭の悪さを再認識できて辛みがあった

演習2-8

右にnビット回転する関数rightrot(x, n)
回転の意味がよくわからなかったので調べたけど↓みたいなことらしい
3ビットの回転として
入力

1100 0001 0101

出力

1011 1000 0010

とういうことらしい
末尾nビットを先頭に持って行き先頭からその分スライドするみたいな感じ

unsigned int rightrot(unsigned int x, int n) {
  unsigned int buf = ~(~0 << n) & x;
  buf = buf << (32 - n);
  x = x >> n;
  x = x | buf;
  return x;
}

32ビットで考えちゃったけど問題ないかな?

演習2-9

x = x & (x - 1)の最も右の1ビットが消えるのはなぜか説明せよ
また、この事実を使ってもっと速いbitcountを書け

理由を文章で説明しても伝わる自信がないけど紙とペンを用意して実際に試してみればわかる
xとx-1の最下位ビットは必ず反対の値になる(xの最下位ビットが0のときは1だし、1の時は0)
なのでこれを&すれば必ず最下位ビットは0になる
これはおそらく誰でもわかる 問題はこの後のこの事実を用いたbitcountの実装
本気で30分ぐらい考えたけどまったくわからないのでggって解答を見てしまった
プログラムは以下のようになる

int bitcount(unsigned int x) {
  int b;
  for (b = 0; x != 0; x = x & (x - 1))
      b++;
  return b;
}

いやー、すごい こんな発想がデキる人が本物のプログラマなんだと思う
自分はこんなプログラム知識として頭に詰め込んでおかなければ絶対に書くことができない
今年の感動プログラムランキング第1位だね

うまく説明できないので実際に色々な値で試してもらえば動作の理解ができると思う
x = x & (x - 1)はxが0になるまで繰り返すとその試行回数はxの1であるビットの個数分であるという事実だけを暗記してもいいと思う
ほんとなんて説明すればいいんだろう? 動作はわかるのに全然文章化できない

演習2-10

文字を小文字に変換する関数lowerを3項演算子で書き直す

int lower(int c) {
  return c >= 'A' && c <= 'Z'? c + 'a' - 'A' : c;
}

感想

第2章終わり 問題数は少なかったけどビット演算とか出てきて少し時間はかかった
やっぱり古典的名著だけあって問題はいい問題が多い 特に2-9
ただ日本語がひどい