Re: 明日使えないすごいビット演算 - えびちゃんの日記たぶん今日も使えないと思うんですけど（名推理）． タイトルの元ネタは これ． 上のスライドでは，ワードサイズ \(w\) に対して，以下の演算を \(O(\log w)\) time で求める方法が書かれています． 立っている最上位のビットを取り出す：msb 立っているビットの個数を取り出す：popcount この記事では，このうち msb の添字を \(O(1)\) time で求める方法を紹介してみます． 今後，単に msb と言った場合に添字の方を指すことにします． ソースコードは一番下にあります． 参考にした資料はいつもの CS166 の スライド． 以下では，ワードサイズの四則演算およびビット演算を一単位時間で計算できることを仮定します*1．すなわち，\(w\) bits の整数に関するこれらの演算を一単位時間で行えます． また，扱う整数は符号なし整数とし，\(2^w\) を法と
明日使えないすごいビット演算
