1545. 找出第 N 个二进制字符串中的第 K 位

1545. 找出第 N 个二进制字符串中的第 K 位

\[ len_n = len_{n-1} * 2 + 1 \\ = (len_{n - 2} * 2 + 1) * 2 + 1 \\ = ... \\ = ((len_1 * 2 + 1) * 2 + 1) * 2... \\ = 2^{n - 1} + 1 + 2 * 1 + 2 * 2 * 1 + ... 2^{n - 2} \\ = 2^{n - 1} + \frac{1*(1 - 2^{n - 1})}{1 - 2} \\ = 2^{n - 1} + 2^{n - 1} - 1 \\ = 2^n - 1 \]

class Solution {
public:
    // S_n的长度为2^n - 1，因此S_n是由2^(n - 1) - 1 + 1 + 2^(n - 1) - 1构成的。所以中间放'1'的地方是2^(n-1)
    char findKthBit(int n, int k) {
        // 当k为1时，恒为0，如果没有这一行，当n = 1,k = 1时会判定为1
        if(k == 1)
            return '0';
        // 中间值，是当前字符串放'1'的位置
        int mid = 1 << (n - 1);
        if(mid == k)
            return '1';
        else
        {
            // 如果k<mid，在前半字符串中递归搜索
            if(k < mid)
                return findKthBit(n - 1, k);
            else
                // 如果k > mid，在前半字符串的反转中搜索，等效为将k变换后搜索新的k
                return invert(findKthBit(n - 1, mid * 2 - k));
        }
    }
private:
    char invert(char ch)
    {
        return (char)('1' - ch + '0'); // 虽然条件传送可以避免后续步骤中的分支预测错误惩罚，但当前分支依旧会有惩罚，因此使用算数运算可以避免这种分支预测错误带来的惩罚。
        // return ch == '0' ? '1' : '0';
    }
};