BST(2)

ビット演算超魔術(その2)

0と1の反転は演算子「~」を使えば簡単に出来るのだが、今回は部分的に入れ替えたり反転させたいので使うことができない。

最下ビットから初めて1が出てくる一つ手前までを反転させるには、1を引けば良い。前回の例312で考えると、

312: 100111000
311: 100110111

この2数の論理和(312|311)は、

100111000
100110111

• • • • • • • • -

100111111

で315になっている!

論理積(312&311)はどうだろう。

100111000
100110111

• • • • • • • • -

100110000

これは304。1を足せば小さい方の答え305になる!!

入力値nとすると、
出力する2数は

1|n&n-1
n|n-1

うんうん、たしかに超短いっ!