位运算

两个常用的位运算

• 第k位是几
• 最后一位1是哪一位

1 第k位是几

算法

将x右移k位，再与上1

C++实现

int x;
cout<< (x >> k & 1);  // 右移k为与上1

2 最后一位 1：lowbit(x)

算法

将 x 取反后加1，则只有其最后一位 1的位置，会被进位置回 1

再将x & ~x + 1，即 x & -x

c++实现

int lowbit(x) {
    return x & -x; // -x即x的补码，即 x 取反加 1
}