LoginSignup
1

More than 5 years have passed since last update.

64bitレジスタ上でselectする

Posted at

突然に64bitのレジスタ上でselectの操作をしたくなるときありますね (ありますね)。これはビット演算テクニックAdvent Calendar 19日目の記事です。

selectとは

select_q(k) は、配列x上を先頭から見たとき、k番目に出現する値qのインデクスを返す関数として定義されます。たとえば、配列 [0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1] について、(左を先頭にして) select_1(3) = 6 となります。

このselectの演算ですが、64bitのレジスタを64要素の {0, 1} の配列と見て、この上で実行したくなるときがあります。これはsuccinct data structureの文脈で出てきたりします。(自分は別の目的でした)

そこにpdepがあらわれた

x86_64にintelが導入したBMI2命令セットに、pdepという命令があります。

pdep

こんな感じに、マスクレジスタを使ってsrcの下位に並んだビットをscatterします。これを使って64bitのレジスタv上でselect_1(k)を計算します。

select

1をkだけ左にシフトし、これをselectしたいベクタをマスクにしてpdepし、結果のレジスタをtzcnt (下位から0を数える) します。また、vのうち1の個数がk個以下の場合は、pdepで1が追い出されるので結果は64となります。シフト、pdep、tzcntともに3クロックかかるのでいうほど速くありませんが、分岐がないのは良いです。めでたしめでたし。

おわりに

pdepってチェスとか将棋にしか使いどころがないのではと思っていたのですが、まさか自分が使うことになるとはと驚き、こんな使い方があったかと発見に嬉しくなりました。この驚きと喜びを誰かに伝えたかった...

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1