0

フラグの管理用に0, 1が格納されているunsigned char配列hogeがあるとして、この配列を元に「いづれかのフラグがたったらtrueを返す」様な関数をbit演算を駆使して作りたいと考えています。(bitを駆使したフラグ管理練習用なので「別にbit使わなくても...」は無しでお願いいたします)
そこで、以下の様な関数を作成してみました。

bool IsAnyFlag() const
{
    unsigned int flags = 0;
    for (int i = 0; i < NUM; i++)
    {
        flags |= hoge[i] << i;
    }
    return flags != 0;
}

しかしこれでは、一応正常に動きはしますが「for文内で1だったら速攻true返せば早くね?」という話になってしまい、bitに直している意味が無いように感じてしまいます。

では、unsigned char配列を一括でbit列に直せる方法があれば良いのではとも考えましたが、そのような方法は私が調べた限りでは無いようで頓挫しています。

あいまいな言葉で申し訳ないのですが、もっとスマートな方法はありませんでしょうか。
よろしくお願いいたします。

余談ですがchar型が文字専用型ではないというのを最近知り「え!? ちがうのぉ!?」と驚愕しております。

6
  • bitsetを使うのはどうでしょうか。
    – BLUEPIXY
    Commented 2017年5月15日 16:07
  • その方法も検討しましたが、bitsetではフラグを立てるのにset関数を呼ぶ必要がありますので、結局for文で「hoge[i]が1だったらset関数を呼ぶ」という手間が増えてしまうため、現在の所使用を控えています。
    – krnkrs
    Commented 2017年5月16日 8:07
  • いえ、「フラグの管理用に」使用するという意味です。
    – BLUEPIXY
    Commented 2017年5月16日 8:13
  • 申し訳ありません、unsigned char配列が元情報であるという事を前提としており私側でも変更が利かない点でもありますので、面倒をおかけしますがその点を考慮していただけると幸いです。
    – krnkrs
    Commented 2017年5月16日 8:42
  • 機能としては変換する部分とIsAnyの機能は別にすべきかと思います。「「for文内で1だったら速攻true返せば早くね?」という話になってしまい、bitに直している意味が無い」ということにそれが表れていると思います。
    – BLUEPIXY
    Commented 2017年5月17日 7:26

5 件の回答 5

2

std::findを使えば特定の値を検索することができます。見つからなかった場合はlastが返されるのでそれと比較すればいいでしょう。

bool IsAnyFlag() const {
    return std::find(hoge, hoge + NUM, 1) != hoge + NUM;
}

もっとスマートな方法はありませんでしょうか。

素直なコードを記述すればコンパイラーは効率的な処理を生成してくれます。例えば上記コードをVisual C++でコンパイルするとC言語のmemchr関数に展開されます。

もちろんmemchr関数は自身の責任範囲内で効率的な検索を行います。int32_tさんが「大きな整数型でまとめて読むと早くなるケースがあります」と書かれていますが、例えばglibcのmemchrなんかもアラインメントを考慮しながらunsigned long intを使うことで複数まとめて読み込んでいます。Visual C++も32bitに関してはアセンブラ言語で記述されており複数まとめて読み込んでいました。

結局、特殊なコードを記述するよりも、標準ライブラリを活用しシンプルな記述をすることが効率的かと思います。


std::findboost::findの違いについて

Boost

Boostは考案された新機能を標準化させる前の試験運用の場であるとも言える。

という位置づけですので、STLとBoostとで全く同じ機能を持つ場合もあれば、STLに取り込まれる際に変更される場合もあり、またSTLに取り込まれた後にBoost側で更に新機能を追加される場合もあったりとまちまちです。std::findboost::findとが似ているのもそのためです。

3
  • 論点がずれてしまい申し訳ないのですが、boost::findというものとは完全に別物(std::とboost::からみても)なのでしょうか。調べてみると機能自体に差は無いようなのですが。
    – krnkrs
    Commented 2017年5月16日 9:14
  • @krnkrs さん、加筆しました。質問文ではboostに触れられていなかったために言及せず、STLを使って説明しました。
    – sayuri
    Commented 2017年5月16日 9:34
  • @sayuriさん。加筆確認しました。情報ありがとうございます!
    – krnkrs
    Commented 2017年5月16日 9:37
0

unsigned char[] から一括で bit 列にする方法は知りませんが、
はじめから flags に各 bit を持たせておけば良いと思います。

unsigned int flags = 0;
void setFlag(int i) {
    flags |= 1 << i;
}
void clearFlag(int i) {
    flags &= ~(1 << i);
}
bool isAnyFlag(void) {
    return flags != 0;
}
0

ビットで表現されてないものをその場でビット表現に直してもスマートにはならないと思われます。ビット表現に直したものをあらかじめ作るかキャッシュすると意味があるかもしれません。

昔ながらの局所最適化で、大きな整数型でまとめて読むと早くなるケースがあります。が、スマートとは言い難いですね。

alignas(int32_t) unsigned char hoge[NUM];

bool IsAnyFlag() {
  assert(NUM % sizeof(int32_t) == 0);
  for (size_t i = 0; i < NUM; i += sizeof(int32_t)) {
    if (*reinterpret_cast<int32_t*>(&hoge[i]))
      return true;
  }
  return false;
}
2
  • 1
    それは、セグメンテーション違反やバスエラーを引き起こすので、やってはいけない方法です。
    – alpha
    Commented 2017年5月16日 12:01
  • 1
    alignas を付けた hoge の宣言を足しました。
    – int32_t
    Commented 2017年5月17日 1:14
0

「スマート」の定義がわかりませんが,まず前提として

unsigned char配列を一括でbit列に直せる方法

については,質問文で書かれているビットシフトと論理和を使う方法が最もシンプルかと思います.

ただ,もしやりたいことが

いづれかのフラグがたったらtrueを返す

であるなら,ビットシフトは必要ないように思います.

bool any() const
{
    std::uint8_t flag = 0;
    for(std::size_t i = 0; i < NUM; ++i) {
        flag |= hoge[i];
    }
    return flag != 0;
}

for文内で1だったら速攻true返せば早くね?

については,最近のコンパイラは賢いのでうまいこと最適化してくれるかもしれませんが,ちょっと頭の悪い子だったりベクトル化が効く処理だったりすると,いちいち条件分岐する方が計算効率が悪くなり,「いっそ全部論理和をとってから最後に判定した方が早くね?」となる場合もあります.

もっとも,他の回答者さんが言及しているように「最初から整数値1つでフラグ情報を持つ」あるいは「最初からbitsetを使う」方が楽ですが…

0

たまたま hoge配列の中にひとつでも1があるかどうかを判定するだけだからfor文の途中でリターンしていいだけでしょう。例えば、hoge[1]、hoge[3]、hoge[4]のどれかに1つ以上1が含まれていたら?とかいう問題なら、flags & 0x16 が0でないかどうか判定すればflagsの存在意味は出るのではないでしょうか。この0x16のような「マスク」を引数に取る関数とか作ってみるとかしてはどうでしょうか。スマートと言っても練習目的ならこのぐらいでいいと思います。
要素が0,1しか値をとらないのだったらhoge をbool型配列にしてみるとか、シフトのかわりに(内容が、0x1、0x2、0x4、0x8、・・・の定数配列など利用して)マスクを使ってみるとか、いろいろやってみてから、C++の便利なクラスの使い方を学んでみるとか。std::vector なんてものもあります。
あと (unsigned)int型のサイズは処理系によって変わるかもしれませんから、std::uint32_t とか std::uint64_t などの方を使う方がいいと思います。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。