晋升答辩那天,我准备了20页PPT,把过去一年的成就讲得天花乱坠,后来我才发现,晋升名单其实早就在答辩前定好了.答辩只是走个过场、

昨天晚上十一点多吧，我在公司楼下抽烟呢，手机叮一声，我们组小李发群里：东哥救命，面试题“第K个语法符号”我脑子卡死了…我当时还在想这题不是老题么，但你真要一行一行生成字符串吧，n=30 这种直接把内存打爆，别说面试了，线上也一样，很多人写代码一上来就“先把数据全算出来”，然后就开始哭，哈哈。

我就跟他说，你别盯着“字符串”，盯着“翻转”。这题的规则是 0 变 01，1 变 10，你看着像在长字符串，其实每往下一层，就是把上一层的每个符号“复制一份”，然后右半边全取反。那第 k 个位置到底是啥？你想象一下，从第 1 行往第 n 行走到第 k 个位置，这一路上你有没有走到“右孩子”。走一次右孩子就翻转一次，翻转奇数次就是 1，偶数次就是 0。就这么粗暴。

然后小李说那怎么知道走没走右孩子，我说你别真建树啊，别把自己架构师写成树莓派…你看 k 的二进制就行。k 从 1 开始编号，换成 0 开始更舒服：idx = k-1。idx 的二进制里有多少个 1，就代表你在路径里走了多少次“右边”，因为每一层你是左还是右，本质上就是看那一位是 0 还是 1。popcount 的奇偶性，就是答案。n 其实就是“保证树够深”，只要 n 足够大到覆盖 k，这个结论就不变。

我当时还顺手在群里丢了段 Rust，免得他又问“东哥 Rust 的 count_ones 叫啥来着…”，你们看就是这么点东西：

pubfnkth_grammar(_n: i32, k: i32) -> i32 {// k 从 1 开始，先转成 0 开始let idx: u32 = (k - 1) asu32;// 走右边的次数 = idx 的二进制 1 的个数// 翻转次数奇数 -> 1，偶数 -> 0    (idx.count_ones() & 1) asi32}#[cfg(test)]mod tests {use super::*;#[test]fntest_basic() {assert_eq!(kth_grammar(1, 1), 0);assert_eq!(kth_grammar(2, 1), 0); // 01assert_eq!(kth_grammar(2, 2), 1);assert_eq!(kth_grammar(4, 5), 1); // 01101001，第5个是1    }}

小李看完又来一句：那递归能写吗，面试官爱看“推导过程”。我说能啊，但你写递归别把栈写炸了就行，递归的意思就是：第 n 行第 k 个来自第 n-1 行的父节点，父节点位置是 (k+1)/2，如果 k 是偶数说明你在右边，要在父节点基础上翻转一下。Rust 写起来也不难，就是有点啰嗦：

pubfnkth_grammar_rec(n: i32, k: i32) -> i32 {if n == 1 { return0; }let parent = kth_grammar_rec(n - 1, (k + 1) / 2);if k % 2 == 1 {        parent    } else {1 - parent    }}

不过我一般更推荐上面那个 bit 的版本，干净，快，还不容易写错。你把它当成“路径翻转次数的奇偶性”就行，跟我们做分布式一致性里那种“状态机只看事件序列，不看中间快照”有点像，别老想着把整棵树生成出来，成本太高，收益还低。

哦对了，我说着说着烟都快抽完了，保安还瞪我一眼…算了我先上楼了，等会儿还得把那台 CI 的破机器重启一下，它又卡在编译缓存那儿了。