# pow1 n: 15의 경우 i = 0~(15-1): 15회 반복문 실행, 시간복잡도 n번 반복 × 반복마다 일정한 연산, O(n)
# def pow1(n):
#     p = 1
#     for i in range(n): 
#         p = p*2
#         print('i: ', i) 
#     return p

# n = int(input('자연수를 입력하세요: '))
# p = pow1(n)
# print(p)

# pow2 n: 15의 경우 n>>1 로 쉬프트연산으로 n이 2의 배수일때마다 1/2 씩 줄어듬 
# n : 15 → 7 → 3 → 1 → 0 반복문 실행,  시간복잡도 O(log n)
def pow2(n):
    d = 2
    p = 1
    i = 1
    while n>0:
        if n%2 ==1:
            p=p*d
        d=d*d
        n=n>>1
        i += i
        print('n: i: ', n, i)
    return p

n = int(input('자연수를 입력하세요: '))
p = pow2(n)
print(p)