March 13, 2013
从线性代数看解线性递推式

写这个的动机出自这篇，平时经常接触的需要解特征根的其实还有求解线性递推式，可以简单的用同样的方法从线性代数来理解。

1. 定义算子

在连续函数空间中定义算子 Txn = Txn+1，xn 为函数 x 在 n 点的值，所以数列递推式 xn+2 = 3 * xn+1+10 * xn 可以写作 T2x = 3 * Tx + 10 * x，易证算子是线性算子，由于 Tcan = an+c = ac * an，所以 xn = an 为算子 Tc 的本征向量，本征值为 ac 。

2. 解线性递推方程

接上面那个例子，(T2 - 3 * T - 10) x = 0，由于线性算子的线性组合仍然是线性算子，所以 L = (T2 - 3 * T - 10) 为线性算子，原方程等价于解 L 的零空间，(T - 5I)*(T + 2I) x = 0，解出 T 的本征值为 5 与 -2，本征向量为 5n 与 ( -2 )n，所以解为 A1 * 5n + A2 * ( -2 )n 。

3. 选择 ax 作为基底

关于为什么 ax 作为基底的张成能构成整个连续函数空间 ( 实际上张成的闭包才是整个连续函数空间 ) 可以参见相当有趣的 Stone-Weierstrass 定理。

PS: 感谢小西大大！

PS2: 统一微分方程线性递推方程和线性代数这困扰我许久的问题终于解决了…

7:38pm  |   URL: http://tmblr.co/Za-SGyg9rrjx
May 23, 2012
位运算基础操作

其实就当是 Hacker’s Delight 的读书笔记啦w 代码用 C 来表示

操作最右侧位

考虑如何用位运算将 x 最右侧的 1 变为 0，显然，这个操作的目的一定会减少 1 的数量，考虑所有的位运算符，唯一符合要求的就是 &，那么这个操作的样子应该是

x & a

其中 a 要在 x 最右侧 1 的位为 0，并且保持其他 1 的位。那么就很显然啦

x & (x-1)

如果 x 是 2^n 的话那么这个式子应该得到 0，所以可以用来判断 x 是否为 2^n

同样的思路，要将 x 最右侧的 0 变成 1 的话就是

x | (x+1)

& 与 |，+ 与 - 是对偶的关系，一般来说把对 1 的操作换成对偶的表达式之后就是对 0 的操作。

现在来考虑如何析出最右侧的 1 位，考虑要将除了最右侧的 1 以外都变成 0，第一反应可能是用 ^，那么构造的表达式是

((x ^ (x-1))+1)»1

虽然可行可是太麻烦啦，除了异或，其他能将 1 都变为 0 且保持 0 的操作就只有 & 了，注意到 x & ~x 恒为 0，后面就很显然了

x & ~(x-1)

上式还能化简，补码表示里 ~(x-1) 等价于 -x，所以最终得到

x & (-x)

前面失败的尝试中也有一个有趣的式子

x ^ (x-1)

这个式子将析出最右侧的 1 和后缀 0 的掩码

最后举一个上面式子的应用，如何穷举一个位向量表示的集合中选取 n 个元素的所有组合，换句话说，如何获得与给定 x 具有相同数量 1 的下一个比 x 大的数

  • 如果 x 最右侧的 1 能够左移，也就是说最右侧的 1 相邻的位为 0，那么显然左移最右侧 1 得到的数是所求的数

  • 如果 x 最右侧的 1 左侧为 1，那么向左直到找到第一个能够左移的 1 后左移，把右侧所有的 1 移到最右侧。比如 0001 1011 0000 将变为 0001 1100 0011

其实第一种情况只是第二种的特例，根据以上描述得到操作如下

// 析出最右侧的 1

s = x & -x

// 所有连续的 1 都会被进位直到第一个 0

ret = x + s

// 析出最右侧的连续 1 以及进位的 1，比需要的 1 多了两个

t = x ^ ret

// 除以 s 将 t 对齐至最低位，左移 2 去掉多余的两个 1

ret |= (t»2)/s

ret 就是所求的数

嘛 我发现学了东西还是要写下来不然会忘 而且我的表达能力太差了正好锻炼下 .-.

2:18pm  |   URL: http://tmblr.co/Za-SGyL_Wa9f
Liked posts on Tumblr: More liked posts »