n & (n-1)

用語

f:id:peroon:20190609172619j:plain

  • LSB : least significant bit 一番右の立っているビット
  • MSB : most significant bit 一番左の立っているビット

LSB 求め方

a = 1010
-a= 0110
(足すと0になる)

a & (-a) = 0010 (LSB)

その1: LSBを0にする

  • 一番右の立っているビットを消す
  • 例
101010 (n)
101001 (n-1)
------ (&)
101000

その2: 2のべき乗判定に使える

  • nが2のべき乗なら(1, 2, 4, 8, ...) trueを返す関数なら、
bool is_power_of_two(ll n){
    return !(n & (n-1));
}

MSB 求め方1

  • 2で割っていけばO(log(N))で求まる
// 0番目から数える
// v==0の時はどうする？
ll MSB(ll v){
  rep(i,50){
    v /= 2;
    if(v==0) return i;
  }
}

例
[MSB(2)]: 1
[MSB(3)]: 1
[MSB(4)]: 2
[MSB(15)]: 3
[MSB(16)]: 4
[MSB(17)]: 4

MSB 求め方2

#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;

#define p(s) cout<<(s)<<endl

ll MSB(ull i){
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    ull v = i - (i >> 1);
    return log2(v);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll v = 0b0001010100;
    auto bs = bitset<15>(v);
    p(bs);
    p(bs._Find_first()); // LSB

    p(MSB(v)); // MSB
    
    return 0;
}

// 出力
000000001010100
2
6