bin_palindrome.py

def bin_palindrome(n):
    """Checks whether binary representation of integer n is a palindrome in O(#1)."""
    ones = []
    while n > 0:
        # find position j of least significant lit bit (one); x = 2^j
        j = (n & (n - 1)) ^ n
        ones.append(j)
        n -= j

    if len(ones) == 0:
        return True
    elif len(ones) == 1:
        return ones[0] == 1

    for i in range(len(ones) - 1):
        # math! 2^i / 2^j = 2^(i – j)
        if ones[i + 1] / ones[i] != ones[-i - 1] / ones[-i - 2]:
            return False

    return True