【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.20463

フラグ変数のビット位置の検索
投稿者---chu-(2005/03/24 11:05:41)


フラグ変数のビットが立っている位置の検索方法を考えています。
例えば、0xC0000021だったら31,30,5,0を求めます。
現在の方法ではビットが1つ立っているだけでも最悪32回ループしてしまいます。
もっと効率の良い方法はないでしょうか。
理想は、ビットが立っている個数だけのループ回数で済む方法です。
[ソース]
#include <stdio.h>

typedef unsigned long ulong;

#define SIZE 32

int main(void)
{
    int count[SIZE] = {0};
    ulong flag;
    int i;

    while ( 1 ) {
        printf(">");
        scanf("%lX", &flag);

#if 0
        /* A */
        for ( i = 0; i < SIZE; i++ ) {
            if ( flag & (0x1 << i) ) {
                count[i]++;
            }
            printf(".");
        }
        printf("\n");
#elif 1
        /* B */
        for ( i = 0; flag != 0x0; flag >>= 1, i++ ) {
            if ( flag & 0x1 ) {
                count[i]++;
            }
            printf(".");
        }
        printf("\n");
#elif 0
        /* C */
        /* もっと良い方法は? */
#endif

        for ( i = SIZE-1; i >= 0; i-- ) {
            printf("%d", count[i]);
            if ( i % 4 == 0 )
                printf(" ");
        }
        printf("\n");
    }

    return 0;
}

[実行例]
>01234567
.........................
0000 0001 0010 0011 0100 0101 0110 0111
>89ABCDEF
................................
1000 1002 1020 1022 1200 1202 1220 1222
>00000001
.                                       ← 1回のループで済んでいる
1000 1002 1020 1022 1200 1202 1220 1223
>80000000
................................        ← 1つ立っているだけで32回もループしてしまう
2000 1002 1020 1022 1200 1202 1220 1223



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:フラグ変数のビット位置の検索 20464 たいちう 2005/03/24 12:05:44
<子記事> Re:フラグ変数のビット位置の検索 20465 かずま 2005/03/24 12:48:58
<子記事> Re:フラグ変数のビット位置の検索 20472 chu- 2005/03/24 19:33:59
<子記事> Re:フラグ変数のビット位置の検索 20515 chu- 2005/03/29 15:14:07


No.20464

Re:フラグ変数のビット位置の検索
投稿者---たいちう(2005/03/24 12:05:44)


Aで十分早いのではないかと。
上位ビットが立つことが多いなら、Bの方がAより遅くなるでしょう。
実測してみましたか?

普通のプログラムではここまでシビアな最適化が必要なことは
ないと思います。速度が必要ならたいてい他にもっと見るところがある。

私はもっと良い方法を知らないし思いつけませんが、
世の中には天才的なアルゴリズムも多いので、
良い方法はあるのかもしれません。面白いのがあったら是非見たいな。

ご参考 ビットの数えかた


この投稿にコメントする

削除パスワード

No.20465

Re:フラグ変数のビット位置の検索
投稿者---かずま(2005/03/24 12:48:58)


浮動小数点が IEEE 754 規格と仮定して、ループの回数を減らすだけなら
こんな手もありますが、速いかどうかは実際に測定してみてください。
#include <stdio.h>

typedef unsigned long ulong;

#ifdef BIG_ENDIAN
typedef union { double d; struct { ulong e:12, m:20, m2:32; } s; } DBL;
#else
typedef union { double d; struct { ulong m2:32, m:20, e:12; } s; } DBL;
#endif

#define SIZE 32

int main(void)
{
    int count[SIZE] = {0};  ulong flag;  int i;  DBL a0 = {0}, a;

    while (printf(">"), scanf("%lX", &flag) == 1) {
        for (a.d = flag; a.d != 0; a.d -= a0.d) {
            count[a.s.e - 1023]++;
            a0.s.e = a.s.e;
            printf(".");
        }
        printf("\n");

        for (i = SIZE-1; i >= 0; i--) {
            printf("%d", count[i]);
            if (i % 4 == 0)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}



この投稿にコメントする

削除パスワード

No.20472

Re:フラグ変数のビット位置の検索
投稿者---chu-(2005/03/24 19:33:59)


返信ありがとうございます。

かずまさんのコードはまだ理解できていませんが、それをCとしました。

ウェブを調べていくと、二の補数とのアンドで最下位のオンビットが求まる、という記述を見つけました。
それを利用して求まったビットをインデックス値に変換するという方法で組んだものをDとしました。

・A,B,C,Dそれぞれの1000万回ループをtimeGetTime()で測定
    flag         A    B    C    D
    0x00000001 : 4081 156  2088 452
    0x80000000 : 4338 4220 2168 2413

ビット割り当ては下位から行っていくので、必要になったらBとDを検討しようと思います。

[ソース]
        /* D */
        for ( bit = flag & -flag; bit != 0x0; bit = flag & -flag ) {
            flag ^= bit;
            i = 0;
            for ( bit >>= 1; bit != 0x0; bit >>= 1 ) {
                i++;
            }
            count[i]++;
            printf(".");
        }
        printf("\n");

[実効例]
>01234567
............
0000 0001 0010 0011 0100 0101 0110 0111
>89ABCDEF
....................
1000 1002 1020 1022 1200 1202 1220 1222
>00000001
.
1000 1002 1020 1022 1200 1202 1220 1223
>80000000
.
2000 1002 1020 1022 1200 1202 1220 1223



この投稿にコメントする

削除パスワード

No.20473

Re:フラグ変数のビット位置の検索
投稿者---REE(2005/03/24 20:30:34)


>・A,B,C,Dそれぞれの1000万回ループをtimeGetTime()で測定
    flag         A    B    C    D
    0x00000001 : 4081 156  2088 452
    0x80000000 : 4338 4220 2168 2413
>ビット割り当ては下位から行っていくので、必要になったらBとDを検討しようと思います。

内部のprintfを抜かして測定しましたか?
printfの処理がかなりのウエイトを占めているはずです。



この投稿にコメントする

削除パスワード

No.20475

Re:フラグ変数のビット位置の検索
投稿者---chu-(2005/03/24 21:48:51)


はい、測定のために各処理に以下の変更を加えました。

・printf文の削除
・Bは、flagを壊しているので、flagへのデータセットコードの追加
・Cは、a0の初期化コードの追加(memsetとa0.d=0.0を試し、同じようなのでa0.d=0.0を採用)
・Dは、flagを壊しているので、flagへのデータセットコードの追加

測定コードは以下のようにしました。
    timeA = timeGetTime();
    for ( j = 0; j < LOOP_MAX; j++ ) {
        /* A */
    }
    timeA = timeGetTime() - timeA;



この投稿にコメントする

削除パスワード

No.20474

Re:フラグ変数のビット位置の検索
投稿者---かずま(2005/03/24 21:43:48)


やはり、浮動小数点の演算は遅いようですね。
これはどうでしょう。
    for (; flag != 0; flag &= flag - 1) {
        ulong i = 0, bit = flag & -flag;
        if (bit >>16) i +=16, bit >>=16;
        if (bit >> 8) i += 8, bit >>= 8;
        if (bit >> 4) i += 4, bit >>= 4;
        if (bit >> 2) i += 2, bit >>= 2;
        if (bit >> 1) i += 1;
        count[i]++;
        //printf(".");
    }
    //printf("\n");



この投稿にコメントする

削除パスワード

No.20476

Re:フラグ変数のビット位置の検索
投稿者---chu-(2005/03/24 23:38:11)


そのビット→インデックス変換の方法は応用が利きそうなので覚えておきます。
ありがとうございます。

その方法をEとして再度測定しました。

今までやっていなかった、全ビットがオン/オフのパターンを追加しました。
最悪のケースも考えた場合はBが一番という結果となりました。
フラグ変数の使い方によって使い分けることになりそうです。
[実行結果]
flag       A     B     C     D     E
00000001 : 5153  236   2052  271   1096
80000000 : 5106  4989  2048  2589  1211
00000000 : 4804  168   817   179   325
FFFFFFFF : 5522  4081  35866 45503 32202



この投稿にコメントする

削除パスワード

No.20480

Re:フラグ変数のビット位置の検索
投稿者---かずま(2005/03/25 16:28:11)


> [実行結果]
> flag       A     B     C     D     E
> 00000001 : 5153  236   2052  271   1096
> 80000000 : 5106  4989  2048  2589  1211
> 00000000 : 4804  168   817   179   325
> FFFFFFFF : 5522  4081  35866 45503 32202

私のところでは、E はそんなに悪くなかったようなのですが、
私のテストプログラムに問題があるのでしょうか?
Windows XP (SP1), Pentium 4, 2.8GHz, 521MB RAM, 80GB HDD です。
1000万回まわしています。

C:\tmp>a
flag         A     B     C     D     E
00000001:  1078   125   766   125   141
80000000:  1093  1797   766  1875   344
00000000:  1093    78   344    94    78
ffffffff:  1609  1719 13250 33844  6437

C:\tmp>cl -O a.c winmm.lib
Microsoft(R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.

a.c
Microsoft (R) Incremental Linker Version 7.10.3077
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:a.exe
a.obj
winmm.lib

C:\tmp>type a.c
#include <stdio.h>
#include <windows.h>
#include <mmsystem.h>

#define SIZE  32
#define N     10000000

typedef unsigned long ulong;
typedef union { double d; struct { ulong m2:32, m:20, e:12; } s; } DBL;

void funcA(int *count, ulong flag)
{
    int i;
    for ( i = 0; i < SIZE; i++ ) {
        if ( flag & (0x1 << i) ) {
            count[i]++;
        }
    }
}

void funcB(int *count, ulong flag)
{
    int i;
    for ( i = 0; flag != 0x0; flag >>= 1, i++ ) {
        if ( flag & 0x1 ) {
            count[i]++;
        }
    }
}

void funcC(int *count, ulong flag)
{
    DBL a0 = {0}, a;

    for (a.d = flag; a.d != 0; a.d -= a0.d) {
        count[a.s.e - 1023]++;
        a0.s.e = a.s.e;
    }
}

void funcD(int *count, ulong flag)
{
    int i;  ulong bit;
    for ( bit = flag & -flag; bit != 0x0; bit = flag & -flag ) {
        flag ^= bit;
        i = 0;
        for ( bit >>= 1; bit != 0x0; bit >>= 1 ) {
            i++;
        }
        count[i]++;
     } 
}

void funcE(int *count, ulong flag)
{
    while (flag != 0) {
        ulong i = 0, bit = flag & -flag;
        flag ^= bit;
        if (bit >>16) i = 16, bit >>=16;
        if (bit >> 8) i += 8, bit >>= 8;
        if (bit >> 4) i += 4, bit >>= 4;
        if (bit >> 2) i += 2, bit >>= 2;
        if (bit >> 1) i += 1;
        count[i]++;
     } 
}

void (*f[])(int *, ulong) = { funcA, funcB, funcC, funcD, funcE };
ulong val[] = { 1, 0x80000000, 0, 0xffffffff };

int main(void)
{
    int count[SIZE] = {0}, i, j, k;  ulong t;

    printf("flag         A     B     C     D     E\n");
    for (k = 0; k < 4; k++) {
        printf("%08x:", val[k]);
        for (j = 0; j < 5; j++) {
            t = timeGetTime();
            for (i = 0; i < N; i++) f[j](count, val[k]);
            printf("%6d", timeGetTime() - t);
        }
        printf("\n");
    }
    return 0;
}



この投稿にコメントする

削除パスワード

No.20498

Re:フラグ変数のビット位置の検索
投稿者---chu-(2005/03/28 10:12:57)


> flag         A     B     C     D     E
> 00000001:  1078   125   766   125   141
> 80000000:  1093  1797   766  1875   344
> 00000000:  1093    78   344    94    78

> ffffffff:  1609  1719 13250 33844  6437
B対比       0.936     1 7.707 19.68 3.744

コピー&ペーストした同コードで、私の環境では以下のようになりました。
Win98, BCB5, Pen2, ?Hz, 128MB です。

flag         A     B     C     D     E
00000001:  5450   453  2648   560  1316
80000000:  5304  4486  2654  2373  1371
00000000:  5095   332  1242   385   421

ffffffff:  5112  3699 46031 38792 29936
B対比     1.381     1 12.44 10.48 8.092





この投稿にコメントする

削除パスワード

No.20499

Re:フラグ変数のビット位置の検索
投稿者---REE(2005/03/28 11:33:44)


念のための確認ですが、ちゃんとReleaseモードでコンパイルしてますか?



この投稿にコメントする

削除パスワード

No.20500

Re:フラグ変数のビット位置の検索
投稿者---chu-(2005/03/28 12:11:04)


はい、大丈夫です。


この投稿にコメントする

削除パスワード

No.20501

Re:フラグ変数のビット位置の検索
投稿者---匿名(2005/03/28 14:26:27)


void funcF(int *count, ulong flag)
{
    int i;
    for ( i = 0; flag != 0x0; flag >>= 4, i+=4 ) {
        if ( (flag & 0xF) == 0) continue;
        if ( flag & 0x1 ) {
            count[i]++;
        }
        if ( flag & 0x2 ) {
            count[i+1]++;
        }
        if ( flag & 0x4 ) {
            count[i+2]++;
        }
        if ( flag & 0x8 ) {
            count[i+3]++;
        }
    }
}

flag         A     B     C     D     E     F
00000001:  2432   274   991   294   332   322
80000000:  2391  2149   993  1888   462   949
00000000:  2439   142   519   166   152   148
ffffffff:  3678  4604 16912 31036  8657  2648

win2000 athlon1.2G VC6

単純にB を4bitごとに展開してみただけだけど。


この投稿にコメントする

削除パスワード

No.20502

Re:フラグ変数のビット位置の検索
投稿者---くまさん(2005/03/28 17:41:47)


もっと単純に、

void func(int *count, ulong flag)
{
    if( flag & 0x00000001 )count[0]++;
    if( flag & 0x00000002 )count[1]++;
    if( flag & 0x00000004 )count[2]++;
    if( flag & 0x00000008 )count[3]++;

    if( flag & 0x00000010 )count[4]++;
    if( flag & 0x00000020 )count[5]++;
    if( flag & 0x00000040 )count[6]++;
    if( flag & 0x00000080 )count[7]++;

    if( flag & 0x00000100 )count[8]++;
    if( flag & 0x00000200 )count[9]++;
    if( flag & 0x00000400 )count[10]++;
    if( flag & 0x00000800 )count[11]++;

    if( flag & 0x00001000 )count[12]++;
    if( flag & 0x00002000 )count[13]++;
    if( flag & 0x00004000 )count[14]++;
    if( flag & 0x00008000 )count[15]++;

    if( flag & 0x00010000 )count[16]++;
    if( flag & 0x00020000 )count[17]++;
    if( flag & 0x00040000 )count[18]++;
    if( flag & 0x00080000 )count[19]++;

    if( flag & 0x00100000 )count[20]++;
    if( flag & 0x00200000 )count[21]++;
    if( flag & 0x00400000 )count[22]++;
    if( flag & 0x00800000 )count[23]++;

    if( flag & 0x01000000 )count[24]++;
    if( flag & 0x02000000 )count[25]++;
    if( flag & 0x04000000 )count[26]++;
    if( flag & 0x08000000 )count[27]++;

    if( flag & 0x10000000 )count[28]++;
    if( flag & 0x20000000 )count[29]++;
    if( flag & 0x40000000 )count[30]++;
    if( flag & 0x80000000 )count[31]++;
}


とか。
あと、レアケースの測定ばかりでなく、例えば乱数を1000個ぐらい
発生させて、それで測定した結果の平均を見るかとかも必要では?


この投稿にコメントする

削除パスワード

No.20514

Re:フラグ変数のビット位置の検索
投稿者---匿名(2005/03/29 09:30:33)


>もっと単純に、
(略)
>とか。

funcB や funcF がそれなりに早いのは、調べてない残りの部分
全部が0かどうかを見て、カットしているところにミソがあるので
少なくとも私はこれをやってみようとは思わないです。

>あと、レアケースの測定ばかりでなく、例えば乱数を1000個ぐらい
>発生させて、それで測定した結果の平均を見るかとかも必要では?

まぁこれは質問主が必要ならそうするでしょう。


この投稿にコメントする

削除パスワード

No.20515

Re:フラグ変数のビット位置の検索
投稿者---chu-(2005/03/29 15:14:07)


フラグ変数を下位ビットから割り当てるという使い方と相性が良く、
最悪のケースでも酷いことにはならないF方式が私に合っていそうです。

皆さん返信ありがとうございました。
[実行結果]
flag         A     B     C     D     E     F     G
00000001:  5409   449  2636   553  1307   559  2006
80000000:  5269  4451  2635  2355  1351  1841  1959
00000000:  5059   325  1259   386   410   329  2003
ffffffff:  5099  3731 45716 38563 29718  2821  1831
※くまさんのコードをGとしています



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧