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; }
中村さん初めまして、色々参考にさせてもらってます。 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のマスクそのまま使うと左から何番目とかも できたりとかいかがでしょうか
スタンフォード大学の懸賞金付き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の場合。
}
下位ビットの影響を受けてしまうので、消してあげないといけないですね。
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;
}
さささんのnlz5は正しく動かないようです。
入力値bを2のべき乗に切り下げて(ハッカーのたのしみで言うところのflip2)
最後のreturnを下記のように変更すれば意図通り動くと思います。
return 31-((b&0xFFFF0000)?c|0x10:c);
さささんコメントありがとうございます。
Core i5-2400 での測定では POPCNT や浮動小数点のトリックを使わないやり方では、さささんのアルゴリズムが一番高速でした。
記事を書き直しました。
中村さん初めまして、色々参考にさせてもらってます。
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のマスクそのまま使うと左から何番目とかも
できたりとかいかがでしょうか
>>NTZ は比較的簡単である。 x&(-x) を行うと左側から最初に 1 が立っているアドレスのみを残して
>「右側」では?
左側は私のミスです。ページを修正しておきます。
>NTZ は比較的簡単である。 x&(-x) を行うと左側から最初に 1 が立っているアドレスのみを残して
「右側」では?
原著はハードカバーだから高いのでは?
このページを見る前に先ほど原著をAMAZONで注文しました。日本語版の方が値段が安いとは...
ぶぅさん、情報ありがとうございます。
邦訳は 3,570円 と価格的にお徳なので、原著を持っていない人にはよいかも (^_^;
Hacker's Delight の日本語訳が出てるようですね。
http://www.amazon.co.jp/exec/obidos/ASIN/4434046683/250-9184073-6450663
nminoruさんには悪いけど原著をもう買ったので、多分買わないだろうなぁ。
会社の資料室には買わせるかも。