public class Solution {
    public char FindKthBit(int n, int k) {
        static char GetBit(int inversions)
            => inversions % 2 == 0 ? '1' : '0';

        var length = (1 << n) - 1;

        int inversions;
        for (inversions = 0; k > 1; length >>= 1) {
            // check for middle
            if (k - 1 == length >> 1) {
                return GetBit(inversions);
            }

            if (k > length >> 1) {
                k = length + 1 - k;
                ++inversions;
            }
        }

        return GetBit(++inversions);
    }
}