刷题笔记 | 向阳花

位运算操作备忘

$x \bmod y$ , x % y , 若 $\bold{y=2^n}$ ，可以使用位运算代替，
- $if \ y=2^n,x\bmod y = x \& (y-1)$
- 即 $y=2,4,6,8\cdots$
- 取余数，是取低位，以 $8$ 为例， $8-1=7$ ， $7:0111$
- 会发现，和 $7$ 取余，恰好是低位的值，也即余数
x & (x - 1) 去除x中最后一个1
可以用来求一个数的二进制表示形式的 1的个数
x & (-x) 可以获得x的最低的非0位(即最低有效位，LowBit)
- -x的值，相当于在x的基础上按位取反~x后再增加1所得
- 注意和负数补码的计算区别开，这里按位取反，符号位也要取反！
- 参考本博客文章关于反码和补码
n的二进制表示中，第k位是几？——n>>k&1
1. 先把第k位移动到最后一位：n>>k
2. 然后看最后一位是几：n&1
3. 综合第1和第2步，即为：
  n>>k&1
位运算补充
- &（AND）常用作二进制取特定位上的值，
例如：x&1取最后一位二进制数，可用来判断是偶数还是奇数
例如：我想取二进制第6位上的值，(x >> 5) & 1
- ｜常用作二进制特定位上的无条件赋值，例如：x | 1的结果就是将x的最后一个二进制位赋为1，
例如：若将二进制最末位变成0，(x|1) - 1即可
某一位置1–> x |= (1 << y)
某一位置0–> x &= ~(1 << y)
- 异或^
假定下面的x是二进制的一位，也就是0或者1！
1
2
3
4
5
0 ^ x = x

x ^ x = 0

x ^ 1 = ~x
关于「原码、补码、反码」参见三码和～-
左移<<、右移>>等参见 java中的左移、右移、无符号右移

关于各种进制

进制	二进制	八进制	十进制	十六进制
英语名称	Binary	Octal	Decimal	Hexadecimal
前缀表示	0b，`0b1100`	0，`014`	无，`12`	0x，`0xc`
后缀表示	B，`1100B`	O(字母O)，`14O`	D，`12D`	H，`cH`
	12	12	12	12

关于哈希表

不要滥用。
要明白，哈希表最大的特点是可以O(1)的时间复杂度进行查询。
如果实际场景的需求是：为关键词保存一个value，即仅需要key-value的数据结构时，可以灵活一点，使用数组来解决。

前提是key的数据结构不能太复杂，char、int、都可以。若是TreeNode这样的还是得用哈希表。

二分查找

int mid = (r - l) / 2 + l;这种写法，可以避免数值溢出。

Java I/O

关于字节流和字符流
@Java字节流和字符流，是时候总结一下IO流了

使用 BufferedReader 来获取键盘输入

使用 BufferedWriter 来打印输出

例子，输入如下，将其获取，并存到数组中去。

1 2	6 7 9 2 5 3 4

代码：

public class Main {
    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(reader.readLine());
        BufferedInputStream bs = new BufferedInputStream(System.in);
        String[] strs = reader.readLine().split(" ");

        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(strs[i]);
        }
        // 打印输出
        log.write(n + "\n");
        for (int i : arr) {
            log.write(i + " ");
        }
        // flush
        log.flush();
        // 释放
        log.close();
        reader.close();
    }
}
/**
 * 6
 * 7 9 2 5 3 4
 * 6
 * 7 9 2 5 3 4
 * 进程已结束,退出代码0
 */

注意：

需要声明IO异常
static的使用
类型转换，将字符串进行转换

位运算操作 备忘

关于各种进制

关于哈希表

二分查找

Java I/O

位运算操作备忘