❤️
bit-fieldで1に到達するまでの個数を数える
結論
- 元の値から1を引く
- 元の値と引いた値でxorを取る
- 1の個数を数える(popcountとか)
どういう場面で使える？
複数のbitが立ったbit-fieldがあり、1つずつ個別に処理したいという場面で使えます。
思いつくまでの考え方
2進数において、1を引くことで繰り下がりにより1に到達するまで1が連続的に続くという数字の性質があります。
例えば、10010000の場合、-1することで10001111となります。
また、元の値と1引いた値のxorを取るということは、値の変化した部分を取得するのと同じ意味になるため、これらを組み合わせることにより、実現できました。
追記
元々SIMDのために考えていたのですが、命令が既に存在していました...
Discussion