Index / Reload

Comment on programming__bitcount

programming__bitcount について、コメントがあればどうぞ!
E-mail アドレスは公開されません。URL は公開されます。
なお、管理者の判断により予告なくコメントを削除することがあります。 ご了承下さい。

パスワードを入力すると後からコメントの修正が可能です。

確認:下の Check の項目に QgoL7sVT をコピーして入力してね。

お名前:
E-mail or URL:
Check: ← 上の方にある確認文字列を入力してね。
Password:
コメント:
* A-11 2022-02-27 04:40:43 [Edit]

スタンフォード大学の懸賞金付きbit操作ハック集
https://graphics.stanford.edu/~seander/bithacks.html
で紹介されている方法では、
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
で共通するマスク処理を別々に行うのではなく、
bits = (bits + (bits >> 4)) & 0x0f0f0f0f;
因数分解っぽい要領で括り出すことで、マスク演算命令を節約しています。
ただし、最初の2bit塊毎,4bit塊毎のカウント処理では、下位bit塊からの繰り上がりが上位bit塊にまで及んでしまうので、この方法は使えませんが。
最初の2bit塊毎の処理では、2bit目からの繰り下がりによりマスク操作を節約する方法を、上記サイトは紹介しています。
bits = bits - (bits >> 1 & 0x55555555);
さらに、
ビットカウントする高速アルゴリズムをPythonで実装しながら詳しく解説してみる - Qiita
https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266
では、最終的に必要なのは最下位の8bit塊だけであることに注目し、以降のマスク操作を最低限のものにしています。

結果として、こんな感じになります。
int numofbits5_stanford(long bits)
{
bits = bits - (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); //ここは変わらない
bits = (bits + (bits >> 4)) & 0x0f0f0f0f;
bits = bits + (bits >> 8);
return (bits + (bits >>16)) & 0x3f; //32bitの場合。
}

* hir0 2014-09-21 07:49:08 [Edit]

下位ビットの影響を受けてしまうので、消してあげないといけないですね。

int
nlz(int x)
{
int c = 0;
if (x == 0) return 32;
if (x & 0xffff0000) { x &= 0xffff0000; c |= 0x10; }
if (x & 0xff00ff00) { x &= 0xff00ff00; c |= 0x08; }
if (x & 0xf0f0f0f0) { x &= 0xf0f0f0f0; c |= 0x04; }
if (x & 0xcccccccc) { x &= 0xcccccccc; c |= 0x02; }
if (x & 0xaaaaaaaa) { c |= 0x01; }
return c ^ 31;
}

* くに 2013-05-08 17:42:14 [Edit]

さささんのnlz5は正しく動かないようです。
入力値bを2のべき乗に切り下げて(ハッカーのたのしみで言うところのflip2)
最後のreturnを下記のように変更すれば意図通り動くと思います。

return 31-((b&0xFFFF0000)?c|0x10:c);

* nminoru 2012-09-02 03:57:14 [Edit]

さささんコメントありがとうございます。
Core i5-2400 での測定では POPCNT や浮動小数点のトリックを使わないやり方では、さささんのアルゴリズムが一番高速でした。
記事を書き直しました。

* ささ 2012-08-31 23:28:02 [Edit]

中村さん初めまして、色々参考にさせてもらってます。
numofbits5 を見て思いついたんですけど
int int nlz5(int b)
{
if(b==0)return 32;
int c = (b&0xAAAAAAAA)?0x01:0;
if(b&0xCCCCCCCC)c|=0x02;
if(b&0xF0F0F0F0)c|=0x04;
if(b&0xFF00FF00)c|=0x08;
return (b&0xFFFF0000)?c|0x10:c;
}
とかしてみるとちょっと早くなるかなとか
numofbits5のマスクそのまま使うと左から何番目とかも
できたりとかいかがでしょうか

* nminoru 2011-10-12 21:14:16 [Edit]

>>NTZ は比較的簡単である。 x&(-x) を行うと左側から最初に 1 が立っているアドレスのみを残して
>「右側」では?
左側は私のミスです。ページを修正しておきます。

* math2ch 2011-10-12 00:02:05 [Edit]

>NTZ は比較的簡単である。 x&(-x) を行うと左側から最初に 1 が立っているアドレスのみを残して
「右側」では?

* dasm 2005-02-23 13:16:57 [Edit]

原著はハードカバーだから高いのでは?

* mctwist 2005-02-13 09:30:39 [Edit]

このページを見る前に先ほど原著をAMAZONで注文しました。日本語版の方が値段が安いとは...

* 管理人 2004-10-18 19:18:11 [Edit]

ぶぅさん、情報ありがとうございます。
邦訳は 3,570円 と価格的にお徳なので、原著を持っていない人にはよいかも (^_^;

* ぶぅ 2004-10-18 18:16:08 [Edit]

Hacker's Delight の日本語訳が出てるようですね。
http://www.amazon.co.jp/exec/obidos/ASIN/4434046683/250-9184073-6450663
nminoruさんには悪いけど原著をもう買ったので、多分買わないだろうなぁ。
会社の資料室には買わせるかも。

Powered by くっつき BBS