算法

003~005 二进制和位运算，三傻排序算法，对数器

常见位运算的原理，正数和负数在计算机中如何用二进制表示，及互相转换方法，计算机不会自动处理溢出。冒泡、选择、插入排序的思路及代码。对数器的概念和实现，用于验证算法正确性，特别是没有在线测试环境时。包括如何生成随机数据、编写暴力解、比较结果等。

Posted by Hilda on March 5, 2025

003 二进制和位运算

1 二进制与位运算

计算机认得二进制，人们只为了便于看（或者说便于编程）喜欢十进制。

位运算是计算机底层的基础和基石。 所有的计算最终都要分解为位运算才能执行。现代处理器包含各种各样的硬件电路，例如加法器、乘法器、寄存器、缓存等。 这些硬件电路的实现依赖于位运算的原理。

2/3 正数/负数如何用二进制表示

二进制是基数为 2 的计数系统，只使用 0 和 1 两个数字。每个位（bit）表示 2 的某个次幂，从右到左依次为\(2^0,2^1,2^2,....\)，即1，2，4，……

无符号整数情况：以4位的二进制为例，正数直接用二进制表示其值，没有符号位。例如，十进制的 5 用二进制表示为 0101。所以表示的范围就是\([0，2^4-1]\)，一共16个。为什么不是到\(2^4\)，因为还要考虑0，0即0000。

有符号整数情况：还是先以4位的二进制为例（不要着急，一会儿拓展到32位和64位）。

首先4bit的二进制能够表示\(2^4\)个数，这点毫无疑问。那么根据上面的猜测，在有符号的情况下，非负数就可以表示的范围是\([0,2^3-1]\),负数的表示范围就是\([2^{-3},-1]\)

现在详细来看，拿出最高位的0作为符号位，那么能够表示值的位数只有剩下3位了，从000一直到111，如下图

image-20250305162158921

即：0～7，即\([0,2^3-1]\)

上面是非负数的情况。如果负数呢？即符号位（最高位是1）

一个十进制负数如何转化成二进制？方法是，其绝对值的十进制变成二进制，然后减1，再取反。最后加上符号位。

比如-1，把1变成二进制就是001，减1，就是000，取反就是111，最后加上符号位1，最终就是1111

那么4bit能够表示的范围就是就是-8～-1，即

-1—》1111（过程在上面）

-2—〉2就是010，减1就是001，取反是110，添上符号位就是1110

以此类推，-7—》7就是111，减1就是110，取反就是001，添上符号位就是1001

-8—〉8就是1000，减1就是0111，取反就是1000，反正最高位就是1。

综上，最高位是1（即符号位是1）表示的范围如下图：

image-20250305163209265

那么4bit二进制（有符号）能表示的16个数就全部有了：\([2^{-3},-1],[0,2^3-1]\)，这些都是连续的整数，只不过为了便于总结我书写成了2个区间。

那么32bit，64bit的有符号整数也是同理了。

32bit:\([2^{-31},-1],[0,2^{31}-1]\)

64bit:\([2^{-63},-1],[0,2^{63}-1]\)

并且显然，32bit的有符号中，最小的自然是100...00，-1就是1111...11

那么已知二进制又如何转化成十进制呢？规则就是先取反（连同符号位取反），然后加1

以32bit的11111..111来说，连同符号位取反就是00000..000，加1就是0000..0001，化成十进制就是1

现在对这一内容进行总结。

总结

表示范围：

4bit:\([2^{-3},-1],[0,2^3-1]\)

32bit:\([2^{-31},-1],[0,2^{32}-1]\)

64bit:\([2^{-63},-1],[0,2^{63}-1]\)

对于负数来说，二进制变成十进制？

先取反（连同符号位取反），然后加1

对于负数来说，十进制变成二进制？

其绝对值的十进制变成二进制，然后减1，再取反。最后加上符号位。

4 打印二进制(直接定义二进制,十六进制的变量)

总结来说，Java中定义一个二进制就是0b，定义十六进制就是0x

简单看例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class PrintBinary {

    public static void printBinary(int num){
        for (int i = 31; i >=0;i--){
            System.out.print((num & (1 << i))==0? '0':'1');
        }
        System.out.println();//换行
    }

    public static void main(String[] args) {
        int a = 78;
        System.out.println("-----打印78的十进制------");
        System.out.println(a);
        System.out.println("-----打印78的二进制------");
        printBinary(a);
        System.out.println("-----直接定义一个二进制变量,并且打印它------");
        int b = 0b1001110;
        System.out.println(b);
        System.out.println("-----打印二进制变量的二进制形式------");
        printBinary(b);
        System.out.println("-----直接定义一个十六进制变量,并且打印它------");
        // 78的十六进制：二进制1001110，0100就是4 1110就是e
        int c = 0x4e;
        System.out.println(c);
        System.out.println("-----打印十六进制变量的二进制形式------");
        printBinary(c);
    }
}

这段代码的输出就是：

1
2
3
4
5
6
7
8
9
10
11
12

-----打印78的十进制------
78
-----打印78的二进制------
00000000000000000000000001001110
-----直接定义一个二进制变量,并且打印它------
78
-----打印二进制变量的二进制形式------
00000000000000000000000001001110
-----直接定义一个十六进制变量,并且打印它------
78
-----打印十六进制变量的二进制形式------
00000000000000000000000001001110

5 常见位运算

位运算有以下这些

1

|或  &与  ^异或  ～取反   <<左移  >>带符号右移  >>>无符号右移

以上面打印二进制为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

System.out.println("-----｜  或------");
int d = 89;
printBinary(a);
printBinary(d);
System.out.println("================================");
printBinary(a|d);
System.out.println("-----&  与------");
printBinary(a);
printBinary(d);
System.out.println("================================");
printBinary(a&d);
System.out.println("-----^  异或------");
printBinary(a);
printBinary(d);
System.out.println("================================");
printBinary(a^d);
System.out.println("-----~  取反------");
printBinary(a);
printBinary(~a);
System.out.println("-----<<  左移------");
printBinary(a);
printBinary(a << 1);
System.out.println("----->>  带符号右移------");
printBinary(-78);
printBinary(-78 >> 1);
System.out.println("----->>>  无符号右移------");
printBinary(-78);
printBinary(-78 >>> 1);

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

-----｜  或------
00000000000000000000000001001110
00000000000000000000000001011001
================================
00000000000000000000000001011111
-----&  与------
00000000000000000000000001001110
00000000000000000000000001011001
================================
00000000000000000000000001001000
-----^  异或------
00000000000000000000000001001110
00000000000000000000000001011001
================================
00000000000000000000000000010111
-----~  取反------
00000000000000000000000001001110
11111111111111111111111110110001
-----<<  左移------
00000000000000000000000001001110
00000000000000000000000010011100
----->>  带符号右移------
11111111111111111111111110110010
11111111111111111111111111011001
----->>>  无符号右移------
11111111111111111111111110110010
01111111111111111111111111011001

注：

  • >>是带符号的右移，如果是正数，就在前面补0，如果是负数，就在前面补1.

  • 另外：其实左移等价于*2，右移等价于/2(取整得除以2， 比如5>>1就是2)

  • 注意上面说的*2以及/2这种特征，只有非负数才有，负数不要用。

  • 不管是正数还是负数的x，如果对其进行~x+1(取反加1)，就会得到它的相反数：

    • 1
2
3
4

        System.out.println(78);
  System.out.println(~78+1);
  System.out.println(-90);
  System.out.println(~-90+1);
    • 输出是：
    1
2
3
4

    78
-78
-90
90

6 理解打印二进制的函数

1
2
3
4
5
6

public static void printBinary(int num){
    for (int i = 31; i >=0;i--){
        System.out.print((num & (1 << i))==0? '0':'1');
    }
    System.out.println();//换行
}

通过循环遍历整数的每一位，使用按位与运算来提取该位的值，然后将该位的值 (0 或 1) 以字符形式打印到控制台。 循环结束后，打印一个换行符

7 位运算和短路逻辑

特别注意：

  • |，&是位运算，而||，&&是短路运算
  • | 和 & 总是会计算两个操作数。 即使第一个操作数已经可以确定结果，它们仍然会计算第二个操作数。
  • || 和 && 是 短路运算符。 这意味着如果第一个操作数已经可以确定结果，它们就不会计算第二个操作数。

看一个例子，可以直观的看到是否有短路的特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class ShortCircuit {

    public static void main(String[] args) {

        // 测试位运算的或和与
        System.out.println("goFalse() & goTrue() = " + (goFalse() & goTrue()));
        System.out.println("goTrue() | goFalse() = " + (goTrue() | goFalse()));
        // 测试短路
        System.out.println("goTrue() || goFalse() = " + (goTrue() || goFalse()));
        System.out.println("goFalse() && goTrue() = " + (goFalse() && goTrue()));
    }

    public static boolean goTrue(){
        System.out.println("进入了True函数");
        return true;
    }
    public static boolean goFalse(){
        System.out.println("进入了False函数");
        return false;
    }
}

输出：

1
2
3
4
5
6
7
8
9
10

进入了False函数
进入了True函数
goFalse() & goTrue() = false
进入了True函数
进入了False函数
goTrue() | goFalse() = true
进入了True函数
goTrue() || goFalse() = true
进入了False函数
goFalse() && goTrue() = false

8 相反数

  • 不管是正数还是负数的x，如果对其进行~x+1(取反加1)，就会得到它的相反数：

    • 1
2
3
4

        System.out.println(78);
  System.out.println(~78+1);
  System.out.println(-90);
  System.out.println(~-90+1);
    • 输出是：
    1
2
3
4

    78
-78
-90
90

9 整数最小值的特殊性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class MinValue {

    public static void main(String[] args) {
        System.out.println("Integer.MIN_VALUE = " + Integer.MIN_VALUE);
        System.out.println("Integer.MAX_VALUE = " + Integer.MAX_VALUE);
        // 按照取反加1
        System.out.println("~Integer.MIN_VALUE+1 = " + (~Integer.MIN_VALUE + 1));
        // 直接相反数呢
        System.out.println("-Integer.MIN_VALUE = " + (-Integer.MIN_VALUE));
        System.out.println("===========");
        printBinary(Integer.MIN_VALUE);
        printBinary(Integer.MAX_VALUE);
        printBinary((~Integer.MIN_VALUE+1));
        printBinary(-Integer.MIN_VALUE);
    }

    public static void printBinary(int num){
        for (int i = 31; i >=0;i--){
            System.out.print((num & (1 << i))==0? '0':'1');
        }
        System.out.println();//换行
    }

}

输出：

1
2
3
4
5
6
7
8
9

Integer.MIN_VALUE = -2147483648
Integer.MAX_VALUE = 2147483647
~Integer.MIN_VALUE+1 = -2147483648
-Integer.MIN_VALUE = -2147483648
===========
10000000000000000000000000000000
01111111111111111111111111111111
10000000000000000000000000000000
10000000000000000000000000000000

总结：

  • Integer.MIN_VALUE（-2147483648）是一个特殊值，因为它的绝对值（2147483648）超出了 32 位有符号整数的正数范围（最大为 2147483647），至于为了超出在前面已经说了，32bit的表示范围是：\([2^{-31},-1],[0,2^{31}-1]\)
  • 对 Integer.MIN_VALUE 取相反数（-Integer.MIN_VALUE）会导致溢出，结果仍然是 -2147483648。其实啊，可以对其二进制进行取反加1，此时可以发现，其实还是原来的二进制，只不过最前面有位数溢出，但是只能是32位，所以溢出就忽略了。
    • 计算过程：
      • -2147483648 的二进制：10000000 00000000 00000000 00000000。 取反加 1（补码求相反数）：01111111 11111111 11111111 11111111 + 1 = 10000000 00000000 00000000 00000000。
        • 溢出后，结果仍为 10000000 00000000 00000000 00000000，即 -2147483648。

10 为什么这么设计二进制

其实是为了加法的逻辑是一套逻辑，没有条件转移

那么为什么加法的逻辑这么重要呢？因为在计算机底层减法，乘法，除法底层都可以由加法高效的搞出来，底层的性能就大大提升了。

想象你在超市买东西，结账时需要计算总价。如果正数（收入）和负数（折扣或退货）用不同的规则处理，收银员每次都要停下来想：“这是加钱还是减钱？规则不一样怎么办？”这样效率很低。如果能设计一套规则，让加法和减法都用同样的“加”操作完成，收银员就不用切换思路，直接按一个流程算就行了。

计算机也是这样。硬件电路（加法器）是固定的，它只知道“加”这个操作。如果正数和负数的加法规则不同，电路就得加很多判断逻辑（例如“如果是负数，就用减法”），这会增加复杂度和延迟。补码表示法解决了这个问题：无论正数还是负数，加法都用同一套电路逻辑完成。

11 关于溢出

看了上面这么多溢出（overflow）的例子，其实可以发现，计算机底层用二进制进行运算的时候，溢出是非常常见的。计算机用固定位数（例如 32 位或 64 位）表示数字，像一个“定长计数器”。比如二进制加法是按位操作，最高位溢出时会被丢弃（加法器只管按位加和进位，最高位溢出就丢掉，不做额外检查）。如果要做溢出的检查，显然需要额外电路（比较结果和范围），会增加复杂度和成本。每次运算都检查溢出，会拖慢速度。例如，一个简单加法从 1 个时钟周期变成 2-3 个，性能下降严重。而计算机的设计肯定是假设程序员知道自己在做什么，追求“快”而非“聪明”。另外溢出在某些场景是有意的（例如模运算），自动处理反而会干扰。

那么底层溢出了，计算机会解决吗？不会呀。

因此，自己确保自己的调用所得到的结果不会溢出，一定是自己确保的，计算机不会给你做检查。

所以，如果溢出，其实需要程序员自己去发现，责任在程序员。计算机只提供工具（加法器、位运算）。Java 的 int 运算不会抛异常，默默溢出。某些语言（例如 Python）用无限精度整数避免溢出，但 Java 追求性能，没这么干。

可以从哪些角度尽量避免呢？

  • 选择合适的类型。比如太大的范围，就可以用 long（64 位）代替 int，范围更大。
  • 适当写if条件语句判断。
  • 使用Java的库：Java 的 Math.addExact(a, b) 检查溢出，溢出时抛 ArithmeticException。
  • ……

004 三傻算法

选择排序一句话：i~n-1范围上，找到最小值并放在i位置，然后i+1~n-1范围上继续 冒泡排序一句话：0~i范围上，相邻位置较大的数滚下去，最大值最终来到i位置，然后0~i-1范围上继续 插入排序一句话：0~i范围上已经有序，新来的数从右到左滑到不再小的位置插入，然后继续

1 冒泡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import org.junit.Test;

import java.util.ArrayList;

public class Bubble_sort {
    public int[] bubble_sort(int[] list){
        for (int i = 0; i < list.length - 1; i++) {
            int count = 0;
            for (int j = 0;j < list.length - 1 - i;j++){
                if (list[j] > list[j + 1]){
                    swap(list, j, j+1);
                    count += 1;
                }
            }
            if (count == 0){
                break;
            }
        }
        return list;
    }
    public void swap(int[] list, int i, int j){
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }

    @Test
    public void test(){
        int[] list = new int[]{5, 3, 1, 2, 4};
        int[] bubble_sort_res = bubble_sort(list);
        for (int i = 0; i < bubble_sort_res.length; i++) {
            System.out.print(bubble_sort_res[i] + " ");
        }
    }
}

2 选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import org.junit.Test;

public class Select_sort {
    public int[] select_sort(int[] list){
        for (int i = 0; i < list.length - 1; i++) {
            int min_index = i;
            for (int j = i+1; j < list.length; j++) {
                if (list[min_index] > list[j]) min_index = j;
            }
            swap(list, min_index, i);
        }
        return list;
    }

    public void swap(int[] list, int i, int j){
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }

    @Test
    public void test(){
        int[] list = new int[]{5, 3, 1, 2, 4};
        int[] bubble_sort_res = select_sort(list);
        for (int i = 0; i < bubble_sort_res.length; i++) {
            System.out.print(bubble_sort_res[i] + " ");
        }
    }
}

3 插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import org.junit.Test;

public class Insert_sort {
    public int[] insert_sort(int[] list){
        for (int i = 1; i < list.length; i++) {
            int j = i;
            while (j > 0 && list[j] < list[j - 1]){
                swap(list, j, j - 1);
                j--;
            }
        }
        return list;
    }

    public void swap(int[] list, int i, int j){
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }

    @Test
    public void test(){
        int[] list = new int[]{5, 3, 1, 2, 4};
        int[] bubble_sort_res = insert_sort(list);
        for (int i = 0; i < bubble_sort_res.length; i++) {
            System.out.print(bubble_sort_res[i] + " ");
        }
    }
}

注

在每个排序算法开始加上：

1
2
3

if (list == null || list.length < 2){
    return list;
}

005 对数器(TestGenerator)-自我验证技巧

对数器的试用场景：

  • 你在网上找到了某个公司的面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..
  • 你和朋友交流面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..
  • 你在网上做笔试，但是前几个测试用例都过了，突然一个巨大无比数据量来了，结果你的代码报错了，如此大的数据量根本看不出哪错了，甚至有的根本不提示哪个例子错了，怎么debug？你好心烦…

对数器的实现（方法论）：

1，你想要测的方法a（最优解） 2，实现复杂度不好但是容易实现的方法b（暴力解） 3，实现一个随机样本产生器（长度也随机、值也随机） 4，把方法a和方法b跑相同的输入样本，看看得到的结果是否一样 5，如果有一个随机样本使得比对结果不一致，打印这个出错的样本进行人工干预，改对方法a和方法b 6，当样本数量很多时比对测试依然正确，可以确定方法a（最优解）已经正确。

关键是第5步，找到一个数据量小的错误样本，便于你去带入debug

然后把错误例子带入代码一步一步排查

Print大法、断点技术都可以

对数器的门槛其实是比较高的，因为往往需要在两种不同思路下实现功能相同的两个方法，暴力一个、想象中的最优解是另一个。

以后的很多题目都会用到对数器，几乎可以验证任何方法，尤其在验证贪心、观察规律方面很有用

到时候会丰富很多对数器的实战用法，这里只是一个简单易懂的示例

下面是针对前面3个三傻排序算法写的对数器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

public class TestGenerator {
    /**
     * 对数器产生随机长度，值也是随机的函数
     * @param n 数组的长度
     * @param v 数组每个元素值的范围，比如给10，那么每个元素的取值范围就是[1,10]
     * @return 返回随机生成的数组
     */
    public static int[] generateArray(int n, int v){
        int[] randomArr = new int[n];
        for (int i = 0; i < n;i++){
            randomArr[i] = (int)(Math.random() * v) + 1;
        }
        return randomArr;
    }

    public static int[] copyArray(int[] arr){
        int[] resArr = new int[arr.length];
        for (int i = 0;i < arr.length;i++){
            resArr[i] = arr[i];
        }
        return resArr;
    }

    public static boolean sameArray(int[] arr1, int[] arr2){
        for (int i = 0;i < arr1.length; i++){
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int N = 1000;
        int V = 900;

        System.out.println("----------测试开始！！！");
        for (int i = 0;i < N;i++){
            int[] arr = generateArray(N,V);
            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            int[] arr3 = copyArray(arr);
            new Bubble_sort().bubble_sort(arr1);
            new Select_sort().select_sort(arr2);
            new Insert_sort().insert_sort(arr3);
            if ((!sameArray(arr1, arr2)) || (!(sameArray(arr1, arr3)))){
                System.out.println("测试错误！！！");
            }
        }
        System.out.println("----------测试结束！！！");
    }
}

注：

(int)(Math.random() * v) + 1产生的是[1,v]的一个随机数，原理是：

  • Math.random() 生成一个 double 类型的随机数，其范围是 0.0 (包含) 到 1.0 (不包含)，即 0.0 <= Math.random() < 1.0。
  • Math.random() * v: 这会将生成的随机数乘以 v。 这会将随机数的范围扩展到 0.0 (包含) 到 v (不包含)，即 0.0 <= Math.random() * v < v。
  • (int)(Math.random() * v): 这会将结果强制转换为整数类型。 因为强制转换会截断小数部分，所以结果是一个 0 到 v-1 的整数，即 0 <= (int)(Math.random() * v) <= v - 1。
  • (int)(Math.random() * v) + 1: 这会将结果加 1。 这会将随机数的范围调整为 1 到 v (包含 1 和 v)，即 1 <= (int)(Math.random() * v) + 1 <= v。
CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 机器学习-吴恩达 力扣 Java基础 numpy ollama工具 pandas
    FRIENDS