力扣779，第K个语法符号(优雅二分)

class Solution {
public:
    int kthGrammar(int n, int k) {
        //第n行共有2^(n - 1)个数
        //如果k > 2^(n - 1) / 2 说明在后半段, 此时可以转换为前半段
        //即k = k - 2^(n - 1) / 2, 此时需要换一次方向
        //否则 k = k;无需修改方向
        //最后蒋规模缩小一半,直至规模为1

        int s = 2 << (n - 1);
        int turn_count = 0;
        int res = -1;
        while (s > 1) {
            s >>= 1;
            if (k > s) {
                k -= s;
                turn_count ++;
            }
        }
        
        if (turn_count % 2) res = 1;
        else res = 0;
        return res;

    }
};