写一些学算法时收获的 coding 小技巧

不等于 -1

在记忆化搜索中通常会有一个 memo 数组，最初的时候 memo 会全被初始化为-1，代码中有时会这么写

1
2
3
4
5
6
7
8
9
10
11
void dfs(int i){
    if(i>n){
        cal();
        return;
    }
    if(memo[i][j]!=-1){
        cal();
        return;
    }
    dfs(i+1);
}

那么这个记忆化判断部分if(memo[i][j]!=-1)，

完全可以写成if(~memo[i][j]).

其中的原理：-1的二进制为 1000 0001 ，其在计算机中存储为补码形式，即 1111 1111 ，~运算取反，-1会运算成0，其他数则会运算为非0，那么if(~memo[i][j])就是表示除了-1均通过

向下取整（仅限JavaScript）

js是弱类型语言，在进行一些运算时会进行隐式类型转换，那么来这么一个式子：
x=~~x;

就可以实现向下取整，因为若右侧x为浮点数，在js中x用64位来储存，在使用位运算后，x就会变成32位整型，此时，小数点后面部分被舍弃，接着再来一次~，就可以返回原来的数。

举个例子，

1
2
3
x=-6.9;
~x=5;       // 运算时先截掉后面的0.9，然后x变为-6，取反为5
~~x=-6      // 5再取反就变成了-6

其实知道原理之后还可以使用如 x=x|0;这样的式子来向下取整。

注意以上只能用于js，其他强类型语言会报错或者运算错误。