二进制和位运算

二进制

二进制是一种数值系统，仅使用两个数字：0 和 1。它是计算机和数字系统的基础，因为计算机使用二进制来表示和处理数据。在二进制中，每个位置代表一个权重，类似于十进制系统中的位置，但权重是 2 的幂次方。
例如，二进制数 1011 可以转换为十进制数如下：
1 × 2^3 = 8
0 × 2^2 = 0
1 × 2^1 = 2
1 × 2^0 = 1
将它们相加：8 + 0 + 2 + 1 = 11，因此二进制 1011 对应的十进制是 11。

C++. 无符号整数（unsigned）

无符号整数只使用二进制数表示非负数，因此所有的位都用于表示数值本身。
存储方式：直接使用二进制表示数值。
范围：unsigned int（假设为 32 位系统）范围是 0 到 2^32-1。(int 32位，long long 64位)
例子：
8 位无符号数 0000 0101 表示十进制的 5。
8 位无符号数 1111 1111 表示十进制的 255。

C++ 有符号整数（signed）

有符号整数使用最高位（称为符号位）表示正负号。通常，C++ 使用 补码（Two’s Complement）表示负数。
存储方式：
最高位是符号位：0 表示正数，1 表示负数。
正数和无符号数的存储方式相同。
负数通过取该数绝对值的补码来表示。
补码计算：
取反（即将每个位变为相反的值，0 变 1，1 变 0），然后加 1。
例子：
7二进制为(为了方便我们用4位表示)0111
取反：1000
加1：1001这个就是-7

假如我们知道一个负数的二进制怎么知道它是负几？先减1，然后再取反
例子：
1000
减1：0111
取反：1000(这个1000就是数值8)所以这个复数就是-8
8和-8的二进制是不同的我们用八位来分别表示：
8的二进制为0000 1000
-8的二进制为1111 1000

范围：int（假设为 32 位系统）范围是 (-2)^31-1到 2^31-1 即 -2147483648 到 2147483647。
例子：
8 位有符号数 0000 0101 表示十进制的 5。
8 位有符号数 1111 1111 表示十进制的 -1（补码表示）。
8 位有符号数 1111 1011 表示十进制的 -5：
原始数是 0000 0101（即 5），取反得到 1111 1010，加 1 得到 1111 1011。
3. 存储上的差异
无符号整数所有位都用于表示数值，范围更大。而有符号整数使用最高位表示符号，实际能表示的正整数范围比无符号整数小一半。
例子对比（8位整数）：
无符号：
0000 0000 表示 0。
1111 1111 表示 255。
有符号：
0000 0000 表示 0。
0111 1111 表示 127（最大正数）。
1000 0000 表示 -128（最小负数）。
1111 1111 表示 -1。

我们可以使用C++的bitset来写一个求一个int类型的二进制

bitset是 C++ 标准库中的一个模板类，用于表示和操作固定大小的位序列。它允许你高效地存储、操作和访问二进制位，常用于处理二进制数据、布尔数组或位掩码。

代码如下：

#include <iostream>
#include <bitset>
using namespace std;
void printBinary(int num) {// 使用bitset 直接输出 32 位二进制bitset<32> binary(num);cout << binary << endl;
}
int main() {int num;// 输入一个整数cout << "请输入一个整数：";cin >> num;// 输出该整数的32位二进制表示cout << "该整数的32位二进制表示为：";printBinary(num);return 0;
}

位运算

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以必要时要添加括号
|按位或和&按位与，它们与||逻辑或和&&逻辑与是不同的。

#include<iostream>
using namespace std;
int main()
{//1. 按位与（ & ）//按位与运算符对两个二进制数的每一位进行与运算，只有对应位都为1时，结果才为1，否则为0。int a1 = 5;  // 0101int b1 = 3;  // 0011int result1 = a1 & b1;  // 结果为 0001, 即 1cout << result1 << endl;//2. 按位或（ | ）//按位或运算符对两个二进制数的每一位进行或运算，只要有一位为1，结果就为1。int a2 = 5;  // 0101int b2 = 3;  // 0011int result2 = a2 | b2;  // 结果为 0111, 即 7cout << result2 << endl;//3. 按位异或（ ^ ）//按位异或运算符对两个二进制数的每一位进行异或运算，当对应位相同时，结果为0，位不同时，结果为1。int a3 = 5;  // 0101int b3 = 3;  // 0011int result3 = a3 ^ b3;  // 结果为 0110, 即 6cout << result3 << endl;//4. 按位取反（~）//按位取反运算符对一个二进制数的每一位进行取反操作，即0变为1，1变为0。对于有符号整数，结果使用补码表示。int a4 = 5;  // 0101int result4 = ~a4;  // 结果为 1010, 即 -6（按补码表示法）cout << result4 << endl;//5. 左移（ << ）//左移运算符将操作数的二进制位左移指定的位数，右侧用0填充。每左移一位，相当于乘以2。int a5 = 5;  // 0101int result5 = a5 << 1;  // 结果为 1010, 即 10cout << result5 << endl;//6. 右移（ >> ）//右移运算符将操作数的二进制位右移指定的位数，左侧根据符号位进行填充（对于无符号数，左侧填充0）。每右移一位，相当于除以2。int a6 = 5;  // 0101int result6 = a6 >> 1;  // 结果为 0010, 即 2cout << result6 << endl;return 0;
}

位运算的一些应用

1.因为位运算与二进制有关因此可以推广出许多与 2 的整数次幂有关的应用。

将一个数乘（除） 2 的非负整数次幂：

int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)return n << m;
}
int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)return n >> m;
}

注：我们平常写的除法是向 0 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别，如： -1 / 2 的值为 0 ，而 -1 >> 1 的值为 -1

2.取绝对值

int Abs(int n) {return (n ^ (n >> 31)) - (n >> 31);/* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)需要计算 n 和 -1 的补码，然后进行异或运算，结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
}

3.获取一个数二进制的某一位：

// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }

4.将一个数二进制的某一位设置为 0：

// 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

5.将一个数二进制的某一位设置为 1：

// 将 a 的第 b 位设置为 1 ，最低位编号为 0
int setBit(int a, int b) { return a | (1 << b); }

6.将一个数二进制的某一位取反：

// 将 a 的第 b 位取反 ，最低位编号为 0
int flapBit(int a, int b) { return a ^ (1 << b); }

7.求n的第k位数字:

 n >> k & 1

8.返回n的最后一位1：

lowbit(n) = n & -n

参考资料
参考资料