質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.92%

ビット列のカウント、比較方法について

解決済

回答 8

投稿 編集

  • 評価
  • クリップ 4
  • VIEW 1,092

tiitoi

OpenCV総合1位

ビット列のカウント、比較について、以下の問題の演算回数を削減する方法がもしあれば教えていただきたいです。

ビットカウントの分割統治法 のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
プログラムは C++ で書いており、下記問題を計算する部分の呼び出し回数が多く、ボトルネックとなっているため、少しでも演算回数を減らしたいというのが質問の背景です。

追記 9/17

沢山のアイデア、サンプルコードありがとうございます。
実行時間を検証した結果、以下のようになりました。

  • C++17

  • Visual Studio 2019

  • ベンチマーク 検証コード

  • テストケース: 今回解きたい全パターン 40万件弱

  • CPU: Core™ i9-9900K 3.6 GHz

  • 40万件*100回=4000万回の計算時間を算出したら以下のようになりました。

                    合計のカウント   1以上の要素数   2以上の要素数   2の要素数  
 質問記載コード            1358ms    1294ms    1452ms    1458ms 
 SHOMI さんのコード       1074ms (-284)    1215ms (-79)    1280ms (-172)    1256ms (-202) 
 kazuma\-sさんのコード    1068ms (-290)   1140ms (-154)   1137ms (-315)   1144ms (-314) 
 kazuma\-sさんのコード2   978ms (-380)    949ms (-345)    1026ms (-426)    996ms (-462)  
 kichirb3 さんのコード    957ms (-401)   854ms (-440)    786ms (-666)     986ms (-472)  

皆さんにご回答いただいた内容を理解していこうと思いますが、時間がかかると思うので一旦質問はクローズします。
全員 BA としたいのですが仕様上できないので、最初にビット演算のコードを使った回答をしていただいた SHOMI さんを BA に選択します。
ありがとうございました。d

問題設定

各値が 0 ~ 4 である長さが 9 の配列があるとします。
各値の最大値は4 (0b100) で 3bit あれば表せるため、配列全体を 3 * 9 = 27bit 表現します。

  • 1 ~ 3bit: a[0]
  • 3 ~ 6bit: a[1]
  • ...
  • 21 ~ 27bit: a[9]

イメージ説明

例えば、[0, 2, 0, 2, 2, 1, 1, 1, 4] の場合、ビット列での表現は 100|001|001|001|010|010|000|010|000 になります。(| は区切りがわかりやすいように入れています)

言語・環境について

  • 動作環境は C++17 です。
  • コンパイラは Visual Studio 2019 Update6
  • 今は int (32bit) にビット値を格納しています。28~32bitは未使用で0になっています。
  • 計算量削減以外に C++ に特化した最適化方法のアイデア等でも大丈夫です。

サンプルコードが C++/Python ですが、ビット演算はどの言語にもあると思うので、ビット演算を使用した計算法であれば、特に言語を限定した質問ではないです。

質問内容

このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。

  1. 元の配列の各値の合計
  2. 元の配列の各値が1以上の要素数
  3. 元の配列の各値が2以上の要素数
  4. 元の配列の各値が2の要素数
  • どれか1つだけでもよいです。
  • コードでなくとも、アイデアだけでも助かります。

例: [0, 2, 0, 2, 2, 1, 1, 1, 4] (69510160)の場合

  1. 元の配列の各値の合計: 13
  2. 元の配列の各値が1以上の要素数: 7
  3. 元の配列の各値が2以上の要素数: 4
  4. 元の配列の各値が2の要素数: 3

C++

#include <iostream>

int main()
{
    int x = 69510160;

    // 各値の合計
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i)
            cnt += (x >> i * 3) & 0b111;

        std::cout << cnt << std::endl;
    }

    // 各値が1以上の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i) {
            if ((x >> i * 3) & 0b111)
                cnt++;
        }
        std::cout << cnt << std::endl;
    }

    // 各値が2以上の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i) {
            if (((x >> i * 3) & 0b111) >= 2)
                cnt++;
        }
        std::cout << cnt << std::endl;
    }

    // 各値が2の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i) {
            if (((x >> i * 3) & 0b111) == 2)
                cnt++;
        }
        std::cout << cnt << std::endl;
    }
}

少し演算回数を減らしたコード

#include <iostream>
#include <vector>

/**
 * @brief マスク
 */
const std::vector<int> mask = {
    7, 7 << 3, 7 << 6, 7 << 9, 7 << 12, 7 << 15, 7 << 18, 7 << 21, 7 << 24,
};

/**
 * @brief 2以上かどうか調べるときのマスク
 */
const std::vector<int> ge2 = {
    6, 6 << 3, 6 << 6, 6 << 9, 6 << 12, 6 << 15, 6 << 18, 6 << 21, 6 << 24,
};

int main()
{
    int x = 69510160;

    // 各値の合計
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i)
            cnt += (x >> i * 3) & 0b111;

        std::cout << cnt << std::endl;
    }

    // 各値が1以上の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i) {
            if (x & mask[i])
                cnt++;
        }
        std::cout << cnt << std::endl;
    }

    // 各値が2以上の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i) {
            if (x & ge2[i])
                cnt++;
        }
        std::cout << cnt << std::endl;
    }

    // 各値が2の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 9; ++i) {
            if (((x >> i * 3) & 0b111) == 2)
                cnt++;
        }
        std::cout << cnt << std::endl;
    }
}

Python

from functools import reduce


def to_bit(key):
    """ビット表現に変換する。
    """
    return reduce(lambda x, y: x * 8 + y, key[::-1])


def to_str(x):
    """ビット表現を表す文字列に変換する。(デバッグ用)
    """
    s = f"{x:027b}"
    s = "|".join([s[i : i + 3] for i in range(0, len(s), 3)])
    return s

########### 以下が本題

key = to_bit([0, 2, 0, 2, 2, 1, 1, 1, 4])  # 実際は元の配列はなく、ビット列だけ与えられます
print(key, to_str(key))
# 69510160 100|001|001|001|010|010|000|010|000


# 各値の合計
cnt = 0
for i in range(9):
    cnt += (key >> i * 3) & 0b111
print(cnt)  # 13


# 各値が1以上の要素数
cnt = 0
for i in range(9):
    val = (key >> i * 3) & 0b111
    if val:
        cnt += 1
print(cnt)  # 7


# 各値が2以上の要素数
cnt = 0
for i in range(9):
    val = (key >> i * 3) & 0b111
    if val >= 2:
        cnt += 1
print(cnt)  # 4


# 各値が2の要素数
cnt = 0
for i in range(9):
    val = (key >> i * 3) & 0b111
    if val == 2:
        cnt += 1
print(cnt)  # 3
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • fana

    2020/09/17 10:23

    雑魚の戯言ですが,
    もしも,ある27bitのデータに対して,1.~4. の全ての値を計測せねばならないのだとすれば,
    要素値のヒストグラムを1回作れば(早いかは知りませんけども)「楽」な気はします.

    キャンセル

回答 8

checkベストアンサー

+6

ビットカウントの分割統治法 のように

こう?

int sum(unsigned int bits)
{
    bits = (bits & 0b00000111000111000111000111000111) + (bits >> 3  & 0b00000111000111000111000111000111);
    bits = (bits & 0b00001111000000001111000000001111) + (bits >> 6  & 0b00000000000000001111000000001111);
    bits = (bits & 0b00011111000000000000000000011111) + (bits >> 12 & 0b00000000000000000000000000011111);
    return (bits & 0b00000000000000000000000000111111) + (bits >> 24 & 0b00000000000000000000000000111111);
}
int countGreaterThanOrEqualTo1(unsigned int bits)
{
    bits |= (bits & 0b00010010010010010010010010010010)>> 1;
    bits |= (bits & 0b00100100100100100100100100100100)>> 2;
    bits = (bits & 0b00000001000001000001000001000001) + (bits >> 3  & 0b00000001000001000001000001000001);
    bits = (bits & 0b00000011000000000011000000000011) + (bits >> 6  & 0b00000000000000000011000000000011);
    bits = (bits & 0b00000111000000000000000000000111) + (bits >> 12 & 0b00000000000000000000000000000111);
    return (bits & 0b00000000000000000000000000001111) + (bits >> 24 & 0b00000000000000000000000000001111);
}
int countGreaterThanOrEqualTo2(unsigned int bits)
{
    bits >>= 1;
    bits |= bits >> 1;
    bits = (bits & 0b00000001000001000001000001000001) + (bits >> 3  & 0b00000001000001000001000001000001);
    bits = (bits & 0b00000011000000000011000000000011) + (bits >> 6  & 0b00000000000000000011000000000011);
    bits = (bits & 0b00000111000000000000000000000111) + (bits >> 12 & 0b00000000000000000000000000000111);
    return (bits & 0b00000000000000000000000000001111) + (bits >> 24 & 0b00000000000000000000000000001111);
}
int count2(unsigned int bits)
{
    bits ^= 0b00010010010010010010010010010010;
    bits |= (bits & 0b00010010010010010010010010010010) >> 1;
    bits |= (bits & 0b00100100100100100100100100100100) >> 2;
    bits = (bits & 0b00000001000001000001000001000001) + (bits >> 3  & 0b00000001000001000001000001000001);
    bits = (bits & 0b00000011000000000011000000000011) + (bits >> 6  & 0b00000000000000000011000000000011);
    bits = (bits & 0b00000111000000000000000000000111) + (bits >> 12 & 0b00000000000000000000000000000111);
    return 10 - ((bits & 0b00000000000000000000000000001111) + (bits >> 24 & 0b00000000000000000000000000001111));
}


すみません、上記コードは30bit(a[9])まで使用していました。
上位bitが0で埋まっていれば同じですが、27bitまでの場合は以下コードで。
どちらのコードも上位ビットが0ならbits >> 24のあとの& 0b~は不要です。

int sum(unsigned int bits)
{
    bits = (bits & 0b00000111000111000111000111000111) + (bits >> 3 & 0b00000000000111000111000111000111);
    bits = (bits & 0b00001111000000001111000000001111) + (bits >> 6 & 0b00000000000000001111000000001111);
    bits = (bits & 0b00011111000000000000000000011111) + (bits >> 12 & 0b00000000000000000000000000011111);
    return (bits & 0b00000000000000000000000000111111) + (bits >> 24 & 0b00000000000000000000000000111111);
}
int countGreaterThanOrEqualTo1(unsigned int bits)
{
    bits |= (bits & 0b00000010010010010010010010010010) >> 1;
    bits |= (bits & 0b00000100100100100100100100100100) >> 2;
    bits = (bits & 0b00000001000001000001000001000001) + (bits >> 3 & 0b00000000000001000001000001000001);
    bits = (bits & 0b00000011000000000011000000000011) + (bits >> 6 & 0b00000000000000000011000000000011);
    bits = (bits & 0b00000111000000000000000000000111) + (bits >> 12 & 0b00000000000000000000000000000111);
    return (bits & 0b00000000000000000000000000001111) + (bits >> 24 & 0b00000000000000000000000000001111);
}
int countGreaterThanOrEqualTo2(unsigned int bits)
{
    bits |= bits >> 1;
    bits >>= 1;
    bits = (bits & 0b00000001000001000001000001000001) + (bits >> 3 & 0b00000000000001000001000001000001);
    bits = (bits & 0b00000011000000000011000000000011) + (bits >> 6 & 0b00000000000000000011000000000011);
    bits = (bits & 0b00000111000000000000000000000111) + (bits >> 12 & 0b00000000000000000000000000000111);
    return (bits & 0b00000000000000000000000000001111) + (bits >> 24 & 0b00000000000000000000000000001111);
}
int count2(unsigned int bits)
{
    bits ^= 0b00000010010010010010010010010010;
    bits |= (bits & 0b00000010010010010010010010010010) >> 1;
    bits |= (bits & 0b00000100100100100100100100100100) >> 2;
    bits = (bits & 0b00000001000001000001000001000001) + (bits >> 3 & 0b00000000000001000001000001000001);
    bits = (bits & 0b00000011000000000011000000000011) + (bits >> 6 & 0b00000000000000000011000000000011);
    bits = (bits & 0b00000111000000000000000000000111) + (bits >> 12 & 0b00000000000000000000000000000111);
    return 9 - ((bits & 0b00000000000000000000000000001111) + (bits >> 24 & 0b00000000000000000000000000001111));
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 03:26 編集

    bits |= (bits & 0b00000010010010010010010010010010) >> 1;
    bits |= (bits & 0b00000100100100100100100100100100) >> 2;

    bits |= (bits >> 1) & 0b00000001001001001001001001001001;
    bits |= (bits >> 2) & 0b00000001001001001001001001001001;
    どちらが速いかは確認していません。

    キャンセル

  • 2020/09/16 03:42

    > 上記コードは30bit(a[9])まで使用していました。

    今はビット値を int (32bit) に入れていて 28bit~32bitは0で埋まっているので、上位ビットは気にしなくても動作は大丈夫です。

    キャンセル

  • 2020/09/17 00:44

    全テストケースで正解で、速度も自分が書いたものよりだいぶ早くなりました。アルゴリズムについてはこれから勉強していこうと思います。
    回答していただきありがとうございました。

    キャンセル

+2

合計だけですが、

#include <iostream>

int main()
{
    int x = 69510160;
    // (1)各値の合計
    {
        int cnt = 0;
        for (int i = 0; i < 27; i += 3)
            cnt += x >> i & 0b111;

        std::cout << cnt << std::endl;
    }
    // (2)各値の合計
    {
        int cnt = (x >> 3 & 07070707) + (x & 07070707);
        cnt = (cnt >> 6 & 0170017) + (cnt & 0170017);
        cnt = (cnt >> 12 & 037) + (cnt & 037);
        cnt += x >> 24;
        std::cout << cnt << std::endl;
    }
}


演算回数
(1) = 2回、< 10回、+= 18回、>> 9回、& 9回
(2) = 3回、>> 4回、& 6回、+ 3回、+= 1回

追記
各値が2の要素数

#include <iostream>

int main()
{
    int x = 69510160;
    // (1)各値が2の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 27; i += 3) {
            if ((x >> i & 0b111) == 2)
                cnt++;
        }
        std::cout << cnt << std::endl;
    }
    // (2)各値が2の要素数
    {
        int cnt = x ^ 0555555555;
        cnt &= cnt >> 2 & cnt >> 1;
        cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24);
        cnt = (cnt >> 6 & 030003) + (cnt & 030003);
        cnt = (cnt >> 12 & 7) + (cnt & 7);
        std::cout << cnt << std::endl;
    }
}


演算回数
(1) = 2回、< 10回、+= 9回、>> 9回、& 9回、== 9回、++ 0~9回
(2) = 4回、^ 1回、+= 1回、&= 1回、>> 6回、& 7回、+ 4回

追記2
各値が1以上の要素数

#include <iostream>

int main()
{
    int x = 69510160;
    // (1)各値が1以上の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 27; i += 3) {
            if (x >> i & 0b111)
                cnt++;
        }
        std::cout << cnt << std::endl;
    }
    // (2)各値が1以上の要素数
    {
        int cnt = x >> 2 | x >> 1 | x;
        cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24 & 1);
        cnt = (cnt >> 6 & 030003) + (cnt & 030003);
        cnt = (cnt >> 12 & 7) + (cnt & 7);
        std::cout << cnt << std::endl;
    }
}


演算回数
(1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0~9回
(2) = 4回、| 2回、>> 6回、& 7回、+ 4回

各値が2以上の要素数

#include <iostream>

int main()
{
    int x = 69510160;
    // 各値が2以上の要素数
    {
        int cnt = 0;
        for (int i = 0; i < 27; i += 3) {
            if (x >> i & 0b110)
                cnt++;
        }
        std::cout << cnt << std::endl;
    }
    // 各値が2以上の要素数
    {
        int cnt = x >> 2 | x >> 1;
        cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24 & 1);
        cnt = (cnt >> 6 & 030003) + (cnt & 030003);
        cnt = (cnt >> 12 & 7) + (cnt & 7);
        std::cout << cnt << std::endl;
    }
}


演算回数
(1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0~9回
(2) = 4回、| 1回、>> 6回、& 7回、+ 4回

追記3
表検索のため演算回数が少ない高速版

#include <iostream>

#define A3(x) x,x+1,x+2,x+3,x+4,x+5,x+6,x+7
#define A6(x) A3(x),A3(x+1),A3(x+2),A3(x+3),A3(x+4),A3(x+5),A3(x+6),A3(x+7)
#define A9(x) A6(x),A6(x+1),A6(x+2),A6(x+3),A6(x+4),A6(x+5),A6(x+6),A6(x+7)
char a[512] = { A9(0) };

#define B3(x) x,x+1,x+1,x+1,x+1,x+1,x+1,x+1
#define B6(x) B3(x),B3(x+1),B3(x+1),B3(x+1),B3(x+1),B3(x+1),B3(x+1),B3(x+1)
#define B9(x) B6(x),B6(x+1),B6(x+1),B6(x+1),B6(x+1),B6(x+1),B6(x+1),B6(x+1)
char b[512] = { B9(0) };

#define C3(x) x,x,x+1,x+1,x+1,x+1,x+1,x+1
#define C6(x) C3(x),C3(x),C3(x+1),C3(x+1),C3(x+1),C3(x+1),C3(x+1),C3(x+1)
#define C9(x) C6(x),C6(x),C6(x+1),C6(x+1),C6(x+1),C6(x+1),C6(x+1),C6(x+1)
char c[512] = { C9(0) };

#define D3(x) x,x,x+1,x,x,x,x,x
#define D6(x) D3(x),D3(x),D3(x+1),D3(x),D3(x),D3(x),D3(x),D3(x)
#define D9(x) D6(x),D6(x),D6(x+1),D6(x),D6(x),D6(x),D6(x),D6(x)
char d[512] = { D9(0) };

int main()
{
    int x = 69510160;
    int cnt;

    cnt = a[x>>18 & 0777] + a[x>>9 & 0777] + a[x & 0777];    
    std::cout << cnt << std::endl; // 各値の合計

    cnt = b[x>>18 & 0777] + b[x>>9 & 0777] + b[x & 0777];    
    std::cout << cnt << std::endl; // 各値が1以上の要素数

    cnt = c[x>>18 & 0777] + c[x>>9 & 0777] + c[x & 0777];    
    std::cout << cnt << std::endl; // 各値が2以上の要素数

    cnt = d[x>>18 & 0777] + d[x>>9 & 0777] + d[x & 0777];    
    std::cout << cnt << std::endl; // 各値が2の要素数
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 03:32

    ご回答ありがとうございます。
    検証や理解に時間がかかりそうなので、取り急ぎお礼まで。

    キャンセル

  • 2020/09/17 00:43

    高速版はビット演算のみのコードでは最速でした。
    回答していただきありがとうございました。

    キャンセル

+2

以下のように、データ内の'1'のビット数を数えるビットカウント問題に変換してしまう案はどうでしょうか。

  1. 元の配列の各値の合計
    ビットマスクして9個のデータのMSBのみを残す。ビットカウントして4倍する。
    ビットマスクして9個のデータの真ん中のみを残す。ビットカウントして2倍する。
    ビットマスクして9個のデータのLSBのみを残す。ビットカウントして1倍する。
    これらを合計すると求める答えになる。

  2. 元の配列の各値が1以上の要素数

  3. 元の配列の各値が2以上の要素数
    元データを左シフトしてビットORをとる。その後に9個のデータのMSBのみを残してビットカウントする。

  4. 元の配列の各値が2の要素数
    3ビットのデータのうち、「真ん中のみ1でMSBとLSBは0」のようなマスクを用意する。
    元データとビットANDをとってからビットカウントする。

これなら、いかにビットカウント部分を高速化するかに注力できます。
ビットカウントはCPU内蔵のpopcnt命令を使えば十分高速とは思いますが「faster population count」とかで検索すると
AVX命令を使うとより速くなるみたいな記事がいろいろと出てきます。

#include <iostream>
#include <x86intrin.h>          // gcc
using namespace std;

int calc_a1(unsigned int x);
int calc_a2(unsigned int x);
int calc_a3(unsigned int x);
int calc_a4(unsigned int x);

int main() {
    unsigned int x = 69510160;
    cout << calc_a1(x) << endl;
    cout << calc_a2(x) << endl;
    cout << calc_a3(x) << endl;
    cout << calc_a4(x) << endl;
}

int calc_a1(unsigned int x)
{
    return _popcnt32(x & 0x4924924) * 4 + _popcnt32(x & 0x2492492) * 2 + _popcnt32(x & 0x1249249);
}

int calc_a2(unsigned int x)
{
    x |= (x << 1);
    x |= (x << 1);
    return _popcnt32(x & 0x4924924);
}

int calc_a3(unsigned int x)
{
    x |= (x << 1);
    return _popcnt32(x & 0x4924924);
}

int calc_a4(unsigned int x)
{
    unsigned bit = x & 0x5b6db6d;
    bit |= (bit >> 1);
    bit |= (bit << 1);
    bit &= 0x2492492;
    return _popcnt32((x & ~bit) & 0x2492492);
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 18:58 編集

    ご回答いただきありがとうございます。

    #include <x86intrin.h> が GCC にしかないため、
    64bit 開発環境での windows の場合、#include <intrin.h> を見ると、

    __MACHINEX86_X64(unsigned int __popcnt(unsigned int))
    __MACHINEX86_X64(unsigned short __popcnt16(unsigned short))
    __MACHINEX64(unsigned __int64 __popcnt64(unsigned __int64))
    __MACHINEX86_X64(int _mm_popcnt_u32(unsigned int))
    __MACHINEX64(__int64 _mm_popcnt_u64(unsigned __int64))

    があり、_popcnt32 っぽいものがなかったので
    __popcnt64() に回答いただいたコードを置き換えて、値は正しく計算されたのですが、質問のコードを動かす上での意図とあっていますでしょうか?

    キャンセル

  • 2020/09/16 20:12

    すみません、Visual Studioは使ってないので分からないというのが正直な答えです。別の方の記事になってしまいますが、この方の場合、_mm_popcnt_u64を使っているようです。(https://qiita.com/Seizh/items/26eef63af739ba48e36b)

    キャンセル

  • 2020/09/17 00:40

    _mm_popcnt_u64 で試してみました。計測した中では最速でした。
    SIMD については名前しか聞いたことがないので、これから勉強していこうと思います。
    ありがとうございました。

    キャンセル

+1

ビット列を8進数に変換すると
該当の配列になることを利用することが何等かの突破口かなとも思いましたが、
pythonの組み込み関数ですし、そもそもこういう回答を求められているのか自信ありませんが・・・

a = 0b100001001001010010000010000

b = str(oct(a))

>> 0o411122020

sum(int(i) for i in b[2:])

>> 13

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 00:58 編集

    > ここでの「回数」とは何でしょうか。

    質問内容に曖昧な部分があり、申し訳ないです。後ほど訂正します。
    「効率的」の意味は、コードの簡潔さや行数ではなく、四則演算、ビット演算などの演算回数のことを意図しておりました。
    C++ で高速化を目指しており、このビット演算が絡む部分がボトルネックとなっているため、アセンブラレベルの比較までは考えてなかったですが、
    コード上で見たとき、この計算の演算回数が少しでも減らす方法がないかという意図での質問でした。
    最適化なので、コードが汚くなり、難読になるとは思いますがそれは犠牲になっても大丈夫です。

    キャンセル

  • 2020/09/16 01:16

    和についてこれ以上効率化となると、3桁ごとに4桁にパッキングしてintrinsic使ってSIMDとかですかね。3桁⇒4桁のところはどうしても演算が発生しますが。(具体的なコードは知らない)

    キャンセル

  • 2020/09/16 01:19

    コメントありがとうございます。教えていただいたキーワードについて調べてみます。

    キャンセル

+1

言語を限定した質問ではない

という事なので・・・cとc++限定ですが・・・題意に沿わないようなら無視して下さい。

#include <stdio.h>

typedef struct {
    unsigned val1 : 3;
    unsigned val2 : 3;
    unsigned val3 : 3;
    unsigned val4 : 3;
    unsigned val5 : 3;
    unsigned val6 : 3;
    unsigned val7 : 3;
    unsigned val8 : 3;
    unsigned val9 : 3;
} bitField;

int main(void)
{
    bitField bf = {0, 2, 0, 2, 2, 1, 1, 1, 4};

    printf("%d\n", bf.val1);
    printf("%d\n", bf.val2);
    printf("%d\n", bf.val3);
    printf("%d\n", bf.val4);
    printf("%d\n", bf.val5);
    printf("%d\n", bf.val6);
    printf("%d\n", bf.val7);
    printf("%d\n", bf.val8);
    printf("%d\n", bf.val9);

    return 0;
}


結果
usr ~/Project/c % ./a.out 
0
2
0
2
2
1
1
1
4
・・・ビットフィールドに配列は使えない^^;
[追記]・・・初期化にしかビットフィールド使ってない^^;力任せw

#include <iostream>

typedef struct {
    unsigned val1 : 3;
    unsigned val2 : 3;
    unsigned val3 : 3;
    unsigned val4 : 3;
    unsigned val5 : 3;
    unsigned val6 : 3;
    unsigned val7 : 3;
    unsigned val8 : 3;
    unsigned val9 : 3;
} bitField;

int main(void)
{
    bitField bf = {0, 2, 0, 2, 2, 1, 1, 1, 4};

    unsigned int cnt[8] = {0};
    cnt[bf.val1]++;
    cnt[bf.val2]++;
    cnt[bf.val3]++;
    cnt[bf.val4]++;
    cnt[bf.val5]++;
    cnt[bf.val6]++;
    cnt[bf.val7]++;
    cnt[bf.val8]++;
    cnt[bf.val9]++;
    //
    int sum = bf.val1 + bf.val2 + bf.val3 + bf.val4 + bf.val5 + bf.val6 + bf.val7 + bf.val8 + bf.val9;
    int nz  = 0;
    int u2  = 0;
    //
    for(size_t i = 1; i < 8; i++) {
        //        std::cout << cnt[i] << std::endl;
        nz += cnt[i];
        if(i > 1) {
            u2 += cnt[i];
        }
    }
    std::cout << "元の配列の各値の合計:" << sum << std::endl;
    std::cout << "元の配列の各値が1以上の要素数:" << nz << std::endl;
    std::cout << "元の配列の各値が2以上の要素数:" << u2 << std::endl;
    std::cout << "元の配列の各値が2の要素数:" << cnt[2] << std::endl;
    //
    return 0;
}


結果
元の配列の各値の合計:13
元の配列の各値が1以上の要素数:7
元の配列の各値が2以上の要素数:4
元の配列の各値が2の要素数:3

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/17 00:52

    ビットフィールドと union 使えば、個々に要素を取り出したり、1つのビット値として取り出しすこともできそうなので、いろいろ使えそうな気がしてきました。
    アイデアをくださりありがとうございます。

    キャンセル

  • 2020/09/17 01:07 編集

    ビットフィールドと(例えば)intで取り出した時の、ビット毎の配置が同一という保証はなかったと思います。(未確認)・・・処理系依存?・・・だと思うのでご注意下さい。

    キャンセル

  • 2020/09/17 01:14 編集

    > 処理系依存?・・・だと思うのでご注意下さい。
    なるほど。ビットフィールドのレイアウトが特に仕様で規程されていないようですね。

    以下の SO みていけるのかなと思ってたのですが、よく見たらコメントでツッコミが入っていました。
    https://stackoverflow.com/questions/2468708/converting-bit-field-to-int

    キャンセル

+1

#※間違いがあるので参考リンク以外を非表示にしておきます。


参考:ビット演算

参考:ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 01:23 編集

    ご回答ありがとうございます。
    コメントいただいた内容について理解、検証してみます。

    キャンセル

  • 2020/09/16 06:02 編集

    010 100 011
    010 010 010
    例えば==2を判定する場合、ANDを取っても2なのか3なのかはっきりしないので他条件でも同様にこの方法では判定出来ないと気づきました。
    テストケースが小さくて見落としていました。このままだと間違いなので一旦取り下げておきます。
    失礼しました。

    キャンセル

  • 2020/09/16 07:01

    蛇足だとは思いますがシステム的に許されるなら(0-4)の全5^9パターンの答えを作っておいて参照させるのはダメですよね?膨大なメモリ消費すると思いますが速度優先とのことなのでもしかしたらと思いました。

    キャンセル

  • 2020/09/17 00:50

    > システム的に許されるなら(0-4)の全5^9パターンの答えを作っておいて参照させるのはダメですよね

    全然ありです。
    質問の事がやりたかった背景として、以下の麻雀の和了り判定のプログラムを作っていて、その中ですでに5^9のうち、200MBぐらい使って必要な全パターンをテーブル化しています。 https://github.com/nekobean/mahjong-cpp
    「a[0]とa[9]が2個ずつあるか」のようにチェックしたい項目が多数あるため全部を記録しておくことは難しいですが、mjk さんがおっしゃっていただいたように合計数とか計算頻度の高いものは記録しておくこともありだと思いました。

    貴重なアイデアをいただきありがとうございます。

    キャンセル

+1

本題の前に、提示のC++コードには演算子の優先順位が意図通りになっていないバグがあります。

--- hoge.cpp    2020-09-16 02:09:33.346257663 +0900
+++ hoge1.cpp   2020-09-16 01:57:43.685888192 +0900
@@ -27,7 +27,7 @@
     {
         int cnt = 0;
         for (int i = 0; i < 9; ++i) {
-            if ((x >> i * 3) & 0b111 >= 2)
+            if (((x >> i * 3) & 0b111 )>= 2)
                 cnt++;
         }
         std::cout << cnt << std::endl;
@@ -37,7 +37,7 @@
     {
         int cnt = 0;
         for (int i = 0; i < 9; ++i) {
-            if ((x >> i * 3) & 0b111 == 2)
+            if (((x >> i * 3) & 0b111 )== 2)
                 cnt++;
         }
         std::cout << cnt << std::endl;

提示コードが、どの程度実際のコードを反映しているのかわかりませんが、
3ビット値を何回も取り出すよりも
1度だけ3ビット値を取り出してからその値に対して集計処理を行ったほうが良さそうな気がします。
(ベンチマークとかアセンブラコード出力して検証をしたりはしていません。)

#include <iostream>

int main()
{
    int x = 69510160;
    int sum = 0;
    int over1 = 0;
    int over2 = 0;
    int equal2 = 0;

    for (  int i = 0 ; i < 9 ; ++i ) {
        int v;

        v = (x >> i * 3) & 0b111;

        // 各値の合計
        sum += v;

        // 各値が1以上の要素数
        if ( v ) {
            ++over1;
        }

        // 各値が2以上の要素数
        if ( v >= 2 ) {
            ++over2;
        }

        // 各値が2の要素数
        if ( v == 2 ) {
            ++equal2;
        }
    }

    std::cout << sum << std::endl;
    std::cout << over1 << std::endl;
    std::cout << over2 << std::endl;
    std::cout << equal2 << std::endl;

    return 0;
}

あと、可読性は落ちますが、ifを通る回数を減らしたり、xをxworkにコピーして破壊しながら3ビットずつ取り出すとかすればちょっと速くなるかもしれません。

#include <iostream>

int main()
{
    int x = 69510160;
    int sum = 0;
    int over1 = 0;
    int over2 = 0;
    int equal2 = 0;
    int xwork;

    xwork = x;
#if 0 /* 0になった時点で(xから取り出すものがなくなった時点で)終了できるがなんか弊害があるかも */
    while ( xwork != 0 )
#else
    for ( int i = 0 ; i < 9 ; ++i )
#endif
    {
        int v;

        v = xwork & 0b111;
        xwork >>= 3;

        // 各値の合計
        sum += v;

        // 各値が1以上の要素数
        if ( v ) {
            ++over1;

            // 各値が2以上の要素数
            if ( v >= 2 ) {
                ++over2;

                // 各値が2の要素数
                if ( v == 2 ) {
                    ++equal2;
                }
            }
        }
    }

    std::cout << sum << std::endl;
    std::cout << over1 << std::endl;
    std::cout << over2 << std::endl;
    std::cout << equal2 << std::endl;

    return 0;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 03:32

    ご回答ありがとうございます。
    検証や理解に時間がかかりそうなので、取り急ぎお礼まで。

    キャンセル

  • 2020/09/16 03:36

    演算子の優先順位については修正しました。ビット演算は普段あまり使わないのであやふやになっていました。
    ご指摘ありがとうございます。

    キャンセル

  • 2020/09/17 00:55

    > ifを通る回数を減らしたり

    実際のコードの中でループの中で1以上と2以上は両方チェックする部分はあるので、そこは入れ子にして削減できそうです。アイデアをくださりありがとうございます。

    キャンセル

+1

ちょうど別言語でテストしていましたが
一番早かったのはデータ型を変換した配列に一度移し替えて計算する方式でした。
もし値自体で計算を行うのでしたら
最も速い数値型
に変換されるのが良いでしょう
ビットシフト演算も早いかもしれません 

ビットシフト演算が遅い言語の場合の手段です

  1. 各バイト用の辞書配列を先に用意(private変数)
    例 byte Dec[4][256][4];
    // 00010000 → 16 
    Dec[0][16][0] = 0; // 000
    Dec[0][16][1] = 2; // 010
    Dec[0][16][2] = 0; // 000
    // 10100100 → 164 
    Dec[1][164][0] = 0; // 0
    Dec[1][164][1] = 2; // 010
    Dec[1][164][2] = 2; // 010
    Dec[1][164][3] = 1; // 1
    // 10100101 → 165 
    Dec[1][165][0] = 4; // 1
    Dec[1][165][1] = 2; // 010
    Dec[1][165][2] = 2; // 010
    Dec[1][165][3] = 1; // 1

  2. 元の値がintとしてbyte[4]に分割(memset使用)

  3. 辞書配列から各値を取得し別の配列に再設定

以降2.~3.の繰り返し

処理回数が少ないと辞書を作成する時間のほうがかかりますが
意外と使えます。

あと確認できていないのですが
ビットフィールド
指定した構造体にmemsetでコピーがうまくいけば早いかもしれません。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 03:33

    ご回答ありがとうございます。
    検証や理解に時間がかかりそうなので、取り急ぎお礼まで。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る