[←1つ前] [→1つ後] [↑質問一覧] [↑記事一覧] [ホームページ]
例えば、このような箱が32個あった場合、それぞれの箱の中に0または1のどち らが入りますから、0と1の入れ方を変えることによって表現できる(区別できる) 種類は、2の32乗、すなわち4294967296通りあります。これはまさに32ビットの符 号なし整数が0〜4295967295を表現できるという現象に対応しています。
ビットとは、このそれぞれの箱のことをいいます。従って、各ビットは0あるい は1という二通りの値のいずれかとなります。
┌─┬─┬─┬─┬─┬─┬─┬─┬〜┬─┬─┬─┬─┐
│０│１│０│１│０│１│０│１│ │０│１│０│１│
└─┴─┴─┴─┴─┴─┴─┴─┴〜┴─┴─┴─┴─┘
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 〜 ↑ ↑ ↑ ↑
それぞれが、ビット
&
」を使います。例えば、下から3番目のビットを調べたい場合には、リストのよ
うな操作を行います。1という値は一番下のビットが1ですから、この値を左に
n-1ビットシフトすれば、n番目のビットだけが1の値を得ることができます。下
から3番目のビットだけ1の数は
(1 << 2)
ですから、この値との「
&
」を求めることにより、そのビットが1か0かを判断することができます。
if (a & (1 << 2)) {
/* 下から3番目のビットが1 */
} else {
/* 下から3番目のビットが0 */
}
|
」を使います。1とのorの結果は常に1となります。そこで、目的のビットだけが
1である数とのorを求めれば、目的のビットだけを変更することができます。次の
コードは、
a
の値に対して下から7番目のビットを1に変更し、その結果を元の変数である
a
に代入します。目的のビットが最初から1の場合は、その値は変化しません。
a |= (1 << 6);あるビットだけを0にするには、0との「
&
」は0であることを利用します。1とのandの結果は、元の値が0なら0、1なら1とな
るため、値を変化しません。従って、目的のビットだけが0である数とのandを求
めれば、目的のビットだけを変更することができます。このような定数を得るた
めに、「
‾
」演算子を使います。この演算子は、対象とする値のビットを全て反転します。
すなわち、1であるビットは0に、0であるビットは1に変更します。
次のコードは、
a
の値に対して下から7番目のビットを0に変更し、その結果を元の変数である
a
に代入します。目的のビットが最初から1の場合は、その値は変化しません。
a &= ‾(1 << 6);
1
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│０│０│０│０│０│０│０│０│０│１│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
1 << 6 ：左に６つシフトする
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│０│０│０│１│０│０│０│０│０│０│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
‾(1 << 6) ：0と1を反転する
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│１│１│１│０│１│１│１│１│１│１│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
a : aの値
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│Ｊ│Ｉ│Ｈ│Ｇ│Ｆ│Ｅ│Ｄ│Ｃ│Ｂ│Ａ│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
a & ‾(1 << 6)
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│Ｊ│Ｉ│Ｈ│０│Ｆ│Ｅ│Ｄ│Ｃ│Ｂ│Ａ│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
&
」で変更したいビットを0にセットしておき、それから「
|
」を使って1にしたいビットを1にします。例えば、変数aの下位4ビット(下から数
えて1〜4番目のビット)を下からそれぞれ0、0、1、0という値にするには、
a = (a & ‾0x0f) | 0x4;
を実行します。
0x0f
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│０│０│０│０│０│０│１│１│１│１│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
‾0x0f
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│１│１│１│１│１│１│０│０│０│０│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
a : aの値
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│Ｊ│Ｉ│Ｈ│Ｇ│Ｆ│Ｅ│Ｄ│Ｃ│Ｂ│Ａ│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
a & ‾0x0f
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│Ｊ│Ｉ│Ｈ│０│Ｆ│Ｅ│０│０│０│０│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
4
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│０│０│０│０│０│０│０│１│０│０│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
(a & ‾0x0f) & 4
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│Ｊ│Ｉ│Ｈ│０│Ｆ│Ｅ│０│１│０│０│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
^
」という演算子を使って簡単に実現できます。例えば、下位2ビットだけを反転さ
せるには、次のようにします。
a ^= 3;
if ((c1 = getchar()) & (c2 = getchar()) & 0x80) {
/* EUC漢字コードの処理 */
}
(c1 = getchar())
という式の値は、
c1
の値になります。
(c2 = getchar())
の値は
c2
になります。従って、これらの値のandを計算し、さらに0x80という値とのandを
求めれば、両方の文字の8ビット目が1である場合を検出できる、と考えたのでし
ょう。この発想は悪くありません。
ところが、「
&
」という演算子は、その両辺の評価順序が不定であると決められています。従っ
て、このコードは一見
(c1 = getchar())
が先に実行されるように見えますが、実は
(c2 = getchar())
が先に実行されるかもしれないのです。そして、その場合には、この後に行われ
る漢字コードの処理で、1バイト目と2バイト目が入れ替わってしまうため、思っ
た通りの動作にならないのです。また、元の処理は
EOF
が戻ってきた場合を想定していないので、どこかでそれを検査する必要がありま
すが、とりあえず元のコードが期待した動作をするように修正するには、次のよ
うにすればよいでしょう。
c1 = getchar();
c2 = getchar();
if (c1 & c2 & 0x80) {
/* EUC漢字コードの処理 */
}
table[0] = 0;
table[1] = 1;
table[2] = 1;
:
table[254] = 7;
table[255] = 8;
これを使えば、32ビット整数aのビットが1の個数は、
table[a & 0xff] + table[(a >> 8) & 0xff] +
table[(a >> 16) & 0xff] + table[(a >> 24) & 0xff]
で求めることができます。
もう一つの、割と有名なトリッキーな方法を紹介します。
/* 与えられた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;
}
(参考: c.l.c FAQ 20.12)
右シフトの場合
┌─┬─┬─┬─┬─┬─┬─┬─┬〜┬─┬─┬─┬─┐
シフト前 │０│１│０│１│０│１│０│１│ │０│１│０│１│
└─┴─┴─┴─┴─┴─┴─┴─┴〜┴─┴─┴─┴─┘
＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼
＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ 消える
┌─┬─┬─┬─┬─┬─┬─┬─┬〜┬─┬─┬─┬─┐
シフト後 │？│０│１│０│１│０│１│０│ │１│０│１│０│
└─┴─┴─┴─┴─┴─┴─┴─┴〜┴─┴─┴─┴─┘
左シフトの場合
┌─┬─┬─┬─┬─┬─┬─┬─┬〜┬─┬─┬─┬─┐
シフト前 │０│１│０│１│０│１│０│１│ │０│１│０│１│
└─┴─┴─┴─┴─┴─┴─┴─┴〜┴─┴─┴─┴─┘
／ ／ ／ ／ ／ ／ ／ ／ ／ ／ ／ ／ ／
消える ／ ／ ／ ／ ／ ／ ／ ／ ／ ／ ／ ／
┌─┬─┬─┬─┬─┬─┬─┬─┬〜┬─┬─┬─┬─┐
シフト後 │０│１│０│１│０│１│０│ │１│０│１│０│？│
└─┴─┴─┴─┴─┴─┴─┴─┴〜┴─┴─┴─┴─┘
C言語では、左シフトの演算子として「
<<
」、右シフトの演算子として「
>>
」を用いることになっています。
このように、シフトした結果、一部のビットは外にはみでてしまうので、それら の情報は消滅することになります。逆に、シフトによってできた空きビットには、 何を入れるかということが問題になります。
C言語では、左シフトの場合、空いたビットには0を詰めることになっています。 右シフトの場合は、シフトする値が符号無し整数型の場合には、空いたビットに 0を詰めることになっています。シフトする値が符号付き整数の場合は、結果は処 理系定義となっています。すなわち、あるコンパイラは1を詰めるかもしれないし、 別のコンパイラは0を詰めるかもしれません。どちらになるかは、処理系のマニュ アルを見てください。
printf("a = %d¥n", a);
a << 3;
printf("a = %d¥n", a);
a << 3
」という式は、
a
の値を左に3つシフトさせた値を持ちますが、
a
の値そのものは変化しません。
a
の値を変えるには「
a = a << 3
」のように結果を代入するか、あるいは「
a <<= 3
」のように代入演算子とシフトを組み合わせたものを使います。
EOF
の処理があるため若干複雑だが、問題点とは無関係なので省いてある。)
c = getc(fp);
c += getc(fp) * 256;
しかし、このコードは次のようにした方が処理が速いといわれた。本当か?
c = getc(fp);
c += getc(fp) << 8;
左に1回シフトするという処理の結果は、元の値を2倍することになります。従 って、8回シフトした結果は、2の8乗倍、すなわち256倍と同じになるのです。
ということは、256を掛けるよりは、左に8シフトした方が処理が速くなるとい う結論でしょうか。残念ながら、その努力は報われない確率が極めて高いでしょ う。なぜなら、最近のコンパイラは昔に比べて随分賢くなったので、256を掛ける というコードがある場合には、もしそれを左シフトに置き換えた方が処理速度が 速いのであれば、勝手に置き換えるという程度の工夫は当然のごとく行うように なっているからです。従って、これが本当に速いコードになっているかどうかは、 コンパイルした結果を分析しなければ何とも言えません。
一般論としては、掛け算で書くべき所をわざわざシフトに書き直すのは、コー ドを分かりにくくする原因となるので、避けるべきです。
ただ、この例の場合は、整数値をファイルから1バイトずつ読み込んで組み合わ せるという処理のはずですから、むしろシフトで書いた方が意味が明確になると いう考え方もあります。悪くはありません。
&&
、
||
、
!
の3つの演算子を使った演算のことです。
ビット毎の演算子との違いは、論理演算の結果は、0か1のどちらかであるとい うことです。言いかえれば、論理演算とは、0は0、0以外の全ての値は1とみなし て1ビット整数のビット演算を行ったのと同じ結果を得ると考えてもよいでしょう。
!
」と「
‾
」はどこが違うのか。
!
」は、論理演算子の否定とされています。すなわち、その結果は0か1のどちらか
となります。「
‾
」はビット毎に反転を行います。結果は元の値の0と1を全て逆転させたものとな
ります。例えば、１に対するそれぞれの演算子を反映させた結果は図の通りで、
違いは一目瞭然です。
1
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│０│０│０│０│０│０│０│０│０│１│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
!1
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│０│０│０│０│０│０│０│０│０│０│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
‾1
〜┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│１│１│１│１│１│１│１│１│１│０│
〜┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
if (((c1 = getchar()) >= 0x80) && ((c2 = getchar()) >= 0x80)) {
/* EUC漢字コードの処理 */
}
従って、このコードの場合は、
&&
の左側にある
((c1 = getchar()) > 0x80)
という式がまず評価されることが間違いないため、
c1
と
c2
は期待した順序の値が入ることになります。
(参考) 【&&や||と副作用完了点】