位运算

位运算相关的知识：

• &符号：x & y会将两个十进制数在二进制下进行与运算(都1为1，其余为0)，然后返回其十进制下的值。例如3(11) & 2(10) = 2(10)；
• |符号：x | y会将两个十进制数在二进制下进行或运算(都0为0，其余为1)，然后返回其十进制下的值。例如3(11) | 2(10) = 3(11)；
• ^符号：x ^ y会将两个十进制数在二进制下进行异或运算(不同为1，其余为0)，然后返回其十进制下的值。例如3(11) ^ 2(10) = 1(01)；
• ~符号：~x为按位取反，例如~101 = 010；
• <<符号：左移操作，x << 2将x在二进制下的每一位向左移动两位，最右边用0填充，x << 2相当于让x乘以4；
• >>符号：是右移操作，x >> 1相当于给x / 2，去掉x二进制下的最右一位；有符号右移，正数用0填补，负数用1填补；
• >>>符号：是无符号右移操作，用0填补。

我们可以把异或运算看成不进位的加法。

参见这篇博文 (原始内容存档于此)。

例：二进制系统；不用判断语句求最大值

求第k位数字

应用：求n的二进制表示中第k位是多少。

注意：个位是第0位。

步骤：

• 先把第k位数字移动到最后一位(使用右移>>运算符)；
• 看一下个位数字是多少(x & 1)。

取整数n的二进制数的第k位数为n >> k & 1，注意二进制的位数是从0开始而不是1。

例题：求二进制第k位

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    cout << (n >> k & 1) << endl;  //输出n对应的二进制数的第k位

    //将n对应的二进制数,从第k位~第0位依次输出
    for(int j = k; j >= 0; j--) cout << (n >> j & 1) << ' ';

    return 0;
}

返回最后一位1

例如：二进制数110100，最后一位1输出为100。

二进制数的补码：-x == ~x + 1，其中~x表示取反。

例题：二进制中1的个数

//返回x的最后一位1
//树状数组
//例子：输入二进制(10100)。输出二进制(100)
//注：-x == ~x + 1   其中~x表示取反
int low_bit(int n) {
    return n & -n;
}

low_bit运算是指获取一个二进制数中最右边的1所对应的数值。具体来说，low_bit运算可以通过对一个数取反然后加1，再与原数进行按位与的方式来实现。假设x的二进制表示中，最右边的1所在的位置是第k位 (即第k位为1，之后的都为0)，那么：

• 对于x的二进制表示中，k位之右的数，它们在x中都对应了0，所以对于这部分的数值，x & (-x) = 0。
• 对于x的二进制表示中，k之左的数值，它们在x中对应了0或者1，而在-x的二进制表示中，他们对应1或0， 与x的数值相反 (0对1，1对0)。因此，在进行按位与运算时，x中第k位之左的数值能够与-x中的相应位数值得到0。
• 对于第k位来说，x的第k位为1，-x的第k位也为1，因此，在进行按位与运算时，x中第k位的数值能够与-x中的第k为数值得到1。
• 因此x & (-x) = 2^k。

由此可见，low_bit运算确实可以得到x二进制表示中最右边的1所对应的数值。

改变二进制某位的数字

• 判断一个数字x二进制下第i位是不是等于1。（最低第0位）
• 方法：if (((1 << i) & x ) > 0)： 将1左移i位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果大于0，说明x第i位上是1，反之则是0。
• 将一个数字x二进制下第i位更改成1。
• 方法：x = x | (1 << i)： 证明方法与1类似。
• 将一个数字x二进制下第i位更改成0。
• 方法：x = x & ~ (1 << i)
• 把一个数字二进制下最靠右的第一个1去掉。
• 方法：x = x & (x − 1)