位运算、算法是什么、简单排序

一、位运算

1. 打印二进制

计算机上所有的数看起来是十进制，底层都是二进制。

int => 32位，long => 64 位

public class Code06_PrintB {

    public static void print(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) {
        // 32 位
        int num = 83928328;
        print(num);
        int num2 = 2;
        print(num2);
    }
}

2.正负整数的二进制表示

int 类型整数可以用32位二进制表示，其中第一位为符号位，0表示正数，1表示负数。int 的范围为 $2^{31},2^{31}-1]$ ，即 $[? 2147483648, 2147483647]$ .

其中，整数 num 的相反数为 ~num+1 .

public class Main {

    public static void main(String[] args) {
        int a = 5;
        int b = ~a + 1;
        int c = -a;
        System.out.println(a); //  5
        System.out.println(b); // -5
        System.out.println(c); // -5
    }
}

由 int 的范围为 $2^{31},2^{31}-1]$ 可知，任何一个正数都有其对应的相反数，那 $2^{31}$ 的相反数是多少呢？

我们计算可以得到 $2^{31}$ 的相反数是它本身。

由于 $2^{31}$ 的二进制为： 10000000000000000000000000000000

$2^{31}$ 的二进制取反为：01111111111111111111111111111111

$2^{31}$ 的二进制取反加1为：10000000000000000000000000000000

故 $2^{31}$ 的相反数是它本身。

验证代码如下

public class Main {

    public static void print(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 num = Integer.MIN_VALUE;
        print(num); // 10000000000000000000000000000000
        print(~num); // 01111111111111111111111111111111
        print(~num + 1); // 10000000000000000000000000000000
        print(-num); // 10000000000000000000000000000000
    }
}

二、算法是什么

有具体的问题
有设计解决这个问题的具体流程
有评价处理流程是可量化指标

三、算法的分类

分类当然非常多
对于新手学习特别重要的一个分类
1. 明确知道怎么算的流程
2. 明确知道怎么尝试的流程（图灵将破解德军密码的尝试方法研究成图灵机）

题目一阶乘和

给定一个参数N,返回：1!+2!+3!+4!+……+N!的结果

代码实现：

public class FactorialSum {

    public static void main(String[] args) {
        int n = 10;
        int factorial = 1;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            factorial *= i;
            sum += factorial;
        }
        System.out.println(sum);
    }
    
}

题目二选择排序

选择排序

0~N-1上选出最小值放到0位置
1~N-1上选出最小值放到1位置
2~N-1上选出最小值放到2位置

代码实现：

import java.util.Arrays;

public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {12, 85, 9, 5, 8, 7, 6, 25, 48, 84};
        printArray(arr); // [12 85 9 5 8 7 6 25 48 84]
        selectionSort(arr);
        printArray(arr); // [5 6 7 8 9 12 25 48 84 85]
    }

    private static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + " ");
            } else{
                System.out.print(arr[i]);
            }
        }
        System.out.println("]");
    }

    private static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = 0; i < arr.length; i++) {
            int minValueIndex = i;
            for (int j = i; j < arr.length; j++) {
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            swap(arr, minValueIndex, i);
        }
    }

    private static void swap(int[] arr, int minIndex, int i) {
        if (minIndex == i) return;
        arr[i] = arr[i] ^ arr[minIndex];
        arr[minIndex] = arr[i] ^ arr[minIndex];
        arr[i] = arr[i] ^ arr[minIndex];
    }
}

题目三冒泡排序

算法流程

步骤一： $[0, N ? 1]$ 范围上操作

$[0, 1]$ 位置谁大谁放后面

$[1, 2]$ 位置谁大谁放后面

……

$[N ? 1, N]$ 位置谁大谁放后面

此时， $N$ 位置数为全局最大数

步骤二： $[0, N ? 2]$ 范围上操作

$[0, 1]$ 位置谁大谁放后面

$[1, 2]$ 位置谁大谁放后面

……

$[N ? 2, N ? 1]$ 位置谁大谁放后面

此时， $N ? 1$ 位置数为全局第二大数

……

代码实现：

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {12, 85, 9, 5, 8, 7, 6, 25, 48, 84};
        printArray(arr);
        bubbleSort(arr);
        printArray(arr);
    }

    private static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + " ");
            } else {
                System.out.print(arr[i]);
            }
        }
        System.out.println("]");
    }

    private static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                }
            }
        }
    }

    private static void swap(int[] arr, int minIndex, int i) {
        if (minIndex == i) return;
        arr[i] = arr[i] ^ arr[minIndex];
        arr[minIndex] = arr[i] ^ arr[minIndex];
        arr[i] = arr[i] ^ arr[minIndex];
    }
}

题目四插入排序

模拟斗地主摸排的时候，你手中的牌已经有序了，每摸一张，从右向左找到这张牌应该在的位置。也就是依次让 $[1, i]$ 位置的牌有序。

步骤i： 让 $[1, i]$ 位置的牌有序

没有步骤一，因为第一个数和它自己默认有序

public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {12, 85, 9, 5, 8, 7, 6, 25, 48, 84};
        printArray(arr);
        insertionSort(arr);
//        insertionSort2(arr);
        printArray(arr);
    }

    private static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + " ");
            } else {
                System.out.print(arr[i]);
            }
        }
        System.out.println("]");
    }

    private static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = 1; i < arr.length; i++) {
            int newNumIndex = i;
            while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {
                swap(arr, newNumIndex - 1, newNumIndex);
                newNumIndex--;
            }
        }
    }

    private static void insertionSort2(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    private static void swap(int[] arr, int minIndex, int i) {
        if (minIndex == i) return;
        arr[i] = arr[i] ^ arr[minIndex];
        arr[minIndex] = arr[i] ^ arr[minIndex];
        arr[i] = arr[i] ^ arr[minIndex];
    }
}