2.【入门】二进制和位运算
·
本文的网课内容学习自B站左程云老师的算法详解课程，旨在对其中的知识进行整理和分享~
一.二进制和位的概念
二进制
- 定义：二进制是一种以2为基数的记数系统，通常用0和1来表示。在计算机科学中，二进制是一种基本的数字系统，因为计算机的硬件和软件都是基于二进制的。
- 应用：二进制在计算机科学中被广泛应用，包括数据存储、数据传输、计算机编程等。在数据存储中，二进制数据被存储在计算机的内存和硬盘中。在数据传输中，二进制数据通过网络传输。在计算机编程中，二进制数据被用来表示数字、字符和其他数据类型。
位
- 定义：位是二进制数字系统中的最小单位，通常用0或1来表示。在计算机中，位是存储和处理数据的基本单位。
- 应用：位在计算机科学中被广泛应用，包括数据存储、数据传输、计算机编程等。在数据存储中，数据被存储在计算机的内存和硬盘中，每个存储单元可以存储一个或多个位。在数据传输中，数据通过网络传输，每个传输单元可以传输一个或多个位。在计算机编程中，位被用来表示数字、字符和其他数据类型。
二进制和位的关系
- 关系：二进制是一种数字系统，而位是二进制数字系统中的最小单位。在计算机中，二进制数据被存储和处理为位的序列。
- 应用：在计算机编程中，二进制数据可以通过位运算进行处理。位运算包括按位与、按位或、按位异或等操作，这些操作可以对二进制数据进行快速和高效的处理。
二.正数怎么用二进制表达
十进制正数转二进制数
除2取余法
- 原理：将十进制数除以2，记录余数，继续除以2直到商为0，最后将余数反向排列即为二进制数。
- 示例：将十进制数10转换为二进制。
- 10除以2得商5余0。
- 5除以2得商2余1。
- 2除以2得商1余0。
- 1除以2得商0余1。
- 反向排列余数得到二进制数1010。
二进制正数转十进制数
按权展开法
- 原理：将每位二进制数乘以2的幂次方，相加得到十进制数。
- 示例：二进制数1101转换为十进制。
三.负数怎么用二进制表达
十进制负数转二进制
- 步骤一：求绝对值的二进制原码
- 先将负数的绝对值转换为二进制数，这就是原码。例如，对于-5，先将5转换为二进制：00000101。
- 步骤二：求反码
- 将原码的每一位取反，得到反码。例如，-5的反码为：11111010。
- 步骤三：求补码
- 在反码的基础上再加1，得到补码。例如，-5的补码为：11111011。
- 步骤四：确定符号位
- 在二进制数中，最高位通常用作符号位，0表示正数，1表示负数。因此，-5的完整二进制表示为：11111011。
二进制负数转十进制
- 步骤一：判断符号位
- 若最高位为1，则表示该数为负数，需要进行转换。
- 步骤二：求补码的反码
- 将补码的每一位取反，得到反码。例如，对于二进制数11111011，其反码为11111010。
- 步骤三：求原码
- 在反码的基础上再加1，得到原码。例如，11111010的原码为11111011。
- 步骤四：转换为十进制数
- 将原码转换为十进制数，并加上负号。例如，11111011转换为十进制数为-5。
特殊情况
- -1的补码：-1的原码为00000001，反码为11111110，补码为11111111。
- 最小负整数的表示：在8位二进制系统中，最小的负整数是-128，其补码表示为10000000。
四.打印二进制：直接定义二进制、十六进制的变量
二进制和十六进制的转换
二进制转十六进制
- 方法：将二进制数从右到左每四位一组进行划分，不足四位的在左边补0，然后将每组二进制数转换为对应的十六进制数。
- 举例：将二进制数1101100转换为十六进制数。先将其按四位一组划分：0110 1100，然后对照二进制与十六进制数的对应表，0110对应6，1100对应C，所以1101100转换为十六进制数是6C。
十六进制转二进制
- 方法：将每位十六进制数转换为对应的四位二进制数。
- 举例：将十六进制数2B转换为二进制数。2对应的二进制数是0010，B对应的二进制数是1011，所以2B转换为二进制数是00101011。
特殊情况
- -1的补码：-1的原码为00000001，反码为11111110，补码为11111111。
- 最小负整数的表示：在8位二进制系统中，最小的负整数是-128，其补码表示为10000000。
打印二进制
package binarysystem;
public class BinaryPrint {
// 打印一个int类型的数字，32位进制的状态
// 左侧是高位，右侧是低位
public static void printBinary(int num) {
for (int i = 31; i >= 0; i--) {
// 下面这句写法，可以改成 :
// System.out.print((a & (1 << i)) != 0 ? "1" : "0");
// 但不可以改成 :
// System.out.print((a & (1 << i)) == 1 ? "1" : "0");
// 因为a如果第i位有1，那么(a & (1 << i))是2的i次方，而不一定是1
// 比如，a = 0010011
// a的第0位是1，第1位是1，第4位是1
// (a & (1<<4)) == 16（不是1），说明a的第4位是1状态
System.out.print((num & (1 << i)) == 0 ? "0" : "1");
}
System.out.println();
}
public static void main(String[] args) {
// 非负数
int a = 78;
System.out.println(a);
printBinary(a);
System.out.println("===a===");
// 负数
int b = -6;
System.out.println(b);
printBinary(b);
System.out.println("===b===");
// 直接写二进制的形式定义变量
int c = 0b1001110;
System.out.println(c);
printBinary(c);
System.out.println("===c===");
// 直接写十六进制的形式定义变量
// 0100 -> 4
// 1110 -> e
// 0x4e -> 01001110
int d = 0x4e;
System.out.println(d);
printBinary(d);
System.out.println("===d===");
}
}
五.常见的位运算（|、&、^、~、<<、>>、>>>）
按位或运算
- 定义：按位或运算通常用符号“|”表示，是一种二元位运算符。它的运算规则是：对两个操作数的每一位进行或运算，如果对应的两位中有一位为1，则结果位为1；只有当两位都为0时，结果位才为0。
- 示例：
- 3 | 5：将3和5转换为二进制数，即0000 0011和0000 0101，然后按位或运算得到0000 0111，转换为十进制数为7。
- 应用场景：按位或运算常用于对二进制数进行特定位置的置1操作。例如，可以使用按位或来设置某个字节中的特定标志位。
按位与运算
- 定义：按位与运算通常用符号“&”表示，是一种二元位运算符。它的运算规则是：对两个操作数的每一位进行与运算，如果对应的两位都为1，则结果位为1；否则，结果位为0。
- 示例：
- 3 & 5：将3和5转换为二进制数，即0000 0011和0000 0101，然后按位与运算得到0000 0001，转换为十进制数为1。
- 应用场景：按位与运算常用于对二进制数进行特定位置的清零操作。例如，可以使用按位与来清除某个字节中的特定标志位。
- 运算规则
异或运算
- 定义：异或运算通常用符号“^”表示，他的运算规则是：如果两个操作数相同（都为0或都为1），则结果为0；如果两个操作数不同（一个为0，另一个为1），则结果为1。
- 真值表
|
A
|
B
|
A ^ B
|
|
0
|
0
|
0
|
|
0
|
1
|
1
|
|
1
|
0
|
1
|
|
1
|
1
|
0
|
性质
- 交换律：A ^ B = B ^ A
- 结合律：(A ^ B) ^ C = A ^ (B ^ C)
- 自反性：A ^ A = 0
- 与0异或不变：A ^ 0 = A
应用
- 数据加密：异或运算可以用于简单的数据加密和解密。例如，将明文与密钥进行异或运算得到密文，再将密文与密钥进行异或运算即可得到明文。
- 数据校验：在数据传输过程中，可以通过异或运算对数据进行校验。发送方将数据与校验码进行异或运算得到结果，接收方再将接收到的数据与校验码进行异或运算，如果结果为0，则说明数据传输正确。
- 数字电路设计：异或运算在数字电路中被广泛应用，如加法器、减法器、奇偶校验器等电路的设计。
- 编程中的应用：在编程中，异或运算可以用于交换两个变量的值，而不需要使用临时变量。
左移运算符（<<）
- 作用：将一个数的二进制表示向左移动指定的位数，右边空出的位用0填充。
- 示例：在Java中，5 << 2表示将5的二进制数101向左移动2位，得到10100，即20。
右移运算符（>>）
- 作用：将一个数的二进制表示向右移动指定的位数，左边空出的位根据原数的符号进行填充，正数用0填充，负数用1填充。
- 示例：在Java中，10 >> 2表示将10的二进制数1010向右移动2位，得到10，即2。
无符号右移运算符（>>>）
- 作用：将一个数的二进制表示向右移动指定的位数，左边空出的位始终用0填充，不考虑原数的符号。
- 示例：在Java中，-10 >>> 2表示将-10的二进制数（补码形式）向右移动2位，得到一个较大的正数。
应用场景
- 优化乘法和除法运算：在某些情况下，左移一位相当于乘以2，右移一位相当于除以2。例如，在计算2的幂次方时，可以使用左移运算符来提高计算效率。
- 位操作和数据处理：左移右移运算符常用于位操作，如设置或清除二进制数中的特定位，以及对数据进行加密和解密等操作。
- 内存管理和数据存储：在内存管理中，左移右移运算符可以用于计算内存地址和数据偏移量等。
package binarysystem;
import static binarysystem.BinaryPrint.printBinary;
public class BitwiseOperation {
public static void main(String[] args) {
// | & ^
int g = 0b0001010;
int h = 0b0001100;
printBinary(g | h);
printBinary(g & h);
printBinary(g ^ h);
System.out.println("===g、h===");
// <<
int i = 0b0011010;
printBinary(i);
printBinary(i << 1);
printBinary(i << 2);
printBinary(i << 3);
System.out.println("===i << ===");
// 非负数 >> >>>，效果一样
printBinary(i);
printBinary(i >> 2);
printBinary(i >>> 2);
System.out.println("===i >> >>>===");
// 负数 >> >>>，效果不一样
int j = 0b11110000000000000000000000000000;
printBinary(j);
printBinary(j >> 2);
printBinary(j >>> 2);
System.out.println("===j >> >>>===");
// 非负数 << 1，等同于乘以2
// 非负数 << 2，等同于乘以4
// 非负数 << 3，等同于乘以8
// 非负数 << i，等同于乘以2的i次方
// ...
// 非负数 >> 1，等同于除以2
// 非负数 >> 2，等同于除以4
// 非负数 >> 3，等同于除以8
// 非负数 >> i，等同于除以2的i次方
// 只有非负数符合这个特征，负数不要用
int k = 10;
System.out.println(k);
System.out.println(k << 1);
System.out.println(k << 2);
System.out.println(k << 3);
System.out.println(k >> 1);
System.out.println(k >> 2);
System.out.println(k >> 3);
System.out.println("===k===");
}
}
六.注意|、&是位运算或、位运算与；||、&&是逻辑或，逻辑与，两者是有区别的
逻辑或与按位或的区别
- 逻辑或：操作数通常为布尔值，结果也是布尔值，用于判断条件是否满足。
- 按位或：操作数为二进制数，结果也是二进制数，用于对二进制数的位进行操作。
逻辑与与按位与的区别
- 逻辑与：操作数通常为布尔值，结果也是布尔值，用于判断条件是否同时满足。
- 按位与：操作数为二进制数，结果也是二进制数，用于对二进制数的位进行操作。
穿透性区别
- 按位与或的穿透性：按位与或运算会对操作数的每一位进行运算，不会因为某一位的结果而提前结束运算。例如，对于按位与运算1010 & 1100，会对每一位进行比较，得到结果1000。
- 逻辑与或的穿透性：逻辑与或运算具有短路特性。对于逻辑与（&&），如果第一个操作数为假，那么就不会再计算第二个操作数，因为无论第二个操作数的值如何，结果都为假。例如，对于表达式 (false && someFunction())，someFunction() 不会被执行。对于逻辑或（||），如果第一个操作数为真，那么就不会再计算第二个操作数，因为无论第二个操作数的值如何，结果都为真。例如，对于表达式 (true || someFunction())，someFunction() 不会被执行。
package binarysystem;
public class DifferencesOfOperator {
public static void main(String[] args) {
// 可以这么写 : int num = 3231 | 6434;
// 可以这么写 : int num = 3231 & 6434;
// 不能这么写 : int num = 3231 || 6434;
// 不能这么写 : int num = 3231 && 6434;
// 因为 ||、&& 是 逻辑或、逻辑与，只能连接boolean类型
// 不仅如此，|、& 连接的两侧一定都会计算
// 而 ||、&& 有穿透性的特点
System.out.println("test1测试开始");
boolean test1 = returnTrue() | returnFalse();
System.out.println("test1结果，" + test1);
System.out.println("test2测试开始");
boolean test2 = returnTrue() || returnFalse();
System.out.println("test2结果，" + test2);
System.out.println("test3测试开始");
boolean test3 = returnFalse() & returnTrue();
System.out.println("test3结果，" + test3);
System.out.println("test4测试开始");
boolean test4 = returnFalse() && returnTrue();
System.out.println("test4结果，" + test4);
System.out.println("===|、&、||、&&===");
}
public static boolean returnTrue() {
System.out.println("进入了returnTrue函数");
return true;
}
public static boolean returnFalse() {
System.out.println("进入了returnFalse函数");
return false;
}
}
七.相反数
package binarysystem;
import static binarysystem.BinaryPrint.printBinary;
public class OppositeNumber {
public static void main(String[] args) {
// ~、相反数
int a = 78;
System.out.println(a);
printBinary(a);
printBinary(~a);
int e = ~a + 1;
System.out.println(e);
printBinary(e);
System.out.println("===e===");
}
}
八.正数最小值的特殊性（取绝对值还是自己）
package binarysystem;
import static binarysystem.BinaryPrint.printBinary;
public class PeculiarityOfMIN_VALUE {
public static void main(String[] args) {
// int、long的最小值，取相反数、绝对值，都是自己
int f = Integer.MIN_VALUE;
System.out.println(f);
printBinary(f);
System.out.println(-f);
printBinary(-f);
System.out.println(~f + 1);
printBinary(~f + 1);
System.out.println("===f===");
}
}
九.为什么这么设计二进制？
位运算可以保证在数据溢出的情况下也可以得到正确的结果。同样的，在这样设计的负数条件下，加法逻辑就不需要再通过条件判断来计算有负数参与的式子，大大加快了加法的运算速率
十.关于溢出
自己确保自己的调用所得到的结果不会溢出，
一定是自己确保的，计算机不会给你做检查
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
34
0- 0
已为社区贡献4条内容
所有评论(0)