RSB - 個人的な競プロメモ

RSB

Rightmost Set Bitの略（この競プロメモ中ではこう訳すことにしています）

1になってるやつで一番右側にあるやつのこと。x & -x で求められる。

https://gyazo.com/fae906b56ec52eb891ed352c018abb71

どうして立ってるビットの一番右が x & -xで求められるのか？

実はコンピュータ内でのマイナス表現はビット否定(0と1が逆)に1を足したものになる。

例：14(00001010)なら-14は(11110110)になる、みたいなイメージ。但し8bitまでしか考えていない。

実際は1111111...1111111111111111111110110だったりするけど、簡単にするために最初の8桁しか考えてない

実験

code:sample.cpp

#include <bitset>

#include <iostream>

using namespace std;

int main() {

int x = 1920826;

cout << "x .... " << bitset<32>(x) << endl;

cout << "~x ... " << bitset<32>(~x) << endl;

cout << "~x+1 . " << bitset<32>(~x + 1) << endl;

cout << "-x ... " << bitset<32>(-x) << endl;

cout << "x & -x " << bitset<32>(x & -x) << endl;

}

table:実行結果

x 00000000000111010100111100111010

~x 11111111111000101011000011000101

~x+1 11111111111000101011000011000110

-x 11111111111000101011000011000110

x & -x 00000000000000000000000000000010

~ ビット否定 … 0と1を逆転させる

& ビット積 … どっちも1の時1でそれ以外は0

もし元のxが2進数で「000100000」みたいなのだったら、反転したのは「111011111」になる。そこに1を足すと繰り上がっていって一番最初の0で止まって「111100000」になる。

そこより左の所は全て反転してるので0、右の所は繰り上がった結果0になっているので0になる。なので一番下の立っているbitがx & -xで求められる。