[B! bitcount] yu4uのブックマーク

x86x64 SSE4.2 POPCNT

2021/4/28 に東京大学で開催された＜AIセミナーシリーズ＞「Arm CPUにおけるSIMDを用いた高速計算入門」講演会で使用した資料になります。

yu4u 2011/08/23

リンク

仕事でintのビット数を数える処理が必要になった。 SSE4あたりではPOPCNTがあるらしいが、そんな新しいCPUとかコンパイラはつかってないのでどんなアルゴリズムがあるか調べてみた。こんなのがあって int popcnt1(unsigned int val){ unsigned int bits = val; bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0F0F0F0F) + (bits >> 4 & 0x0F0F0F0F); bits = (bits & 0x00FF00FF) + (bits >> 8 & 0x00FF00FF); bits = (bits & 0x0000

yu4u 2011/03/22

bitcount

リンク

アセンブラ vs C言語のテーブル引き　速度対決！ - 小宮日記

かずさんの提案で、ビットの立ってる１を数える関数をアセンブラで書いた場合と、 8ビットでテーブルもっといて一発で引いた場合（ソースはうさ親さん提供のれさぴょんから）を比較してみました。ソースは最後にあります。アリーナに鍛え抜かれた強者たちが入ってきました。筋肉と筋肉が雌雄を決するアスリート同士の頂上がちんこ対決。筋肉番付、今スタートです！さて注目の結果は？ C:\misaki>bench 0xaaaaaaaa PopCnt32 =1440000016 2.7s 0xaaaaaaaa PopCnt32b=1440000016 1.4s 0xa00aa00a PopCnt32 =720000008 1.3s 0xa00aa00a PopCnt32b=720000008 1.4s 0xa000a000 PopCnt32 =360000004 0.8s 0xa000a000 PopCn

yu4u 2011/03/22

bitcount

リンク

Bit Twiddling Hacks

By Sean Eron Anderson seander@cs.stanford.edu Individually, the code snippets here are in the public domain (unless otherwise noted) — feel free to use them however you please. The aggregate collection and descriptions are © 1997-2005 Sean Eron Anderson. The code and descriptions are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY and without even the implied warranty of

yu4u 2011/03/22

リンク

Fast Bit Counting

Devise a fast algorithm for computing the number of 1-bits in an unsigned integer. If the machine supports n-bit integers, can we compute the number of 1-bits in O(log n) machine instructions? Can we compute the number of 1-bits in O(b) machine instructions where b is the number of 1-bits in the integer?