Index
/
Reload
Edit on
programming__bitcount
このコメントを修正します。
内容を修正した後で投稿時のパスワードを入力してください。
現在、コメントを削除する機能がありません。
コメントを削除したい場合には、 コメント欄を空欄にしておいてください (管理人が後で削除します)。
お名前:
E-mail or URL:
Password:
コメント:
スタンフォード大学の懸賞金付き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の場合。 }
Powered by
くっつき BBS