def _bitreverse(x):
    """Reverses the bits in the byte x. E.g. 0x41 -> 0x82."""
    result = 0
    for i in range(8):
        if x & (1 << i):
            result |= (0x80 >> i)
    return result


bitreverse = [_bitreverse(i) for i in range(256)]


def value_in_sorted_bitreverse_1(start, end, rem):
    """Compute list(sorted(bitreverse[start:end]))[rem]."""
    output = 0
    position = -start
    length = end - start
    shifted_length = length
    bit = 1

    masks = [1, 3, 7, 15, 31, 63, 127, 255]
    lengths = [length & masks[i] for i in range(8)]

    for i in range(8):
        output <<= 1
        shifted_length >>= 1
        bit0s = shifted_length + (lengths[i] > (position & masks[i]))
        new_rem = rem - bit0s

        if new_rem >= 0:
            rem = new_rem
            output |= 1
            position += bit
        bit <<= 1

    return output


def value_in_sorted_bitreverse_2(start, end, rem):
    """Approximate list(sorted(bitreverse[start:end]))[rem].

    This is an approximation only in the sense that the returned value
    will not necessarily be present in bitreverse[start:end]. However, it
    nonetheless has the property that "rem" entries of bitreverse[start:end]
    are smaller than it.
    """

    length = end - start
    position = start
    i = 0
    while True:
        if length <= 1:
            break
        add = 1 << i
        length2 = (end - position + ((1<<i)-1)) // (1<<i)
        assert length == length2, (i, position, length, length2)
        even = length // 2 + (length & 1)
        odd  = length // 2
        if not (position & add):
            bit0s, bit1s = even, odd
            pos0, pos1 = position, position+add
        else:
            bit0s, bit1s = odd, even
            pos0, pos1 = position+add, position
        assert (even + odd) == length
        if rem >= bit0s:
            position = pos1
            rem -= bit0s
            length = bit1s
        else:
            assert bit0s
            position = pos0
            length = bit0s
        i = i + 1
    return _bitreverse(position)