首页 数据结构

计算机二进制运算与实际应用

正整数转二进制，负整数转二进制，小数转二进制

在说明换算之前，先介绍一下次方和负次方的概念:

^在这里为幂等 不是位运算符的异或

2^2 = 2×2 = 4 // 次方
2^-2 = 1÷2^2 = 1÷4 = 0.25; // 负次方

1，正整数转二进制

在计算机中存储字节是定长的，即我们8、16、32位等等，6的二进制位为110，但如果在8位计算机中是00000110，高位补零

6/2 = 3 // 余数 0
3/2 = 1 // 余数 1
1/2 = 0 // 余数 1
// 所以值为110

2，负整数转二进制

取反就是把1变0，加1就是把最右边的1挪到后面一位去

// 6在8位计算机中二进制是
00000110 // 先取反
11111001 // 再+1
11111010 // 这个值就是-6的二进制

3，小数转二进制

小数转二进制，先把整数为转换成二进制，然后把小数位转换(小数为换算每次乘2，不足1为0)，最后相加，6.25的二进制为110.01

6.25 //转二进制
6 = 110 // 整数的二进制
0.25×2 = 0.5 //不足整数 得 0 
0.5×2 = 1 //为整数 1
// 所以二进制为 110.01

二进制转换正负整数以及小数

1，二进制转正整数

二进制位左边首位为0为正数（6 --->00000110），1为负数(-6---->11111010)

00000110
.....2^2,2^1,2^0
2^0 × 0 = 0; // 从左往右第一个为0
2^1 × 1 = 2; // 从左往右第二个为1
2^2 × 1 = 4; // 从左往右第三个为1
... // 前面都是0，值肯定也为0
// 所有值相加 0+2+4+0+0... = 6

2，二进制转负整数

-6的二进制位为11111010,取反为00000101，然后加1为00000110,110为6，故值为-6

11111010 取反为00000101，然后加1为00000110,110为6 然后再转负

3，二进制转小数

和小数转二进制一致，先算整数位，再算小数位，最后相加

0.01 // 二进制
2^0 2^-1 2^-2
2^0 * 0 = 0;
2^-1 * 0 = 0;
2^-2 * 1 = 1 ÷ 2^2 = 1 ÷ 4 = 0.25;
0+0+0.25 = 0.25 // 值为 0.25

原码，反码，补码

建议阅读该文章：原码 反码 补码 概念 原理 详解 

  1. 计算机操作的都是补码
  2. 正数的原码，反码，补码一样
  3. 负数的反码，符号位不变(第一位)，其它位反过来，补码，在反码基础上加一
X=+101011 , [X]原= 0010_1011 ，[X]反=0010_1011，[X]补=0010_1011
X=-101011 , [X]原= 1010_1011 ，[X]反=1101_0100，[X]补=1101_0101

位运算符

& (位与)

//是将两边的数转换为二进制位，然后运算最终值，运算规则即(两个为真才为真)
1&1=1 , 1&0=0 , 0&1=0 , 0&0=0
0000 0011 //3的二进制
0000 0101 //5的二进制
0000 0001 // 3 & 5的值为 1
// 特性
1.一个数 & 一个数 = 最小值为0,最大值为这两个中最小数
2.一个大于1的数 & 这个数-1 = 如果等于 0 则这个数肯定是2的幂等(因为只有2的幂等数转换为2进制只有一个1)
// 1.可用于实现奇偶数判断 因为偶数的二进制最后一位肯定是 0 ,而 1 的二进制为 00000001
// 所以任何整数 & 1 的值不是 0 就是 1
if(0 == (a & 1)) {
 //偶数
}
// 2.可用于数据范围落点，利用第一个特性
int[] a = new int[6];
int 51; // 要存放的数据
51 & a.lenght-1 = 1 // 得到下标
a[1] = 51; //下次找时也可以继续通过这种方式可实现O(1)时间复杂度,
// HashMap 的数组就是这么做的,但数组长度尽量是2^n次方，因为长度-1后二进制值后面都是1,因为与特性保证入参值的0或1都有效，减少hash冲突
// 3.可以用于判断是否为2的幂等,利用第二个特性
a > 1 && (a & (a-1)) == 0

| (位或)

//是将两边的数转换为二进制位，然后运算最终值，运算规则即(一个为真即为真)
1|0 = 1 , 1|1 = 1 , 0|1 = 1 , 0|0 = 0
0000 0011 //3的二进制
0000 0101 //5的二进制
0000 0111 //3 | 5的值为 7
// 特性
1.一个数 & 一个数 = 最小值为这两个中最大数,最大值为这个两个数之和

^ (异或)

//异就是不同，其运算规则为(相同为0,不同为1)
1^0 = 1 , 1^1 = 0 , 0^1 = 1 , 0^0 = 0
0000 0011 //3的二进制
0000 0101 //5的二进制
0000 0110 //3 ^ 5的值为 6
// 特性
根据运算规则 1^0 = 1 , 1^1 = 0 , 0^1 = 1 可看出构成一个闭环。二进制后数据就这个样子所以可以得出结论
1.知道任意两个数可以异或出另一个数，且这三个数任意两数异或都是剩下的数
2.一个数 ^ 相同数 = 0
3.一个数 ^ 0 = 这个数
// 1.数字换位
a ^= b; // a = a ^ b
b ^= a; // b = a ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
a ^= b; // a = a ^ b = (a ^ b) ^ b = (a ^ a) ^ b = b ^ 0 = b

~ (取反)

// 在二进制下，取反运算规则是
1 = 0; 0 = 1;
0000 0101; // 5的二进制
1111 1010; // -6的二进制
~5 = -6 // 这就是取反
//特性
1.将二进制0与1弄反，不是反码首位也会改动
2.~一个数 = 这个数的反数+1
// 1.获取绝对值 （int 最小负数值不变）
a > 0 ? a : ~a+1;

<< (左移)

// 5<<2的意思为5的二进制位往左挪两位,右边补0,运算规则为(向左挪n位,就是原数×2的n次幂)
5<<2
0000 0101 //5的二进制
0001 0100 //向左移动2位也就是×2的2次幂等于十进制值 20
-5>>2
1111 1011 //-5的二进制
11(左移丢弃) 1110 1100 //左移2位前面丢掉的也就是×2的2次幂等于十进制值 -20
//特性
1.移动时最左边第一个数永远不变
2.移动时尾数补0
3.向左移就是×2的n次幂,移动n次就是2的n次幂

>> (右移)

// 5>>2的意思为5的二进制位往右挪两位,左边补0(负数左边补1),运算规则(向右挪n位,就是原数÷2的n次幂,余数丢弃)
5>>2
0000 0101 //5的二进制
0000 0001 01(丢弃) //向右移动2位也就是÷2的2次幂,5÷2=2(余数丢弃)2÷2 = 1(最终值)
-5>>2
1111 1011 //-5的二进制
1111 1110 11(丢弃) //右移动2位也就是÷2的2次幂,5÷2=2(余数1加上)3÷2 = 1(余数1加上) = 2 再转负数 -2 (最终值)
// 特性
1.移动时正数左边第一位补0，负数补1
2.向右移就是÷2的n次幂,移动n次就是2的n次幂
3.负数每次移动如果有余数会加上余数，最小值为-1,正数最小值为0

>>> (无符号右移)

// 与右移的区别在一个特性是移动时正数左边第一位补0，负数补1改为负数也补0
5>>>2
1111 1011 //-5的二进制
0011 1110 11(丢弃) // 值62.没想到好的算数过程

组合使用

1.生成第一个大于a的满足2^n的数

public int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1; // >>> 获取一个向右偏差一位的二进制，再通过位或|的特性填充原二进制，可以得到一个不会有单个1出现的二进制。如 19[00010011],弄完后[00011011]
    n |= n >>> 2; // >>> 获取一个向右偏差两位的二进制，再通过位或|的特性填充原二进制，可以得到一个不会有两个1出现的二进制。如 19[00010011],弄完后[00011111]
    n |= n >>> 4; // ..
    n |= n >>> 8; // ..
    n |= n >>> 16;// .. 结果是从第一个1开始后面全面1的二进制。这样对这个数+1可以得到一个只有一个1存在的二进制，那么这个二进制肯定是2的幂等
    return (n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1; // 第一层判断是正负数判断，第二层判断是否大于int类型正整数范围内最后一位2幂等数，都不满足就加+，将后面一排1变为最前面一个1
}

2.求绝对值 (比较是右移)

// a >> 31 int类型32位，移动31看最前面1位是1还是0，代表正负
a >> 31 == 0 ? a : (~a + 1);

3.计算二进制中1的个数

count = 0  
while(a){ // a 等于 0 时退出循环
  a = a & (a - 1);  
  count++;  
}

4.判断是否为2.的幂等

a > 1 && (a & (a - 1)) == 0

5.将整数A转换为B,需要改变多少bit位

// 第32位相等
a ^= b; // 通过异或相同为0，不相同为1，再判断1的个数
count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}
count // 次数

总结

待续~~