はじめに この記事はビット演算テクニック Advent Calendar 2016の23日目の記事です。 www.adventar.org オセロとビット演算 オセロは盤面サイズが8x8=64マスなので、64bit変数を2つ用意し、1つめを自分の石（あるいは黒石）の位置を、2つめを相手の石（ある…

はじめに この記事はKMC Advent Calendar 2016の19日目の記事です。 www.adventar.org GPGPUとは GPGPU（General-purpose computing on graphics processing units; GPUによる汎用計算）とは、GPUの演算資源を画像処理以外の目的に応用する技術のことである…

Bit scan reverse (bsr) 00000001010100010100000100101101 <-clz->*<---bit scan reverse---> 1になっている最も高位のビットのインデックスを0-indexedで計算します。0に対する結果は未定義（不定）です。 似た処理にcount leading zero(clz)があり、こち…

この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の11日目の記事です。 ビット単位のunpack C++の固定長ビット配列を扱うクラスstd::bitsetを例として解説します。 std::bitset<128> unpacklo(const std::bitset<128> &a, const std:…

この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の三日目の記事です。 ビット列の部分列を入れ替える操作を効率的に行えるDelta swapを紹介します。xorが好きなのでDelta swapも好きなテクニックの一つです。 行える操作 マスクとず…

はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。 この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。 本文中で説明を省略した部分については、詳しい説明のあ…

CUDAではDynamic Parallelism（GPU側から新たなカーネルを起動する）以外に普通の（シリアル実行の）再帰が可能です(Compute Capability 2.0以上)。 しかし、再帰的に関数を呼び出す場合、必要なスタックサイズが静的に割り出せないことがあり、このときはデ…