C++のような言語でビット演算的な

本来、C++でビット演算と言えば、”&”や”|”などで実装するんだけど、今回はちょいと違う。
というのも、今回やりたいことというのは、
「任意の値を複数格納するための配列xがあるとして、この中に含まれている値には何があるのかを簡単に調べる」
というもの。

この配列xには同じ値は存在し得ないとする。更に、与えられる値は予め分かっているものとする。
今回与えられる値は1~9の整数値である。

こういった処理で一番最初に思いつくのは、ビット演算ではないだろうか。
9bitあれば、ビットが立っているかどうかでどの値が存在し、どの値が存在しないのか示すことが出来る。

しかし、基本的にバイト単位で処理されるので、9bitというのは、かなり中途半端である。
まあ、とりあえずビット演算ではどうすれば良いか考えてみよう。以下、2進数は4bit毎に区切って表示する。

それぞれの数値を各ビットに対応させたモノと、全ての数値が揃った状態を一覧にすると、以下の通り。

0000 0001 1111 1111    ALL

0000 0001 0000 0000     9
0000 0000 1000 0000     8
0000 0000 0100 0000     7
0000 0000 0010 0000     6
0000 0000 0001 0000     5
0000 0000 0000 1000     4
0000 0000 0000 0100     3
0000 0000 0000 0010     2
0000 0000 0000 0001     1

しかし、2バイト分の変数を用意するのが面倒であることと、処理内容的にもこれを本当のビット演算でやるには、地味にコストが掛かりそうである。
そこで、これらの2進数を10進数に変換すると以下のように対応する。

0000 0001 1111 1111    ALL    511

0000 0001 0000 0000     9     256
0000 0000 1000 0000     8     128
0000 0000 0100 0000     7      64
0000 0000 0010 0000     6      32
0000 0000 0001 0000     5      16
0000 0000 0000 1000     4       8
0000 0000 0000 0100     3       4
0000 0000 0000 0010     2       2
0000 0000 0000 0001     1       1

これを見ると、右端の10進数の総和を取ると、511になることが分かる。
つまり、1~9に1~256の数値を対応させると、その総和によって存在する数値を簡単に求めることが出来る。

まあ、だからなんだと言われちゃうと、それまでなんだけどね。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA


このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください