🎈🎈进制与位运算
进制详解
包括二进制、八进制、十进制和十六进制, 计算机由电路构成, 只有0/1两种状态, 所以采用的是二进制
- 二进制
由0 和 1组成, 计算机内部都是二进制的形式存储的。 进行加法运算的时候逢二进一, 减法运算的时候借一当二。在java中0b开头表示二进制值
- 十进制
由0~9的数字组成, 加法计算时逢十进一, 减法计算时借一当十。十进制是人类发展中自然形成的
- 八进制
由0~7的数字组成, 加法计算时逢八进一, 减法计算时借一当八。java中要求第一位是0开始
- 十六进制
由0~9,A(10),B(11),C(12),D(13),E(14),F(15)(不区分大小写)组成, 加法计算时逢十六进一, 减法计算时借一当十六。java中要求以0x开始
进制互相换算
- 二进制 -> 十进制
假设一个二进制是 1011(3210), 从右往左开始分别是 0、1、2、3 位, 那么它的十进制值为:
java
1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 => 8 + 0 + 2 + 1 => 13- 十进制 -> 二进制
假设一个十进制是 13, 一种方法是除二反序取余法, 计算如下:
java
13/2 = 6 余 1
6/2 = 3 余 0
3/2 = 1 余 1
1/2 = 0 余 1
反序取余数值, 结果是: 1101另一种计算如下:
java
13 => 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0- 二进制 -> 八进制
假设一个二进制是 10110101, 从右往左每三位一组(不足补 0, 二进制三位最大值是 7(111), 最小值是 0, 逢八进一, 这也是八进制的由来)分别是:
java
010 110 101 对应的结果是: 010(2) 110(6) 101(5) => 265- 二进制 -> 十六进制
假设一个二进制是 110110101, 从右往左每四位一组(不足补 0, 二进制四位数最大值是 15(1111), 最小值是0, 逢十六进一， 也是十六进制的由来)分别是:
java
0001 1011 0101 对应的结果是: 1 11(B) 5 => 1B5位运算
与运算
两个操作数都是1, 结果是1, 否则是0
java
// 17
byte a = 0b00010001;
// 10010001 -> 10010000 -> 11101111 -> -(64+32+8+4+2+1) -> -111
byte b = (byte) 0b10010001;
/*
* 都1取1 否则取0
* 0001 0001
* & 1001 0001
* ————————————
* 0001 0001
* 17
*/
System.out.println("移位&运算: " + (a & b)); // 17或运算
两个操作数有一个是1, 结果是1, 否则是0
java
// 17
byte a = 0b00010001;
// 10010001 -> 10010000 -> 11101111 -> -(64+32+8+4+2+1) -> -111
byte b = (byte) 0b10010001;
/*
* 有1为1 无1为0
* 0001 0001
* | 1001 0001
* —————————————
* 1001 0001
* —————————————
* 原 1110 1111
* -111
*/
System.out.println("移位|运算: " + (a | b));// -111异或
两个操作数相同则为0, 不相同则为1
java
// 17
byte a = 0b00010001;
// 10010001 -> 10010000 -> 11101111 -> -(64+32+8+4+2+1) -> -111
byte b = (byte) 0b10010001;
/*
* 相同为0 不同为1
* 0001 0001
* ^ 1001 0001
* ————————————
* 1000 0000
* ————————————
* -128(-0)
*/
System.out.println("移位^运算: " + (a ^ b)); // -128取反运算
对操作数取相反值
java
// 10010001 -> 10010000 -> 11101111 -> -(64+32+8+4+2+1) -> -111
byte b = (byte) 0b10010001;
/* 直接取反
* ~ 1001 0001
* ————————————
* 0110 1110
* 110
*/
System.out.println("移位取反运算: " + (~b));// 110移位运算
包括左移<< 和 右移 >>, 1 << 2 表示1左移2位, 1 >> 1 表示1右移1位
java
101011001
<< 2
——————————————
101100100
如果左移没有改变最高位(符号位), 那么将一个整数左移1位相当于乘以2, 编译器做移位比乘法快的多。
101011001
>> 2
——————————————
001010110
同理如果没有改变最高位, 那么右移一位相当于除以2负数的二进制
负数的计算
因为负数的二进制表达以及位运算的特殊性, 所以单独提出来解释, 在此之前需要了解机器数, 真值, 原码, 反码, 补码的概念
机器数
一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1
java+1 -> 0000 0001 -1 -> 1000 0001真值
因为第一位是符号位, 所以机器数的形式值 ≠ 真正的数值。 比如 1000 0001 其真值是 -1, 而其形式值是129(转成十进制: 2^7 + 2^0)。我们将带符号位的机器数对应的真正数值称为机器数的真值
原码
原码就是真值的绝对值加上符号位(最高位), 正数用0, 负数用1表示
java// 假设8bit的二进制的原码 +1 -> 0 0000001 -1 -> 1 0000001反码
正数的反码是其本身, 负数的反码是在原码的基础上, 保持符号位不变, 其余的位执行取反操作
java// 假设8bit的二进制的反码 +1 -> 0 0000001 -> 0 0000001 -1 -> 1 0000001 -> 1 1111110补码
正数的补码就是其本身, 负数的补码就是在其反码的基础上 + 1
java// 假设8bit的二进制的补码 //真值 原码 反码 补码 +1 -> 0 0000001 -> 0 0000001 -> 0 0000001 -1 -> 1 0000001 -> 1 1111110 -> 1 1111111为什么要使用原码, 反码和补码
java1. 首先在计算机中, 为了计算机运算设计的更简单, 符号位也参与计算, 其次计算机是只有加法没有减法的, 减法是用正数加负数来实现的。 2. 如果我们分别使用原码, 反码和补码进行1+(-1)大小是8bit的计算: 1 1 1 (-1) + (-1) + (-1) + (-1) + (-127) —————————————— —————————————— —————————————— —————————————— 原码 0000 0001 反码 0000 0001 补码 0000 0001 补码 1111 1111 原码 1000 0001 反码 1111 1110 补码 1111 1111 补码 1000 0001 —————————————— —————————————— —————————————— —————————————— 1000 0010 反码 1111 1111 补码 10000 0000 补码 11000 0000 —————————————— —————————————— —————————————— —————————————— -2 原码 1000 0000 原码 0000 0000 原码 1000 0000 —————————————— —————————————— —————————————— -0 0 -128 3. 综合上面的结果, 原码的结果肯定是不对的, 反码的结果问题在于+0 & -0, 而补码的结果是正确的, 但是还有一个-0, 通过计算发现(-1) + (-127)的正常结果是-128, 而补码的计算结果是1000 0000, 所以我们-128的补码由1000 0000(需要注意的是-128没有原码和反码)表示, 这样能够解决+0&-0的问题 4. 这样也能解释为什么在java语言中, 基本数据类型byte的范围是[-128, 127], 因为它们存储的时候是用补码(-0用于表示-128), 程序运行展示的数据是原码的十进制(需要补码->原码->十进制转换)。如果是使用反码表示, 范围就是[-2^(n-1)+1...-0, +0...+2^(n-1)-1]。这里有个特殊的类型: char, 因为它没有负数, 所以范围是[0, 2^16-1]java 中进制的表示
java// 定义基本数据类型的数据, 其大小不能超过默认大小, 比如byte -> 8bit System.out.println("--------------------------binary------------------------------------ "); // java中0b开头表示二进制 byte a = 0b00000011; // 补码: 0 0000011 -> 反码: 0 0000010 -> 原码: 0 0000010 -> 十进制展示: 3 System.out.println("positive binary: " + a); byte b = (byte) 0b10000001; // 补码: 1 0000001 -> 反码: 1 0000000 -> 原码: 1 1111111 -> 十进制展示: -127 System.out.println("negative binary: " + b); System.out.println("---------------------------Octal------------------------------------ "); // 如果八进制存在大于8的数字肯定是不对的 // 补码: 0000 0000 0000 0000 0000 0000 0001 0100 -> 原码: 0000 0000 0000 0000 0000 0000 0001 0100 int c = 014; System.out.println("positive Octal -> Binary: " + Integer.toBinaryString(c)); // 补码: 1000 0000 0000 0000 0000 0000 0001 0100 -> 原码: 1111 1111 1111 1111 1111 1110 1100 int d = -014; System.out.println("negative Octal -> Binary: " + Integer.toBinaryString(d)); System.out.println("---------------------------Hex------------------------------------ "); // 补码: 0000 0000 0000 0000 0000 0000 0001 1111 -> 原码: 0000 0000 0000 0000 0000 0000 0001 1111 int e = 0x1f; System.out.println("positive hex -> Binary: " + Integer.toBinaryString(e)); // 补码: 1000 0000 0000 0000 0000 0000 0001 1111 -> 原码: 1111 1111 1111 1111 1111 1110 0001 int f = -0x1f; System.out.println("negative hex -> Binary: " + Integer.toBinaryString(f));
负数的移位
移位运算分为有符号移位和无符号移位, 分别用 << >> & <<< >>> 表示. 在 java 语言中, 只有 <<, >>, >>> 三种, 使用 <<< 编辑器会报错
java
/* java 不支持 无符号左移, 支持有符号左右移位&无符号右移 */
System.out.println("------------------------正数移位------------------------");
// 0000 0011 << 2 -> 0000 1100 -> 12
// 正数左移 低位补0
byte a = 0b00000011 << 2;
System.out.println("有符号位正数左移2位: " + a);
// 0000 0111 >> 0000 0001 -> 1
// 正数右移 高位补0
byte b = 0b00000111 >> 2;
System.out.println("有符号位正数右移2位: " + b);
// 0000 1111 >>> 0000 0001 -> 1
// 无符号右移 高位补0
byte c = 0b00001111 >>> 3;
System.out.println("无符号位正数右移3位: " + c);
System.out.println("-------------------------二进制负数移位------------------------");
// 补码: 1000 1011 -> 左移2位 0010 1100 -> 十进制 2^5+2^3+2^2 -> 44
// 负数先移位后计算原码, 负数左移低位补0(包括符号位), 负数左移有正有负, 一直左移最终会变成0
byte d = (byte) (0b10001011 << 2);
System.out.println("有符号位负数左移2位: " + d);
// 补码: 1000 1011 -> 右移2位 0010 0010 -> 十进制 2^5 + 2^1 -> 34
// 负数右移(包括符号位), 高位补1, 如果一直右移最终会变成-1
byte e = (byte)(0b10001011 >> 2);
System.out.println("有符号位负数右移2位: " + e);
//补码: 1000 1011 -> 右移3位 0001 0001 -> 十进制 2^4 + 2^0 -> 17
// 负数无符号右移(包括符号位), 高位补0
byte f = (byte)(0b10001011 >>> 3);
System.out.println("无符号负数右移3位: " + f);
System.out.println("-------------------------十进制负数移位------------------------");
// 十进制 -> 补码 -> 移位 -> 原码 -> 十进制
// -1 -> 1000 0000 0000 0000 0000 0000 0000 0001 原码
// -> 1111 1111 1111 1111 1111 1111 1111 1111 补码
// -> 0111 1111 1111 1111 1111 1111 1111 1111 移位1
// -> 2^30 + 2^29 + ... + 2 + 2^0 -> 2147483647
System.out.println(-1 >>> 1);- 移位对照表
| 有符号左移 << | 有符号右移 >> | 无符号右移 >>> | |
|---|---|---|---|
| 正数 | 低位补 0 | 高位补 0 | 高位补 0 |
| 负数 | 低位补 0 | 高位补 1 | 高位补 0 |
- 在Java代码中，正常的数字都是代表着这个数的十进制，比如
byte a = 1，而二进制用0b、八进制用0、十六进制用0x开头。- 如果代码中数字是二进制数数a，移位需要遵循:
a(补码) -> 移位 -> 十进制(计算的时候不包括符号位)，移位的时候包括符号位。- 如果代码中数字是十进制数b，移位需要遵循:
b(十进制) -> b二进制原码 -> b二进制补码 -> 移位 -> 移位后补码 -> 移位后反码 -> 移位后原码 -> 十进制(计算的时候不包括符号位)。- 有符号负数左移的时候并不能保证还是正数, 有符号负数右移一直是负数。
进制移位小技巧
- 取模运算(HashMap)
java
x % 2^n = x & (2^n-1)
ex:
7 % 2^2 = 3
7 & (2^2 - 1) = 3
0000 0111
& 0000 0011
————————————
0000 0011需要注意的是: 被除数必须是2^n，否则该公式不成立
- 绝对值运算(HashTable)
java
|x| = x & 0x7FFFFFFF
ex:
|-1| = -1 & 0x7FFFFFFF
1111 1111 1111 1111 1111 1111 1111 1111
& 0111 1111 1111 1111 1111 1111 1111 1111
——————————————————————————————————————————
0000 0000 0000 0000 0000 0000 0000 0001需要注意数值越界问题