항상 양수 값을 가지기 때문에 프로그램에서 루프가 종료됩니까?

Question

long long fast_exp(long long int base,long long int exp,int p) { 
int res=1; 
while(exp>0) { 
if(exp%2==1) 
{res=(res*base)%p;} 
exp=exp>>1; 
base=(base*base)%p; 

} 
return res; 
} 

이것은 모듈러 지수 함수의 함수입니다. 나는 while loop에 대해 물어보고 싶다. 이 루프는 언제 종료됩니까? exp은 항상 0보다 큽니다. 따라서이 루프가 실행되는 방식과 줄마다 어떻게 작동하는지이 루프를 이해하지 못합니다. 나는이 루프의 접근법을 이해하지 못한다.

Answer 1

먼저 코드의 형식을 지정해야합니다. 그렇지 않으면 잘못 읽습니다.

long long fast_exp(long long int base, long long int exp, int p) { 
    int res = 1; 
    while (exp > 0) { 
     if (exp % 2 == 1) { 
      res = (res * base) % p; 
     } 
     exp = exp >> 1; // Note 
     base = (base * base) % p; 
    } 
    return res; 
} 

참고 의견으로 라인. exp은 루프 반복마다 1 씩 오른쪽으로 이동하므로 결국 0에 도달하여 루프를 종료합니다.

Wikipedia이 알고리즘을 잘 설명하므로 반복 할 필요가 없습니다. Wikipedia가 보여주는 의사 코드는 코드와 거의 동일합니다. 줄 단위로 비교하십시오.

는 여기에 몇 가지 실수가 있습니다

했어야 계수가 int p로 제공됩니다

• , long long plong long res