이분 쾌속 멱
2 분 쾌속 멱 은 b 의 2 진 특징 을 이용 하여 a ^ b 를 빠르게 구 하 는 알고리즘 입 니 다.
예 를 들 면:
a = 2, b = 35
b 의 이 진 표현 형식 은 100011 이다.
a ^ b = (2 ^ 32) * (2 ^ 2) * (2 ^ 1)
이런 생각 이 생 긴 후에 b 번 순환 할 필요 가 없다.
b 의 이 진 이 n 위 를 나타 낸다 고 가정 하면 뒤에서 1 - n 위, 초기 결 과 는 1 이다.지금 은 마지막 자리 부터 시작 해 야 합 니 다. 이 자리 가 0 이면 생략 하고 이 자리 가 1 이면 결 과 는 a ^ (2 ^ 현재 위치 번호) 를 곱 합 니 다.마지막 으로 얻 은 결 과 는 a ^ b 입 니 다.이렇게 순환 적 으로 실행 하 는 횟수 는 b 의 바 이 너 리 로 표시 하 는 자릿수 로 b 보다 훨씬 적다.
long long bigpow(int x, int y)
{
long long ret = 1;
long long tmp = x;
while (y > 0)
{
if (y & 1) ret *= tmp;
y >>= 1;
tmp *= tmp;
}
return ret;
}상기 코드 의 함수 입력 매개 변 수 는 두 개의 정형 값 x 와 y 로 x ^ y 의 값 을 되 돌려 줍 니 다.반환 값 과 임시 변 수 는 범위 가 충분 한 숫자 형식 으로 설정 해 야 합 니 다. 그렇지 않 으 면 넘 칠 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
