- 位运算、算法是什么、简单排序
- 一、位运算
- 1. 打印二进制
- 2.正负整数的二进制表示
- 二、算法是什么
- 三、算法的分类
- 题目一 阶乘和
- 题目二 选择排序
- 题目三 冒泡排序
- 题目四 插入排序
- 四、写在后面
计算机上所有的数看起来是十进制，底层都是二进制。
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 ] [-2^{31},2^{31}-1] [−231,231−1] ，即 [ − 2147483648 , 2147483647 ] [-2147483648,2147483647] [−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}-1] [−231,231−1] 可知，任何一个正数都有其对应的相反数，那 − 2 31 -2^{31} −231 的相反数是多少呢？
我们计算可以得到 − 2 31 -2^{31} −231 的相反数是它本身。
由于 − 2 31 -2^{31} −231 的二进制为： 10000000000000000000000000000000
− 2 31 -2^{31} −231 的二进制取反为：01111111111111111111111111111111
− 2 31 -2^{31} −231 的二进制取反加1为：10000000000000000000000000000000
故 − 2 31 -2^{31} −231 的相反数是它本身。
验证代码如下
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
}
}
二、算法是什么
- 有具体的问题
- 有设计解决这个问题的具体流程
- 有评价处理流程是可量化指标
- 分类当然非常多
- 对于新手学习特别重要的一个分类
- 明确知道怎么算的流程
- 明确知道怎么尝试的流程（图灵将破解德军密码的尝试方法研究成图灵机）
给定一个参数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,N-1] [0,N−1] 范围上操作
[ 0 , 1 ] [0,1] [0,1] 位置谁大谁放后面
[ 1 , 2 ] [1,2] [1,2] 位置谁大谁放后面
……
[ N − 1 , N ] [N-1,N] [N−1,N] 位置谁大谁放后面
此时， N N N 位置数为全局最大数
步骤二： [ 0 , N − 2 ] [0,N-2] [0,N−2] 范围上操作
[ 0 , 1 ] [0,1] [0,1] 位置谁大谁放后面
[ 1 , 2 ] [1,2] [1,2] 位置谁大谁放后面
……
[ N − 2 , N − 1 ] [N-2,N-1] [N−2,N−1] 位置谁大谁放后面
此时， N − 1 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 ] [1,i] [1,i] 位置的牌有序。
步骤i： 让 [ 1 , i ] [1,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];
}
}
四、写在后面
欢迎关注，会经常记录一些算法学习中遇到的问题。
欢迎随时留言讨论，与君共勉，知无不答！
暑期编程PK赛 得CSDN机械键盘等精美礼品！
