-
@ThothChildren
- 2018.10.18
- PV 147
最下位の1が立つbitだけ残したい
ー 概要 ー
高速にビット列が与えられたときに1が立っているビットの中で最下位の1だけを残して他のbitを全て0にする方法についてまとめます.
この章を学ぶ前に必要な知識
条件
- 0と1からなるビット列が入力
効果
- 1が立つ最下位1bitのみを残したビット列を得る
ポイント
- x&(-x)を行うことで最下位の1bitのみを残すことができます.
解 説
高速にビット列が与えられたときに1が立っているビットの中で最下位の1だけを残して他のbitを全て0にする方法についてです.
方法
x = 1100とします.
-x = 0100となります.
このとき最下位の1が立っているbitが変わらず他は反転するため、
これらの"&"を取ることで1だけを残せます.
x & (-x) = 0100
これで目的のビット列が手に入りました. | 最下位の1が立つbitだけ残したい |
| 1だけ残すbit列の作成過程 |
この章を学んで新たに学べる
Comments