kclib1_0003 のバックアップ(No.2)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
kclib1_0003 へ行く。
- 1 (2019-04-16 (火) 15:19:51)
- 2 (2019-04-16 (火) 15:21:25)

kclib1のページ#3

(by K, 2019.04.16)

(3) kpopCount32

int kpopCount32(unsigned int b)
- 普通のポップカウントです。与えられた引数の中でビットが1になっている個数を数えます。
- これはCPUのpopcnt命令を使って高速化しようとかそういうことは考えていません。古い環境でも確実に計算できればそれで十分なケース向けです。
- こんなの関数にするまでもない規模なのですが、たまに書き方を忘れるので、その時に使います。

[内部実装]

int kpopCount32(unsigned int b)
{
    b -= b >> 1 & 0x55555555U;
    b = (b & 0x33333333U) + (b >> 2 & 0x33333333U);
    b = (b + (b >> 4)) & 0x0f0f0f0fU;
    return (b * 0x01010101U) >> 24;
}

↑

(4) kpopCount64

int kpopCount64(unsigned long long b)
- 普通のポップカウントのlong long版です。与えられた引数の中でビットが1になっている個数を数えます。
- これはCPUのpopcnt命令を使って高速化しようとかそういうことは考えていません。古い環境でも確実に計算できればそれで十分なケース向けです。
- こんなの関数にするまでもない規模なのですが、たまに書き方を忘れるので、その時に使います。

[内部実装]

int kpopCount64(unsigned long long b)
{
    b -= b >> 1 & 0x5555555555555555ULL;
    b = (b & 0x3333333333333333ULL) + (b >> 2 & 0x3333333333333333ULL);
    b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
    return (b * 0x0101010101010101ULL) >> 56;
}

↑

(5) kgetMsb32

unsigned int kgetMsb32(unsigned int i)
- 与えられた引数の最上位ビット位置を抽出します。bsr命令のようにビット位置を返すのではなく、0x0123に対して0x0100を返すように振る舞います。
- 引数に0を与えた場合は想定していませんが、下記の実装からすると1が返ることになりそうです。これは引数に1を与えた場合と同じになっています。
- こんなの関数にするまでもない規模なのですが、たまに書き方を忘れるので、その時に使います。

[内部実装]

unsigned int kgetMsb32(unsigned int i)
{
    i >>= 1;
    i |= i >> 1;
    i |= i >> 2;
    i |= i >> 4;
    i |= i >> 8;
    i |= i >> 16;
    return i + 1;
}

↑

こめんと欄

コメント	お名前	NameLink