月別アーカイブ: 2014年11月

2014/11/29 までの週間PV数の推移(2)

temp

 

上図は、最近作成したページの週間PV数の推移グラグ。
作ってから8週間~12週間はたたないと、PV数を稼げるかどうかは判明しないので、単なる参考情報だ。

ちなみに、各ページのここ1周間の平均検索掲載順位は以下のとおり(括弧内は先週の順位)。

list: 11位(14位)
map: 15位(18位)
static: 26位(25位)
プログラミング入門: 9.4位(3.1位)

list と map は徐々に順位が上がってるっぽいが、static は下位低迷だ orz

 

ビット演算>xor(排他的論理和)を用いたビットの交換(2)

前稿 では、異なる変数の同じ位置のビットを交換したが、ひとつの変数内のビットを交換することも出来るぞ。
下記は、変数 x の下位4ビット(bit0~bit3)とその上4ビット(bit4~bit7)を交換するコードだ。

x = 何らかの値;
int t = (x ^ (x >> 4)) & 0xf;    //  x の下位4ビットとその上4ビットの xor を計算
t |= t << 4;    //  xor 値を bit4~bit7 にもコピー
x ^= t;    // xor を取ることでビットを交換

論理演算の回数はわずか6回だ。
どうだい、こんな簡潔なコードでビットの交換ができるなんて感激しないか?

 演習問題:

  1. 上記コードをビルド・デバッガで実行し、ビットが交換されていることを確認しなさい。
  2. 論理積と論理和を使って上記と同じコードを書いてみなさい。
  3. 変数x の bit4~bit7 と bit12~bit15 を交換(x = 0x1234; ならば x = 0x3214 となる)するコードを書きなさい。

ビット演算>xor(排他的論理和)を用いたビットの交換

前稿 で、and, or を用いたビット交換方法を示したが、xor を用いると、より簡潔に書けるぞ。

int x = 何らかの値;
int y = 何らかの値;
const int t = (x ^ y) & 0xf;   //  x と y の下位8ビットの xor
x ^= t;    //  下位8ビットが x^(x^y) = y になる
y ^= t;    //  下位8ビットが y^(x^y) = x になる

どうだろう?ご理解いただけるであろうか?
前稿の方法と比べて、非常に簡潔になったでしょ。

交換したい部分の xor(排他的論理和)をとり、それを元の変数に xor することで、ビットを交換できるということだ。

筆者がはじめてこのテクニックを見たときはかなりびっくりした。言われてみればあたりまえなのだが、ビットを交換するときに方法が思いつかず、前稿の方法を使っていたからだ。

演習問題:

  1. 上記コードをビルド・デバッガで実行し、正しく交換されることを確認しなさい。

ビット演算>and(論理積), or(論理和)を用いたビットの交換

int x, int y に何らかの値が入っている時、下位8ビットの値を交換するコードは以下のように記述することが出来る。

int x = 何らかの値;
int y = 何らかの値;
const int mask = 0xf;    // 交換する部分のマスク
int tx = x & mask;    // x の下位8ビットを取り出す → tx に保存
int ty = y & mask;    // y の下位8ビットを取り出す → ty に保存
x &= ~mask;    // x の下位8ビットを0に
x |= ty;    // x の下位8ビットを y の下位8ビットの値にする
y &= ~mask;    // y の下位8ビットを0に
y |= tx;    // y の下位8ビットを x の下位8ビットの値にする

これまでに説明した、論理積・論理和のテクニックを使用している。ご理解いただけるであろうか?
よくわからない人はこれまでの解説を是非読み返して欲しい。

演習問題:

  1. 上記コードをビルドし、デバッガで動きを確認しなさい。

2014/11/29 までの週間PV数の推移:vector バブル崩壊か!?

下図は、5月中旬から11/29 までの各C++解説ページの週間PV数の推移と、指数関数回帰による将来のPV数予測だ。

temp

指数関数回帰+祭日補選による PV数予測は、vector: 1660, string:1057 だったのだが、実際は 1364, 907 と散々な結果であった。

あと2週間くらいは様子をみないとなんとも言えないが、これは vector バブル崩壊か!?

ちなみに、この週の各ページの平均検索順位は以下のとおり

vector: 7.0 (-0.1)
string: 6.6 (±0)
measure: 4.9 (+0.2)
random: 7.8 (+0.1)

 

指数関数的増加が年末までは続いて、3000PV/週程度になることを密かに期待していたのだが・・・

ビット演算>xor(排他的論理和)を使った値の交換

ここまでは基礎編だったが、ここからは中級編だ。少し難しくなるかもしれない。
が、マスターすれば便利な機能なので、ぜひマスターしてワンランク上のビット演算氏になってもらいたい。

排他的論理和 のところで一応説明したのだが、もう一度書いておくと、排他的論理和には以下の様な性質がある。

  • x ^ 0 = 0 ^ x = x   // 0 との排他的論理和は値を変えない
  • x ^ x = 0    // 同じものを xor すると結果は 0
  • (x ^ y) ^ z = x ^ (y ^ z)   // 結合法則
  • x ^ y = y ^ x    // 交換法則

なので、 (x ^ y) ^ x = (y ^ x) ^ x = y ^ (x ^ x) = y ^ 0 = y となる。

この性質を使うと、下記のコードで2つの変数を入れ替えることが出来る。

int x = 何らかの値;
int y = 何らかの値;
x ^= y;
y ^= x;
x ^= y;

狐に摘まれた方も少なくないと思うが、上記のコードで x, y に入っている値はしっかり入れ替わる。

x,y の初期値を x0, y0 として説明する。
最初に x ^= y; を実行すると、x には x0 ^ y0 が入る。
次に y ^= x; を実行すると、y0 ^ (x0 ^ y0) = x0 なので、y には x の初期値 x0 が入る。
次に x ^= y; を実行すると、x には (x0 ^ y0)、y には x0 が入っているので、(x0 ^ y0) ^ x0 = y0 となり、x には無事 y0 が入り、x と y の値が交換されることになる。

ご理解いただけたであろうか?

演習問題:

  1. 変数の値を入れ替えるコードをビルド・デバッガで実行し、本当に中身が入れ替わることを確認しなさい。

ビット演算>右シフト

右シフトとは、下図のように、各ビットをひとつ右にずらし、最上位ビットに0を入れることだ。最下位ビットの値は捨てられる。
ただし、シフトされる対象が符号付きの場合、最上位ビットの値はそのまま残る。

temp

1ビット 左シフトとが2倍することだったことの裏返しで、1ビット右シフトは2で割る(余りは切り捨て)ことと同等だ。符号付き整数を右シフトした場合、最上位ビットがそのまま残るのは、マイナスの数値の符号を維持するためだ。

C/C++ では 二項演算子 >> が右ビットシフトを表す。
シフトするビット数は1だけとは限らず、「x >> 2」 の様にシフトするビット数を付加して記述することが出来る。

int x = 0xff00 >> 4;  // 0xff00 を4ビットシフトした値を x に代入
x >>= 2;  //  x を 2ビット左シフトし、それを x に代入

上記は C/C++ での右シフトの使用例だ。

前稿 で、左シフトを使って、全ビットを検査するコードを示したが、左シフトでは最下位ビットから最上位ビットに向かって、順に処理を行うことになる。場合によっては、最上位ビットから下位ビットに向かって、処理を行いたい場合がある。その場合は、右シフトを用いる。

int x = 何らかの値;
for(unsigned int mask = 0x80000000; mask != 0; mask>>=1) {
  if( (x & mask) != 0 ) {  // x の mask ビットが立っていたら
    何らかの処理;
  }
}

注意すべきは、mask は符号付きではなく、符号なし(unsigned)を用いないといけないという点だ。符号付だと、最上位ビットが残ってしまい、うまくループしてくれない。

演習問題:

  1. int x = 100; を宣言し、x を1ビット右シフトした値を表示し、値が半分になっていることを確認しなさい
  2. int x = -100; を宣言し、x を1ビット右シフトした値を表示し、値が半分になっていることを確認しなさい
  3. int x; に何らかの値が入っているとき、中身のビットを逆順にするコードを書きなさい。例:0xff00aa03 → 0xc05500ff;

演習問題解答例

ビット演算>左シフトと論理積による全ビット検査

左シフト(<<)と論理積(&)を使って、全ビットを検査するコードはよく使うので紹介しておく。

int x;
x に何らかの値を設定;
int bitCount = 0;
for(int mask=1; mask != 0; mask<<=1) {
  if( (x & mask) != 0 )
    ++bitCount;
}

上記は、x の全ビットを調べ、ビットの値が1であれば bitCount をインクリメントすることで、 x の中の値が1のビットの数を計算するコードだ。
mask の値は最初 1 で、ループ毎に左にシフトされて行き、上位ビットから溢れた時点でループを終了する。

このように、ループとシフトとビット演算を使うことはよくあるので、ちゃんと理解し、マスターしてほしい。

ビット演算>左シフト

左シフトとは、下図のように、各ビットをひとつ左にずらし、最下位ビットに0を入れることだ。最上位ビットの値は捨てられる(最上位ビット1で、それが捨てられることを「ビット溢れ」と呼ぶ)。

shift-left

C/C++ では 二項演算子 << が左ビットシフトを表す。
シフトするビット数は1だけとは限らず、「x << 2」 の様にシフトするビット数を付加して記述することが出来る。

int x = 0xff << 4;  // 0xff を4ビットシフトした値を x に代入
x <<= 2;  //  x を 2ビット左シフトし、それを x に代入

上記は C/C++ での左シフトの使用例だ。

2進数の各ビットの値を b[i] とすると、値は Σ (b[i] * 2^i) である。
1ビット左シフトするということは b[i+1] = b[i] を実行することなので、ビット溢れがなければ、シフト後の値は Σ (b[i] * 2^(i+1)) = Σ (b[i] * 2^i)*2) = 2 * Σ (b[i] * 2^i) となる。

つまり、ビット溢れが無い場合は、1ビット左シフトするということは値を2倍することを意味する。
2ビット左シフトなら4倍、3ビット左シフトなら8倍、4ビット左シフトなら16倍・・・ というわけだ。

このことがよく理解出来ない人は、10進数を考えるといいかもしれない。
例えば「123」を一桁左シフトすると「1230」となる。もとの値の10倍だ。これは10進数だからである。
2進数なら1ビット左シフトは2倍、N進数なら1桁左シフトはN倍ということだ。

演習問題:

  1. int x = 100; を宣言し、x を1ビット左シフトした値を表示し、値が2倍になっていることを確認しなさい
  2. char c = 5; を宣言し、c <<= 6 を実行すると、c の値はいくつになるかを事前に予想してから、結果を確かめなさい。
  3. int x; に何か数値が入っているとき、掛け算を使わず、左シフトを使って x を10倍にするコードを書きなさい。

 演習問題解答例

 

ビット演算>ビット反転

ビット反転とは、ビットが0ならば1に、ビットが1ならば0にすることである。
C/C++ では前置演算子で 「~」 記号を使用する。

A ~A
0 1
1 0

A が入力で、~A のカラムが演算結果だ。

int や short などの整数型に「~」演算子を適用すると、各ビットが反転する。

short x = 0b0000000100100011;
short z = ~x; // z には x のビット反転 0b111111101101100 が代入される

論理積のところで、変数 x の特定のビットを強制的に0にしたい場合は、0にしたいビットを0、それ以外を1にした値と論理積をとるとよい、と説明した。覚えているだろうか?

例えば、int x; に値が入っていて、下位4ビットを強制的に0にしたい場合は、 x &= 0xfffffff0; と書く。
が、0xfffffff0 はわかりづらいので、x &= ~0xf; と書くのが普通だ。この方が、f の数を数えなくても下位4ビットを強制的に0にするということが明確で分かりやすい。