50. Pow(x, n)

https://leetcode.com/problems/powx-n/description/?envType=featured-list&envId=top-google-questions%3FenvType%3Dfeatured-list&envId=top-google-questions

input :

• x, n

output :

• x^n의 결과를 출력하시오.

조건 :

---

Solution explain : Solution1

idea

• 재귀나 반복문을 쓰면 n이 정수형의 전체값을 커버하기에 21억 이상의 연산량이 필요하다.
  
  
• 해설에 따라 bit masking을 사용하자.
• n이 음수인 경우에는 곱해지는 값이 분수이니까 x를 분수로 변경한다.
• 비트 벡터의 구분이 될 수 있는 것은 가장 뒤에 위치한 원소가 1인 경우이기에
• 해당 값은 나머지가 1인 경우, 1과 &연산을 한 경우 결과가 1인 경우로 구분할 수 있다.
• 해당 조건을 만족하는 경우 반환값에 곱해질 값을 곱한다.
• 기본적으로 반복문에선 계속 곱해지는 값이 제곱되는 형태가 있고
• n의 경우 계속 2로 나누는 형태를 띈다.

주의

class Solution:
    def myPow(self, x: float, n: int) -> float:
        ret = 1

        if n < 0:
            x = 1 / x
            n = -n

        multiply = x
        while n != 0:
            if n % 2 == 1:
                ret *= multiply
            multiply *= multiply 
            n = n >> 1
        
        return ret