Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
初級C言語Q&A(15)
[go: Go Back, main page]

初級C言語Q&A(15)

初出: C MAGAZINE 1996年8月号
Updated: 1996-09-21

[←1つ前] [→1つ後] [↑質問一覧] [↑記事一覧] [ホームページ]

　今回は、よく知られているけどちょっと分かりにくいアルゴリズム、あるいは、 今までの連載で出てきたトリッキーなコードについて、どのような原理で動作す るのかを紹介してみようと思います。ただし、一般論として、凝ったコードより も分かりやすいコードの方が価値がある場合が多いということも頭に入れておい てください。

凝ったアルゴリズム

Ｑ　【曜日の求め方】

　Comp.lang.c FAQ listを見ると、曜日を求める関数として次のものが紹介され ていた。 
        dayofweek(y, m, d)  /* 0 = Sunday */
        int y, m, d;        /* 1 <= m <= 12, y > 1752 or so */
        {
            static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
            y -= m < 3;
            return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
        }
　なぜこれで曜日が得られるのか?

Ａ

ある年の1月1日が0曜日であるとします。一年を365日で計算すれば、その翌年 の1月1日は、(365 = 7*52 + 1)なので1曜日です。従って、単純に考えれば、1月 1日の曜日は、1年ごとに1ずつずれていくので、定数をCとして、次のコードで計 算できるはずです。 
    (y + C) % 7;
　しかし、4年に一度の割合でうるう年があるために曜日がさらに2つずれること になります。うるう年は4で割りきれる年に発生しますから、4で割りきれる年毎 に1増えるような式を追加すれば修正することができます。このような式は簡単で、 正整数の割り算で割りきれない時に余りが切り捨てられることを利用すれば、y/ 4を追加すれば目的通りの結果が得られることがわかります。この補正を追加する と、次のようになります。 
    (y + y/4 + C) % 7;
　もう少し細かいことを考えれば、うるう年の例外年というものがあります。100 で割りきれる年はうるう年に数えません。ただし、400で割りきれる年はうるう年 です。これらの処理も追加すれば次のようになります。 
    (y + y/4 - y/100 + y/400 +  C) % 7;
　次に、この処理をy年m月1日の曜日を求めるように拡張しましょう。これも同様 に考えれば、1月1日が0曜日なら、2月1日は3曜日、のような差を表として作成し ておき、それを追加すればよさそうです。 　しかし、ここで問題になるのは2月末の処理です。2月だけは、うるう年と、そ うでない年によって、一か月の長さが変化します。このため、2月1日が3曜日の場 合、3月1日が何曜日になるかは2通りの結果があることになってしまいます。幸い、 このような現象は2月末にしか発生しません。そこで、毎月の曜日の差の表の基準 を3月にしますと、その年の12月までは一意的なテーブルを持つことができます。 そして、翌年の1、2月は、前年の3月からの差で表現することにします。こうすれ ば、2月末の曖昧さは表に含めずに済み、2月末の処理を避けることができます。 3月1日が0曜日の時の、各月の1日の曜日表は、次のようになります。ただし、t [m-1]がm月を表します。 
  int t[] = {5, 1, 0, 3, 5, 1, 3, 6, 2, 4, 0, 2};
mが1と2の場合には前年の基準から数えるので、yを減算する必要があります。C言 語の大小比較の式が0か1という値を持つことを利用すれば、この処理は次のコー ドで実現できます。 
  y -= m < 3;
　もっとも、ここは次のように書いてもいいでしょう。 
  if (m < 3)
    y--;
　このテーブルを使って、y年m月1日の曜日を求めるコードは次のようになります。 
  int t[] = {5, 1, 0, 3, 5, 1, 3, 6, 2, 4, 0, 2};
  y -= m < 3;
  (y + y/4 - y/100 + y/400 + t[m-1] + C) % 7;
y年m月d日の場合は、定数から1を減らして、日付を加えればOKです。 
  (y + y/4 - y/100 + y/400 + t[m-1] + d + C1) % 7;
　さて、この定数の値は、実際の曜日を当てはめると2になることが分かります。 しかし、最初から表の値に2を加えておけば、いちいち加算する必要がなくなるの で、少しだけ効率的になります。このように修正した表の値は次のようになりま す。 
  int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
　これでComp.lang.c FAQ listに紹介されたプログラムの通りになりました。 　m-1という計算も毎回行うことが気になりますか? テーブルの先頭にダミーの 0という値を追加する方法もあります。ついでに、ANSI Cのスタイルで書いて、if 文に置き換えてみます。 
/* 0 = Sunday, 1 <= m <= 12, y > 1752 */
int dayofweek(int y, int m, int d)
{
    static int t[] = {0, 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};

    if (m < 3)
        y--;
    return (y + y/4 - y/100 + y/400 + t[m] + d) % 7;
}
tはstaticにしておかないと、関数呼び出しの度にメモリの初期化が発生します ので、効率が悪くなってしまいます。 * 　なお、このアルゴリズムは割と有名なものです。数学でよく知られている式は、 
    (y + [y / 4] - [y / 100] + [y / 400] + [2.6m + 1.6] + d) mod 7
　というもので、ここで[]は、小数部を捨てることを意味します。この場合も、 1月と2月は前年の13月、14月として計算しています。 
int dayofweek(int y, int m, int d)
{
    if (m < 3) {
        y--;
        m += 12;
    }
    return (y + y/4 - y/100 + y/400 + (26*m+16)/10 + d) % 7;
}

Ｑ　【ビットの数え方】

　次の関数は、なぜビットを数えることができるのか。 
/* 与えられたintの中の1であるビットの数を返す。
 * 最上位2ビットは利用できない
 */
int numofbits(int bits)
{
    int num;

    num = (bits >> 1) & 03333333333;
    num = bits - num - ((num >> 1) & 03333333333);
    num = ((num + (num >> 3)) & 0707070707) % 077;
    return num;
}

Ａ

　話を簡単にするために、まず、3ビットの整数を考えてみましょう。 
  +----+----+----+
  |bit2|bit1|bit0|  --- (1)
  +----+----+----+
　これを1つ右にシフトすると、次の図のような状態になります。 
  +----+----+----+
  | ?? |bit2|bit1|
  +----+----+----+
??の部分には何が入るか分からないと考えておきます。しかし、03との&を取れ ば、??のビットは0になります。 
  +----+----+----+
  |  0 |bit2|bit1|  --- (2)
  +----+----+----+
　これをさらに1つ右にシフトします。 
  +----+----+----+
  | ?? |  0 |bit2|
  +----+----+----+
　同様に03とのandを取ります。 
  +----+----+----+
  |  0 |  0 |bit2|  --- (3)
  +----+----+----+
　さて、(1)、(2)、(3)をそれぞれ3ビットの整数とみなして、その値を使って計 算します。(1) - (2) - (3) は、どのような値になるでしょうか。 
  (1) : bit2 * 4 + bit1 * 2 + bit0
  (2) : bit2 * 2 + bit1
  (3) : bit2
　という値なので、 
  (bit2 * 4 + bit1 * 2 + bit0) - (bit2 * 2 + bit1) - bit2 = bit2 + bit1 + bit0
　という結果になります。つまり、(1) - (2) - (3) によって、この3ビットの中 に1のビットがいくつあるかを計算したことになります。 　この結果が常に0から3の範囲の値となることに注目しながら、次に、6ビットの 整数で同様の処理を行うとどうなるか考えてみます。 
  +----+----+----+----+----+----+
  |bit5|bit4|bit3|bit2|bit1|bit0|  --- (1)
  +----+----+----+----+----+----+

  1つ右にシフトする
  +----+----+----+----+----+----+
  | ?? |bit5|bit4|bit3|bit2|bit1|
  +----+----+----+----+----+----+

  033とのandを取る。
  +----+----+----+----+----+----+
  |  0 |bit5|bit4|  0 |bit2|bit1|  --- (2)
  +----+----+----+----+----+----+

　これをさらに1つ右にシフトする。
  +----+----+----+----+----+----+
  | ?? |  0 |bit5|bit4|  0 |bit2|
  +----+----+----+----+----+----+

  033とのandを取る。
  +----+----+----+----+----+----+
  |  0 |  0 |bit5|  0 |  0 |bit2|  --- (3)
  +----+----+----+----+----+----+
(1) - (2) - (3) を計算すると、次のような結果になります。 
  +----+----+----+----+----+----+
  |bit5+bit4+bit3|bit2+bit1+bit0|
  +----+----+----+----+----+----+
　3ビットずつ区切ったブロックの中では、計算が完結しており、左右のブロック に影響を与えることがありません。つまり、繰り下がりが発生しないのです。32 ビットに拡張すると、上位の2ビットを除くすべてのビットに同様の処理が行われ、 3ビットずつのブロックに、そこにあった1のビットの数が数値として置き換わっ た状態になります。 　次に、 
    num + (num >> 3)
　を考えてみましょう。今までの操作で、下位から3ビットずつ区切ったブロック には、それぞれ、そこに元々あったビット数を表す値に置き換わっています。そ の結果が0〜3の範囲に入っていることに注目しましょう。numを3つ右にシフトし たものを加算すると、3ビットのブロック毎に、すでに求めたビット数を加算する ことになり、その結果、3ビットのブロックの値は、6ビットずつのブロックに含 まれているビット数となります。この数は0〜6の範囲に収まりますから、2進数で 表現すれば0〜110の範囲、つまり、やはり3ビットで表現できることになります。 つまり、足し算の結果は、3ビットで区切ったブロックで考えれば、隣のブロック に影響しない、言いかえれば、ブロック単位でオーバーフローは発生しないこと が分かります。 
  num
  +----+----+----+----+----+----+----+----+----+
  |bit8+bit7+bit6|bit5+bit4+bit3|bit2+bit1+bit0|
  +----+----+----+----+----+----+----+----+----+

  num >> 3
  +----+----+----+----+----+----+----+----+----+
  .....          |bit8+bit7+bit6|bit5+bit4+bit3|
  +----+----+----+----+----+----+----+----+----+

  num + (num >> 3)
  +----+----+----+----+----+----+----+----+----+
  |bit11+ ..+bit6|bit8+ .. +bit3|bit5+ .. +bit0|
  +----+----+----+----+----+----+----+----+----+
　この結果、下から6ビットずつ区切ったブロックは、それぞれbit5〜bit0、bit8 〜bit3、bit11〜bit6、…という値になります。これ中から、元にあったビットを 二度数えているブロックを取り除くために、0707070707でandをとってやります。 
    ((num + (num >> 3)) & 0707070707)
  +----+----+----+----+----+----+----+----+----+
  |bit11+ ..+bit6|       0      |bit5+ .. +bit0|
  +----+----+----+----+----+----+----+----+----+
　最後の仕上げは077による余りの計算です。これは剰余の演算の性質を使ってい ます。10進数の場合、3や9で割った余りを求める速算法として、各桁の数を足し 算して3や9で割る、という有名なテクニックがあります。 077 + 001 == 2^6 であることに注目します。 　現在の計算結果は、 
　bit29〜24 * 2^24 + bit23〜18 * 2^18 + bit17〜12 * 2^12 + bit11〜6 * 2^6 + bit5〜0
　という値になっています。例えば、2^24は、2^6 * 2^6 * 2^6 * 2^6ですから、 
  bit29〜24 * (077 + 001) * (077 + 001) * (077 + 001) * (077 + 001)
　となります。これを077で割れば、077で掛け算した項はごっそり抜け落ちて、 bit29〜24の値だけが残ります。同様に他のブロックも077で割った余りで加算す ることによって、bit29〜0を数えた値を077で割った余りと等しい値になることが 分かります。 　ところで、077というのは63ですから、077で割った余りというのは0〜62の範囲 の値になるはずです。もともと、ビットの数は0〜32の範囲の値なので、結局077 で割った余りというのは1であるビットの数そのものであることになります。 (参考: c.l.c FAQ 20.12)

Ｑ　【ビットの数え方】

　では、次の関数は、なぜビットを数えることができるのか。 
int numofbits(long bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

Ａ

　まず、2ビットの場合に単純化して考えてみましょう。2ビットの整数の中のビ ット数をテーブルを使わないで計算します。 
  +----+----+
  |bit1|bit0|
  +----+----+
bit1が1か0、bit0が1か0であると考えれば、bit1の値とbit0の値を加算すれば、 1であるビット数を求めることができます。しかし、そのままでは桁がずれてしま うので加算できません。そこで、シフトを使って桁をそろえます。 
  +----+----+              +----+----+
  |bit1|bit0|  & 1 -->     |  0 |bit0|
  +----+----+              +----+----+

  +----+----+              +----+----+
  |bit1|bit0| >> 1 & 1 --> |  0 |bit1|
  +----+----+              +----+----+
                     +)
                   ------------------------
                         (bit0 + bit1)
　次に、4ビットの場合を考えてみましょう。まず、隣り合う2ビットを同様に計 算してみます。 
  +----+----+----+----+                +----+----+----+----+
  |bit3|bit2|bit1|bit0|   & 0101  -->  |  0 |bit2|  0 |bit0|
  +----+----+----+----+                +----+----+----+----+

  +----+----+----+----+                +----+----+----+----+
  |bit3|bit2|bit1|bit0| >> 1 & 0101--> |  0 |bit3|  0 |bit1|
  +----+----+----+----+                +----+----+----+----+
                                   +)
                                  --------------------------
                                       +---------+---------+
                                       |bit3+bit2|bit1+bit0|
                                       +---------+---------+
　図のように、上の2ビットにはbit3+bit2の結果が、下の2ビットにはbit1+bit0 の結果が入ることになります。さて、さらにこの二つの値を加算するには、2つシ フトして桁をそろえてみます。 
  +----+----+----+----+                +----+----+----+----+
  |bit3+bit2|bit1+bit0|   & 0011  -->  |    0    |bit1+bit0|
  +----+----+----+----+                +----+----+----+----+

  +----+----+----+----+                +----+----+----+----+
  |bit3+bit2|bit1+bit0| >> 2 & 0011--> |    0    |bit3+bit2|
  +----+----+----+----+                +----+----+----+----+
                                   +)
                                  --------------------------
                                       +-------------------+
                                       |bit3+bit2+bit1+bit0|
                                       +-------------------+
　このように、bit3からbit0までの各ビットの値(すなわち1か0)を加算した結果 が、この4ビットの位置に入ることが分かります。 　同様のことを8ビット、16ビット、32ビット、に対して行ったのが、最初のコー ドですから、結果としてビットを数えた値が得られることになります。 　ところで、3行目の次のコードを実行した所で、 
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
　bitsの32ビットは4つのブロックに分かれて、それぞれ次の値が入っています。 
  +----------------+----------------+---------------+---------------+
  | bit31+..+bit24 | bit23+..+bit16 |bit15+..+bit8  |bit7 +..+bit0  |
  +----------------+----------------+---------------+---------------+
          a                 b               c               d
　a〜dは、それぞれ8ビット中の1であるビットの数てすから、たかだか8ですね。 ここで、aの部分に注目すると、値がたかだか8(2進数では00001000)なので、一番 上のビットが常に0となり、すなわち、bitsの値が正となることが確定します。ANSI Cの仕様では、符号付き整数の値が負の場合には右シフトした場合の結果は処理系 定義となっていますが、符号付き整数xが正の値のときには、右にyシフトした場 合には、xを2^yで割った結果に等しいとなっています。従って、上位のビットに は0が入ることになり、bitsを8ビット右にシフトすると、一番左のブロックの8ビ ットはすべて0で埋まります。 
  bits
  +----------------+----------------+---------------+---------------+
  | bit31+..+bit24 | bit23+..+bit16 |bit15+..+bit8  |bit7 +..+bit0  |
  +----------------+----------------+---------------+---------------+

  bits >> 8
  +----------------+----------------+----------------+---------------+
  |      0         | bit31+..+bit24 | bit23+..+bit16 |bit15+..+bit8  |
  +----------------+----------------+---------------+----------------+
　この両者に対して、andを取らずに足し算をしても、結果は各ブロックに対して たかだか16ですから、隣のブロックには影響がなく、そのブロックの中だけで値 が収まることになります。そして、その値はたかだか16となります。加算した結 果は、次のようになります。 
   bits += bits >> 8;
  +----------------+----------------+---------------+---------------+
  | bit31+..+bit24 | bit31+..+bit16 |bit23+..+bit8  |bit15+..+bit0  |
  +----------------+----------------+---------------+---------------+
　同様にして、さらに16シフトしたものも足すと、次のようになります。これも、 足した結果は32以下ですから、隣のブロックには影響がありません。 
  +----------------+----------------+---------------+---------------+
  | bit31+..+bit24 | bit31+..+bit16 |bit31+..+bit8  |bit31+..+bit0  |
  +----------------+----------------+---------------+---------------+
　これらの工夫で少し効率を良くしたコードは次のようになります。 
    int numofbits(long bits)
    {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (((bits >> 4) + bits) & 0x0f0f0f0f;
        bits += bits >> 8;
        return (bits + (bits >> 16)) & 0xff;
    }
　※質問中に出てくる方法は、サイエンス社の「システムプログラムの実際」(島 内剛一著)に出ているとの情報を坂本智彦様より紹介していただきました。回答中 の、効率を良くしたコードは同氏によるものです。興味のある方は、その他のア ルゴリズムも含めて、fjニュースグループ次の投稿が参考になります。 
  Newsgroups: fj.lang.c
  Message-ID: <4nppj5$dml@csdnews.sm.sony.co.jp>
  From: sakamoto@sm.sony.co.jp (Tomohiko Sakamoto)
  Subject: bit count
※1998年現在、fj.lang.cはfc.comp.lang.cに名称変更されています。

Ｑ　【シフトJISの1バイト目の判定】

　次のマクロは、なぜシフトJISの1バイト目であることを判定できるのか? 
#define is_kanji1st(c) ((unsigned int) (c ^ 0x20) - 0xa1 < 0x3c)

Ａ

cがunsignedである場合に、よく使われるマクロは次のようなものです。 
    (c >= 0x81 && c <= 0x9f) || (c >= 0xe0 && c <= 0xfc)
　なお、これを次のようにした方が、無駄な比較が少なくなると、以前コラムで 紹介しています。(Cマガジン、フィンローダのあっぱれご意見番 1995-09) 
    (c >= 0x81 && (c <= 0x9f || (c >= 0xe0 && c <= 0xfc))
　ところで、このようなcの範囲を図にすると次のようになります。 
  (cの範囲)

    　０１２３４５６７８９ＡＢＣＤＥＦ(×0x10)
    ０□□□□□□□□□■□□□□■■
    １□□□□□□□□■■□□□□■■
    ２□□□□□□□□■■□□□□■■
    ３□□□□□□□□■■□□□□■■
    ４□□□□□□□□■■□□□□■■
    ５□□□□□□□□■■□□□□■■
    ６□□□□□□□□■■□□□□■■
    ７□□□□□□□□■■□□□□■■
    ８□□□□□□□□■■□□□□■■
    ９□□□□□□□□■■□□□□■■
    Ａ□□□□□□□□■■□□□□■■
    Ｂ□□□□□□□□■■□□□□■■
    Ｃ□□□□□□□□■■□□□□■■
    Ｄ□□□□□□□□■■□□□□■□
    Ｅ□□□□□□□□■■□□□□■□
    Ｆ□□□□□□□□■■□□□□■□
　これに対して、0x20でxorを実行すると、次の範囲の文字が入れ替わります。 
    0x00〜0x1F ←→ 0x20〜0x3F
    0x40〜0x5F ←→ 0x60〜0x7F
    0x80〜0x9F ←→ 0xA0〜0xBF
    0xC0〜0xDF ←→ 0xE0〜0xFF
　例えば、0x00^0x20は0x20だし、0x20^0x00は0x00、となります。これによって 文字コードは入れ替わりますが、一対一の対応になっているため、情報が失われ ることはありません。この交換の結果、漢字1バイト目の文字は次の位置になりま す。 
    　０１２３４５６７８９ＡＢＣＤＥＦ
    ０□□□□□□□□□□□■■■□□
    １□□□□□□□□□□■■■■□□
    ２□□□□□□□□□□■■■■□□
    ３□□□□□□□□□□■■■■□□
    ４□□□□□□□□□□■■■■□□
    ５□□□□□□□□□□■■■■□□
    ６□□□□□□□□□□■■■■□□
    ７□□□□□□□□□□■■■■□□
    ８□□□□□□□□□□■■■■□□
    ９□□□□□□□□□□■■■■□□
    Ａ□□□□□□□□□□■■■■□□
    Ｂ□□□□□□□□□□■■■■□□
    Ｃ□□□□□□□□□□■■■■□□
    Ｄ□□□□□□□□□□■■■□□□
    Ｅ□□□□□□□□□□■■■□□□
    Ｆ□□□□□□□□□□■■■□□□
　この結果、検査する文字が連続した一つの範囲になります。図をみればわかる ように、xorした結果が0xa1から0xdcの範囲になっていればOKです。このためには 2回の比較が必要なのですが、この値から、さらに0xa1を引き算すると、比較対象 のコードは図のような範囲に収まることになります。 
    　０１２３４５６７８９ＡＢＣＤＥＦ
    ０■■■■□□□□□□□□□□□□
    １■■■■□□□□□□□□□□□□
    ２■■■■□□□□□□□□□□□□
    ３■■■■□□□□□□□□□□□□
    ４■■■■□□□□□□□□□□□□
    ５■■■■□□□□□□□□□□□□
    ６■■■■□□□□□□□□□□□□
    ７■■■■□□□□□□□□□□□□
    ８■■■■□□□□□□□□□□□□
    ９■■■■□□□□□□□□□□□□
    Ａ■■■■□□□□□□□□□□□□
    Ｂ■■■■□□□□□□□□□□□□
    Ｃ■■■□□□□□□□□□□□□□
    Ｄ■■■□□□□□□□□□□□□□
    Ｅ■■■□□□□□□□□□□□□□
    Ｆ■■■□□□□□□□□□□□□□
　この場合、符号なしの整数に関する演算が剰余法則に従うことを利用していま す。つまり、引き算の前に0〜0xa0だった数は、符号付きの演算であるなら-0xa1 〜-1という値になるのですが、符号なしの整数として演算すると、非常に大きな 正の数になるはずです。 　最終的に変換した範囲の値に含まれているかどうかを調べるのは、0x3cという 値より小さいかどうかで分かります。これで最初に紹介したコードの意味です。 
※ c.l.c FAQ : comp.lang.c FAQ list

http://www.eskimo.com/~scs/C-faq.top.html
文中の項目番号は新しい版に対応しています。旧版とは異なります。
(C) 1996, 1998 Phinloda, All rights reserved
無断でこのページへのリンクを貼ることを承諾します。問い合わせは不要です
内容は予告なく変更することがあります。