二进制与位运算

（一）进制转化

（1）任意进制转化为十进制

// 二进制转十进制
string num = "10010"; // 需要转化的二进制数
int ans = stoi(num, nullptr, 2); // 2就是num的进制，ans 就是答案，ans = 18 = num

// 十六进制转十进制
num = "14A";
ans = stoi(num, nullptr, 16); // ans = 330 = num

// 其他进制同理

（2）十进制转化为任意进制（2~9进制）

string calc(int num, int x) { // 将十进制数num，转化为x进制数
    string ans = ""; // 记录结果
    while(num) {     // 只要num不为0
        ans += to_string(num % x); // 记录余数
        num /= x;              
    }
    reverse(ans.begin(), ans.end()); // 反转ans字符串
    return ans;  // 返回结果字符串
}

int num = 10; // 将10转化为2,8,6进制
cout << calc(num, 2); // 输出：1010 
cout << calc(num, 8); // 输出：12
cout << calc(num, 6); // 输出：14

将 num 不断模 x 的结果放入答案， 同时 num 不断除 x, 只要 num 不为 0。结果反转就是答案。证明略。

（二）位运算

（1）&（按位与）

1、规则

二进制相应位都为1则为1，否则为0

例如：

111010  // 58
100100  // 36
------  // & （按位与）
100000  // 32

2、判断奇偶

if(n & 1) {
    cout << "n为奇数";
} else {
    cout << "n为偶数";
}

n & 1 若为真， n 的二进制位最低位为 1， 就是奇数，否则为偶数

3、取出最后一位的 1

int lowbits(int x) {
    return x & (-x);  // 返回x最后一位1对应的数
}

$10_{10}$ 的二进制为 $1010_2$ （下表为2表示二进制数）
$lowbits(10_{10}) = 10_2 = 2_{10}$
所以 $lowbits(10) = 2$

4、判断一个数是否为2的幂

int num = 16;
if(!num && num == lowbits(num)) { // num不为0 && num的二进制数只有一位1 
    cout << "是2的幂";
} else {
    cout << "不是2的幂"
}
// 输出：是2的幂

若x == lowbits(x)，说明x的最低为的1对应的十进制数也为x，说明x的二进制位只有一个1，符合2的幂的特点。0除外，因为lowbits(0) = 0，而0不是2的幂。

（2）| （按位或）

1、规则

二进制相应位只要有一个为1则为1，否则为0

例如：

100101  // 37
101000  // 40
------  // | （按位或）
101101  // 45

2、集合合并

给定两个集合，合并这两个集合：

int A = 0b10010;
int B = 0b10111;
int C = A | B;
cout << C;  // 输出：10111