常见的位运算和算法总结

一、常见位运算和算法

参考

位运算：https://zhuanlan.zhihu.com/p/94577806

位运算：https://www.jianshu.com/p/104f53c663c9

小数表示：https://www.runoob.com/w3cnote/bit-operation.html

1. 四大基本位运算符

1.1 与 &

1 & 1 = 1
1 & 0 = 0
0 & 0 = 0
  
1110 & 0111 = 0101
  

1.2或 |

1 | 1 = 1
1 | 0 = 1
0 | 0 = 0
  
1110 | 0111 = 1111
  

1.3非(反) ~

~1 = 0
~0 =1
~ 1110 = 0001

1.4 异或 ^（同为 0 ，异为1）

  0000 1111
^ 0000 1100
= 0000 0011

相同的，结果是 0 ，比如 0 ^ 0 = 0 ,1^1 =0​

相反的，结果是 1，比如 0 ^ 1 = 1,1 ^0 =1

2 正负数的表示

首位是符号位

负数 -3 的表示方法

# 首先是是 3 
0000 0011
# 然后取反
1111 1100
# 然后 +1 
1111 1101

1111 1101 就是 -3 的表示方法，又称之为「补码」

为什么我们要用「补码」这中花哨的的方法来表示负数呢？？？

举个例子：

十进制的 3 +(- 3) = 0 我们很容易理解

我们看看二进制的

   00000000 00000000 00000000 00000011 #3，原码
+  xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx #-3，补码
-----------------------------------------------
 (1)00000000 00000000 00000000 00000000 #括号里面的 1 是忽略的溢出

我们可以通过结果，反推补码的组成

反推的思路是3的二进制数从最低位开始逐位加1，使溢出的1不断向高位溢出，直到溢出到第33位。然后由于int类型最多只能保存32个二进制位，所以最高位的1溢出了，剩下的32位就成了（十进制的）0。

   00000000 00000000 00000000 00000011 #3，原码                         
+  11111111 11111111 11111111 11111101 #-3，补码
-----------------------------------------------
 1 00000000 00000000 00000000 00000000

都是为了方便计算机计算罢了，不是为了方便我们人类计算的

3.加减运算

3.1 加法

这个很简单

比如说

3 + 3 = 6

二进制就是「逢二进一」即可

0000 0011
0000 0011
0000 0110

3.2 减法「忽略溢出」

比如 5-3

可以看做 5+(-3)

# 5
0000 0101
# -3
1111 1101
# 5 -3
# 这里注意多了一位，「我们直接忽略溢出」
# 这就是减法这么表示的原因
(1)0000 0010
# 最后 5-3 结果为
0000 0010

为了方便计算机的运算，所以要使用这种方式表示减法

重点是「忽略溢出」

4.将一个 byte 转化为 8 个布尔值

问题：

在 Java 中，boolean 类型只有 true 和 false，2 种类型，但是却占用了 1 Byte = 8 bit 的大小，8 个 bit 可以表示 8 个不同的字段，但是如果我们用 boolean 只能表示 1 个字段 。

我们要用一个 byte 记录 8 个字段的 true 或者是 false，可以将空间空间利用率提升 800%（你的工资并不会提升 800%）

在 java 中一个字节 boolean 就是 1 Byte 大小，1 Byte = 8 bit ,

就是 8 位，比如 0000 0000

拓展:

（这里不具体讨论 boolean 的占的大小，可以参考这个 https://blog.csdn.net/amoscn/article/details/97377833）

4.1 问题：怎么读取某个位是0还是1？

我怎么知道这个某个位置是 0 还是 1

比如：

我们可以通过 & 与 运算 知道第 3 位是 0 还是 1

# 测试第一个数据 0001 1100 （第三位是 1)
  0000 1100 
& 0000 0100 #这里是关键，我们将 0000 0001 右移 3-1 = 2位 就是 0000 0100 ，
            # 用这个和测试数据取与 & 
= 0000 0100 
# 因为 0000 1100 & 0000 0100 == 0000 0100 可以判定，第三位是 1

# 测试第二个数据 0000 0010 (第三位不是 1)
  0000 0010 
& 0000 0100 #这里是关键，我们将 0000 0001 右移 3-1 = 2位 就是 0000 0100 ，
            #用这个和测试数据取与 & 
= 0000 0000
# 因为 0000 0010 & 0000 0100 != 0000 0100 可以判定，第三位不是 0

4.2 在不影响其他位的情况下，怎么把一个位置设置为 1

使用 | 或操作可以将，一个指定的位置设置为 1

举个例子，下面，我们将位置为 3 的位置设置为 1

# 测试的第一个数据是 0000 0000 (我们要将它从右至左的第三个位置设置为 1)
  0000 0000 
| 0000 0100 #这里是关键，我们将 0000 0001 右移 3-1 = 2位 就是 0000 0100 ，
            # 用这个和测试数据取货 |
= 0000 0100 
# 我们使用取  | 或操作，成功，将第三为设置为 1 ，不管这个位置是 0 还是 1 都会被设置为 1

4.3 在不影响其他位的情况下，将一个位置设置为 0

分析:通过 取 & 操作，才能将一个为 1 的位置设置为 0 ，所以，这个操作必须是为 取与 &

举个例子，下面，我们将位置为 3 的位置设置为 1

# 测试第一个数据 0001 1100 （第三位是 1，将其变为 0)
0000 0100 
& 1111 1011 # 这里十分关键，我们先将 0000 0001 左移 3-1=2 位为 0000 0100
            # 然后取反为 1111 1011
            # 然后再和元数据 0000 0100 & 运算
= 0000 0000 
# 成功

4.4 代码

通过 4.1，4.2，4.3 我们基本了解了如何用一个 char 表示 8 个字段的方法和思路

现在我们用代码实现它即可

public class BitUtils {

    public static final byte base = 1;
    
    /**
     * 判断对于 aByte 来说index的位置是,是0或是1
     */
    public static boolean check(int index,byte aByte) {
        return(base << index) == (aByte & base << index);
    }

    /**
     * 将 index 的位置设置为 1
     */
    public static byte setTure(int index,byte aByte) {
        return (byte) (aByte | base<<index);
    }

    /**
     * 将 index 位置设置为 0
     */
    public static byte setFalse(int index, byte aByte) {
        //左移
        int temp1 = base << index;
        //取反
        int temp2 = ~temp1;
        return (byte) (aByte & temp2);
    }
}

测试

    public static void main(String[] args) {
        //判断 0000 0001 第一个位置 是是否为 1
        System.out.println("判断 0000 0001 第一个位置 是是否为 1"+check(0, (byte) 1));
        //判断 0000 0010 第一个位置 是是否为 1
        System.out.println("判断 0000 0010 第一个位置 是是否为 1:"+check(0, (byte) 2));
        //将 0000 0000 第二个位置设置为 1
        byte b = setTure(1, (byte) 0);
        System.out.println("将 0000 0000 第二个位置设置为 1:"+b);
        //将 0000 0010 第二个位置设置为0
        byte b2 = setFalse(1, (byte) 2);
        System.out.println("将 0000 0010 第二个位置设置为 0:"+b2);
    }

最后

以上就是阳光雪糕为你收集整理的常见的位运算和算法总结的全部内容，希望文章能够帮你解决常见的位运算和算法总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。