動機

之前面試題目有遇過bit trick的考題，用到lowBit!! 所以來記錄一下

這篇不記錄要table或是常數的做法，這裡只記錄用bit operation與負號就能用的手法，如果需要看這裡

需要工具

  • -n (2補數，not是1補數)
    • 取not再加1
  • -1
    • 把到LSM(最左)最近的1mark成0，剩下的到LSM之間的用成1
    • 可以想成把1往左拖，經過的地方都會變成1，類似痕跡
    • 像1000扣1後，變成0111
  • ^ (xor)
  • &,|

思考方式

如果是設定就直接用and,or,xor

如果是要num的bit，就從想要的bit開始，用-n,-1再搭配and

乘除有關就是左右移了

當成array

  • set第i個是1: ret = ret | (1 << i)
  • unset第i個: ret = ret & ~(1 << i)
  • toggle第i個: ret = ret ^ (1 << i)
  • check第i個由沒有被set: ret = ret & (1 << i)
  • 把LSB(最右)到第i個清0: ret = ret & ~((1 << (i+1))-1)
  • 把MSB(最左)到第i個清0: ret = ret & ((1 << i)-1)

幾個bits被set

while (n) {
  n = n & (n-1);
  ret++;
}
return ret;

reverse

unsigned int v;     // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{   
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero

最靠左的1

  • get: n & (-n)
  • del: n & (n-1)

算餘數

const unsigned int n;          // numerator
const unsigned int s;
const unsigned int d = 1U << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m;                // m will be n % d
m = n & (d - 1);

大小寫

  • 小寫: ch |= ' '
  • 大寫: ch &= '_'
    • 其實就是' '的not

是不是2的次方數

(x && !(x & x-1))

被3整除?

3: 11 6: 1100 9: 1111

所以可以看兩位是不是都是1來看是不是整除3

int divide3(int a){
    int ans = 0;
    while(a){
        ans += a&1;
        a>>=1;
        ans -= a&1;
        a>>=1;
    }
    return !(ans);
}

Ref

Bit Tricks for Competitive Programming Bitwise Hacks for Competitive Programming Bit Twiddling Hacks