二进制和位运算

算法 算法 二进制 位运算
发布时间 :
字数:3.1k 阅读 : 评论:
  1. 一、二进制基础
    1. 1、二进制与十进制的转换
    2. 2、有符号数与无符号数
    3. 3、源码、反码与补码
    4. 4、十进制负数如何转换成二进制数
    5. 5、负数二进制数如何转成十进制数
    6. 6、Java如何定义一个二进制数
    7. 7、二进制数转十六进制数
  2. 二、位运算基础
    1. 1、相反数
      1. 1.1、如何得到一个数的相反数？
    2. 2、常见的位运算(|、&、^、~、<<、>>、>>>)
      1. 2.1、按位或运算符(I)
      2. 2.2、按位与运算符(&)
      3. 2.3、按位异或运算符(^)
      4. 2.4、按位取反(~)
      5. 2.5、左移(<<)
      6. 2.6、带符号右移(>>)
      7. 2.7、无符号右移(>>>)
  3. 三、二进制如此设计的原因
  4. 四、解析二进制打印函数
    1. 1、二进制打印函数如下
    2. 2、解析

一、二进制基础

1、二进制与十进制的转换

  • 举例：0101 –> 5

    二进制[0101] 表示: 0 * 23 + 1 * 22 + 0 * 21 + 1 * 20 = 5

计算结果正好等于十进制数：5

上面的计算使用的是4位二进制数来表示的，4位二进制数可表示的10进制数有 24 = 16 个，表示十进制数的范围是 0 ~ 24 -1 ，即：0 ~ 15 。

2、有符号数与无符号数

  • 无符号数

    一个二进制数上的所有 0 和 1 都表示数字。

  • 有符号数

    二进制数上最左边的数字表示：符号位

    • 0：表示该二进制为正数
    • 1：表示该二进制为负数

举例说明：

比如一个4位长度的二进制数，它能表示的十进制数依然有 24 = 16 个，表示的正数只有 23 个，负数也是 23,即：

  • 正数：0000 ~ 0111

    十进制表示：0 ~ 7

  • 负数：1111 ~ 1000 【计算机中负数的表示，与正数不同】

    十进制表示：-1 ~ -8

3、源码、反码与补码

  • 应用范围：源码、补码、反码只能应用在整数中：正整数、负整数

  • 在正整数中：源码 =反码 =补码

  • 在负整数中：如果是负数，将源码的符号位不变，其余各位取反，得到反码。

    • 如果是负数，将反码加1，得到补码

  • 举例：int a = 3 ;

int a = 3 ; // int整型为4字节，32个bit位
//源码：00000000 00000000 00000000 00000011
//反码：00000000 00000000 00000000 00000011
//补码：00000000 00000000 00000000 00000011
//因为是正整数所以 源码=反码=补码
  • 举例：int a = -3 ;
int a = -3 ; // int 为整型4个字节32个bit位
//因为是负数，所以最高位是 1
//源码：10000000 00000000 00000000 00000011
//源码符号位不变，其余各个位按位取反，得到反码
//反码：11111111 11111111 11111111 11111100
//反码+1，得到补码
//补码：11111111 11111111 11111111 11111101

4、十进制负数如何转换成二进制数

十进制负数转成二进制数的转换逻辑大致是，先将负数取正，转成二进制数，再减1，然后取反。下面举例说明转换过程：

  • 示例1，十进制数：-1
    • 先将 -1 转成 正数 1，并得到正数 1 的二进制数 0001
    • 再将二进制数 0001 减去 1 ，得到二进制数 0000
    • 然后将二进制数 0000 取反，得到 二进制数 1111
    • 此时就得到了 -1 的 二进制表示：1111
  • 示例2，十进制数：-7
    • 先将 -7 转成 正数 7，并得到正数 7 的二进制数 0111
    • 再将二进制数 0111 减去 1 ，得到二进制数 0110
    • 然后将二进制数 0110 取反，得到 二进制数 1001
    • 此时就得到了 -7 的 二进制表示：1001
  • 示例3，十进制数：-8
    • 先将 -8 转成 正数 8，并得到正数 8 的二进制数 1000
    • 再将二进制数 1000 减去 1 ，得到二进制数 0111
    • 然后将二进制数 0111 取反，得到 二进制数 1000
    • 此时就得到了 -8 的 二进制表示：1000

注意：上面的方法得到的都是对应负数的二进制补码。

5、负数二进制数如何转成十进制数

根据有符号数的定义：如果一个二进制数表示一个负数，那么在这个二进制数中，最左侧的数一定是1。确定符号位是否为负数，是后面进行转换的前提。

负数二进制数转十进制数 与 负数十进制数转二进制的过程正好相反，转换逻辑大致是，先将负数二进制数整体取反，然后再加1，得到十进制数的二进制表示，转成十进制数，再将10进制数取反，得到负的十进制数。

  • 示例1，二进制数：1001
    • 首位是1，表示它是一个负数
    • 先将二进制数 1001 整体取反得到 0110
    • 再将取反后的二进制数 0110 + 1 得到二进制数 0111
    • 0111 表示十进制数 7
    • 再将十进制数 7 取反，得到负数 -7
    • 所以二进制数 1001 对应的十进制数为 -7
  • 示例2，二进制数：1000
    • 首位是1，表示它是一个负数
    • 先将二进制数 1000 整体取反得到 0111
    • 再将取反后的二进制数 0111 + 1 得到二进制数 1000
    • 1000 表示十进制数 8
    • 再将十进制数 8 取反，得到负数 -8
    • 所以二进制数 1000 对应的十进制数为 -8

1000 在无符号二进制数中表示 8，在有符号二进制数中表示 -8 。

上面的方法，都是使用负数的补码进行运算的，1001、1000 都是补码

6、Java如何定义一个二进制数

int c = 0b0000101110; // 使用 0b 开头，后面是 0和1 定义一个二进制数
System.out.println(c);

16进制数字定义使用 0x 开头，例如：0x4e

7、二进制数转十六进制数

  • 概念：

    • 二进制是由数字0和1组成，十六进制是由：[ 0、1、2、3、4、5、6、7、8、9、a、b、c、d、e、f ] 共16个数字和字母组成，逢十六进一。

  • 二进制数与十六进制数的对照关系

    • 二进制数 –> 十六进制数
    二进制数 十六进制数
    0000 0
    0001 1
    0010 2
    0011 3
    0100 4
    0101 5
    0110 6
    0111 7
    1000 8
    1001 9
    1010 a
    1011 b
    1100 c
    1101 d
    1110 e
    1111 f

由上表可以进下面具体的进制转换了，举例说明。

  • 二进制数：0b01100111
    • 0b 表示这是一个二进制数
    • 前四位 0110 对应十六进制数 6
    • 后四位 0111 对应十六进制数 7
    • 所以这个二进制数对应十六进制数为 0x67， 0x 表示这是一个十六进制数
  • 二进制数：0b01101111
    • 0b 表示这是一个二进制数
    • 前四位 0110 对应十六进制数 6
    • 后四位 1111 对应十六进制数 f
    • 所以这个二进制数对应十六进制数为 0x6f , 0x 表示这是一个十六进制数

二、位运算基础

1、相反数

  • 概念：相反数是一个数学术语，指绝对值相等，正负号相反的两个数互为相反数。
  • 举例：1 的相反数是 -1，78 的相反数是 -78

1.1、如何得到一个数的相反数？

答案：需要对一个数进行 取反 ，再加1 即可得到一个数的相反数。

// ~、相反数
System.out.println(a); // 打印结果：78
printBinary(a); // 打印结果：00000000000000000000000001001110
printBinary(~a); // 打印结果：11111111111111111111111110110001
int e = ~a + 1;
System.out.println(e); // 打印结果：-78
printBinary(e); // 打印结果：11111111111111111111111110110010
System.out.println("===e===");

注意：int、long的最小值，取相反数、绝对值，都是自己

2、常见的位运算(|、&、^、~、<<、>>、>>>)

2.1、按位或运算符(I)

  • 参加运算的两个对象，按二进制位进行“或”运算。

  • 运算规则:0|0=0；0|1=1；1|0=1；1|1=1。

    • 即:参加运算的两个对象只要有一个为1，其值为1.
    • 例如:3|5 即 0000 0011 | 0000 0101=0000 0111 因此，3|5的值得7.

    负数按补码形式参加按位或运算。

2.2、按位与运算符(&)

  • 参加运算的两个数据，按二进制位进行“与”运算。

  • 运算规则:0&0=0;0&1=0;1&0=0;1&1=1;

    • 即:两位同时为“1”，结果才为“1”，否则为0
    • 例如:3&5 即 0000 0011 & 0000 0101 = 0000 0001 因此，3&5的值得1.

    负数按补码形式参加按位与运算。

2.3、按位异或运算符(^)

  • 参加运算的两个数据，按二进制位进行“异或”运算
  • 运算规则:0^0=0; 0^1=1; 1^0=1; 1^1=0;
    • 即:参加运算的两个对象，如果两个相应位为“异”(值不同)，则该位结果为1，否则为0.
    • 例如:3&5 即 0000 0011 ^ 0000 0101 = 0000 0110 因此，3^5的值得6.
  • 任何数与0异或都等于自身
  • 任何数与自己异或都为0

负数按补码形式参加按位与运算。

2.4、按位取反(~)

  • 运算规则：按照二进制位是0则变为1，是1则变成0
    • 即：~1 = 0 ~0 = 1
    • 符号位也取反
  • 举例
    • 78 的二进制表示：00000000000000000000000001001110
    • 取反后二进制表示：11111111111111111111111110110001

2.5、左移(<<)

  • 左移表示的是某数的各二进位全部左移若干位，高位丢弃，低位补0
// 举例:
print(123);			// 00000000000000000000000001111011
print(123 << 1);	// 00000000000000000000000011110110	
// 整体左移1位，高位丢弃，低位补0
  • 应用
// 左移1位相当于在原数的基础上乘以2
System.out.println(123);	// 123
System.out.println(123<<1);	// 246
// 左移2位相当于在原数的基础上乘以4
System.out.println(2);		// 2
System.out.println(2<<2);	// 8
// 左移3位、4位...以此类推

2.6、带符号右移(>>)

  • 带符号右移（>>）指的是各二进位全部右移若干位，低位丢弃，高位补为符号位
// 举例
printBinary(8); // 00000000000000000000000000001000
System.out.println(8>>1); // 4
printBinary(8>>1); // 00000000000000000000000000000100
  • 应用
System.out.println(8);	// 8
System.out.println(8>>1);	// 4
// 无符号右移2位相当于在原数的基础上除以4
System.out.println(8);		// 8
System.out.println(8>>2);	// 2
// 负数右移规则也适用
System.out.println(-8>>1); // -4
// 右移3位、4位...以此类推

2.7、无符号右移(>>>)

  • 无符号右移（>>>）指的是各二进位全部右移若干位，低位丢弃，高位补0
  • 如果是负数进行无符号右移，需要使用负数的二进制补码进行运算。
  • 如果是正数进行无符号右移，则与 >> 规则相同，右移n位，就相当于除以 2n
// 正数无符号右移
System.out.println(8>>>1);
printBinary(8);
printBinary(8>>>1);
// 负数无符号右移
System.out.println(-8>>>1); // 2147483644
printBinary(-8); // 二进制补码：11111111111111111111111111111000
printBinary(-8>>>1); // 01111111111111111111111111111100
System.out.println("=== >>>无符号右移 ===");

三、二进制如此设计的原因

这么设计二进制是为了保证加法的逻辑是一套逻辑，没有条件转移。

也就是说无论是 正数+正数、正数+负数、负数加负数 都是遵循同一套逻辑，可以提高计算机的运行效率。

四、解析二进制打印函数

1、二进制打印函数如下

/**
  * 打印一个int类型的数字，32位进制的状态
  * 左侧是高位，右侧是低位
  * 这里打印的是num的二进制补码。
  * @param num 十进制数值
  */
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();
}

2、解析

  • 一个int类型的数在java中有32位，如果需要打印它的二进制表示，就需要知道它在二进制数中，每一位是0还是1。
  • 根据位运算符 按位& 的特点，相同位都为1，按位&计算为1，否则为0的特点来实现这一需求。
  • 1 << i 表示打印第 i 位上的二进制数
    • 例如：num等于8，那么它的二进制表示为：00000000000000000000000000001000
    • i 从高位(31) 到低位(0) 依次打印。
    • i 等于31时，1 << 31 的值表示的二进制为：10000000000000000000000000000000
    • 此时 num & (1 << i) 的值就是0，所以 num 的二进制值，在第31位上为0。
    • i 递减，依次往后打印出 num 每一位二进制数。
  • 如果num是一个负数，这个函数打印的就是负数二进制数的表示的补码。
    • 例如：num等于 -8 ，此函数打印出它的二进制补码为：11111111111111111111111111111000

正数的二进制 原码、反码、补码是相同的。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 george_95@126.com

©2016-2020 George

Built with Hexo and 3-hexo theme