记录下经常忘记的位运算--与或非

「这是我参与11月更文挑战的第5天，活动详情查看：2021最后一次更文挑战」

一，二进制和十进制转换方法

1. 十进制转二进制

2. 二进制转10进制

二，基本概念

1. 机器数

一个数在计算机中的二进制表示形式, 叫做这个数的机器数。

机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1。

比如，十进制中的数 6，计算机字长为8位，转换成二进制就是00000110。如果是 -6 ，就是 10000110 。这里的 00000110 和 10000110就是机器数。

2. 真值

第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000110，其最高位1代表负，其真正数值是 -6 而不是形式值134（10000110转换成十进制等于134）。所以为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。

例：0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1

3. 原码

原码是一种计算机中对数字的二进制定点表示方法。原码表示在数值前面增加了一位符号位（即最高位为符号位）：正数该位为0，负数该位为1（0有两种表示：+0和-0），其余位表示数值的大小。原码也是机器数的一种表示方式。

比如如果是8位二进制:

[+6] = 0000 0110

[-6] = 1000 0110

第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是:

[1111 1111 , 0111 1111]

即 [-127 , 127]

4. 反码

正数的反码与其原码相同；

负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.

[+6] = 0000 0110(原码) = 0000 0110(反码)

[-6] = 1000 0110(原码) = 1111 1001(反码)

5. 补码

正数的补码与其原码相同；

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (补码=反码+1)

[+6] = 0000 0110(原码) = 0000 0110(反码) = 0000 0110(补码)

[-6] = 1000 0110(原码) = 1111 1001(反码) = 1111 1010(补码)

三，常用位运算

1. 与 (6 & 7)

6和7的二进制位进行与操作，只有对应的二进制位两个都为1结果才为1，否则为0

ini复制代码1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

例如

十进制 = 二进制

6 = 110

7 = 111

6 & 7= 110

二进制110转换成十进制是6

例如：判断奇偶 6 & 0x1

2. 或(6 | 7)

6和7的二进制位进行或操作，只有对应的二进制位两个有一个为1结果就是1，否则为0

ini复制代码1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

例如：

十进制 = 二进制

6 = 110

7 = 111

6 | 7= 111

二进制111转换成十进制是 7

3. 非(~6)

6的二进制位的每一位取反操作，二进制位如果是0，取反后是1，反之是0

1 2	ini复制代码~ 1 = 0 ~ 0 = 1

在Java中整型占4字节(32个二进制位)

6 = 00000000 00000000 00000000 00000110

~6 = 11111111 11111111 11111111 11111001

上面二进制最高位是1，表示负数，而负数在计算机中是按照补码存储的。

补码-1得到反码：11111111 11111111 11111111 11111000

首位符号位不变，其他取反得到原码：10000000 00000000 00000000 00000111

二进制原码转换成十进制是 -7

4. 异或(6 ^ 7)

1	复制代码规则：两个位相同为0，不同为1

异或运算的性质

任意一个变量和0异或结果都是其本身（0^N=N）
任意一个变量和其自身异或结果都是0（N^N=0）
异或运算满足交换律和结合律

例1： 6 ^ 7

值	二进制
6	1 1 0
7	1 1 1
1=6^7	0 0 1

5. 左移(6<<2)

把6表示的二进制数左移2位，左边高位超出舍弃，右边低位补0;

在数字 x 上左移 y 位时，得出的结果是 x * 2^y ，即6<<2=6*2^2

6 = 00000110

6>>2 = 00011000 = 24

6. 有符号右移(6>>2)

把6表示的二进制数右移2位，向右被移出的位被丢弃，拷贝最左侧的位以填充左侧。由于新的最左侧的位总是和以前相同，符号位没有被改变。所以被称作 “符号传播”。

因为负数在内存中是以补码形式存在的，所有首先根据负数的原码求出负数的补码

正数6：

6 = 00000110

6>>2 = 00000010 = 2

负数-6：

-6右移2位

-6的原码：10000110

-6的反码：11111001 （原码符号位不变，其余按位取反）

-6的补码：11111010 （反码+1）

右移2位：11111110

补码右移不是最终结果，需要转成原码，才是最终结果

按位取反：10000001（保留符号位，其他位取反）

+1得原码：10000010

最终结果 -2

7. 无符号右移(6>>>2)

把6表示的二进制数右移2位, 向右被移出的位被丢弃，左侧用 0 填充。

因为符号位变成了 0，所以结果总是非负的。

正数6：

6 = 00000110

6>>2 = 00000010 = 2

负数-6：

-6的原码：10000000000000000000000000000110

-6的反码：11111111111111111111111111111001 （原码符号位不变，其余按位取反）

-6的补码：11111111111111111111111111111010 （反码+1）

右移2位：00111111111111111111111111111110

原码：00111111111111111111111111111110（正数的原码补码相同）

最终结果 1073741822

四，实际应用

1. 判断奇偶数

java复制代码int m = 6;
int n = 7;

System.out.println(m % 2 == 0?"偶数" : "奇数");//偶数
System.out.println(n % 2 == 0?"偶数" : "奇数");//奇数
System.out.println(((m & 1) == 1) ? "奇数" : "偶数");//偶数
System.out.println(((n & 1) == 1) ? "奇数" : "偶数"); //奇数

2. redis的bigmap和HyperLogLog

通过位运算可以做基数统计，极大的节省内存，像注册IP数、每日访问 IP 数、页面实时UV）、在线用户数，这个后面可以单独写一篇

3. 巧妙利用异或，不用额外变量交换两个变量的值

java复制代码public static void main(String[] args) {

           int a = 10;
           int b = 6;
      // a = a^b
           a = a ^ b;
      // b = a^b^b = a
           b = a ^ b;
      // a = a ^ a^b = b
           a = b ^ a;
           System.out.println("a="+a + ",b=" + b);  
  }

输出： a=6,b=10

4. 选择排序中交换两个数据的位置(剩下数据中最小的与当前位置互换)

java复制代码public static void main(String[] args) {
       int[] nums = {5, 3, 8, 4, 2, 1, 9, 7, 6,500,100,300,200,400};
       for (int i=0;i<nums.length;i++){
           int n = i;
           for (int j=i;j<nums.length;j++){
               if (nums[n]>nums[j]){
                   n = j;
              }
          }
           if (i!=n){
               nums[i] = nums[i] ^ nums[n];
               nums[n] = nums[i] ^ nums[n];
               nums[i] = nums[i] ^ nums[n];
          }
      }
       System.out.println(Arrays.toString(nums));

  }

输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 200, 300, 400, 500]

5. 一个数组中只有一种数出现奇数次，其他都出现偶数次，怎么找到这个数

ini复制代码public static void main(String[] args) {
       int[] nums = {3,5,5,8,8,3,10};
       int eor=0;
       for(int i=0;i<nums.length;i++){
           eor = eor^nums[i];
      }
       System.out.println("奇数="+eor);
  }

输出： 奇数=10

因为相同数字异或是0，所以其中的所有偶数的数据结果都是0，最后结果就剩下 0^10 = 10

我是纪先生，用输出倒逼输入而持续学习，持续分享技术系列文章，以及全网值得收藏好文，欢迎关注或者关注公众号，做一个持续成长的技术人。

实际问题系列的历史文章(也可以在掘金专栏中看其他相关文章)

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有