비트 쉬프트를 사용하여 정수 제곱근을 찾는 가장 빠른 방법은 무엇입니까?

Question

숫자 (정수)의 제곱근 (정수)을 계산하는 가장 빠른 방법을 찾고있었습니다.

short isqrt(short num) { 
    short res = 0; 
    short bit = 1 << 14; // The second-to-top bit is set: 1L<<30 for long 
    // "bit" starts at the highest power of four <= the argument. 
    while (bit > num) 
     bit >>= 2; 
    while (bit != 0) { 
     if (num >= res + bit) { 
      num -= res + bit; 
      res = (res >> 1) + bit; 
     } 
     else 
      res >>= 1; 
     bit >>= 2; 
    } 
    return res; 
} 

: 나는 주어진 숫자가 완벽한 정사각형이 아닌 경우 (숫자의 제곱근 (의 경우 완벽한 사각형) 또는 가까운 낮은 정사각형의 제곱근을 발견 위키 피 디아에서이 솔루션을 통해 온 알고리즘을 추적하기 위해 많은 테스트를 시도했지만 while(bit!=0) 부분을 이해할 수없는 것 같습니다.

Answer 1

몇 가지 작은 예제도 추적했는데, 생각났습니다. . 내가 이해하는 한 최선의 알고리즘은 최상위 비트에서 최하위 비트까지 한 번에 한 자리의 이진수로 대답을 구성합니다.

"num_init"을 함수 시작 부분의 num 값으로 둡니다. 어떤 반복에서 우리는 그 비트가 4^x이고 그 num이 어떤 값 "num_curr"과 같다는 것을 가정합니다 (비트가 0이 될 때까지 그것은 항상 4의 거듭 제곱입니다). 그러면 res는 y * 2^(x + 1)의 형식을 취합니다. 여기서 y^2 + num_curr = num_init이고 y는 실제 답변보다 작지만 2^x 이내입니다.

num, res 및 bit의 값에 대한이 불변 값이 중요합니다. 이 코드에서 수행되는 방법은

while (bit != 0) { 
    .... 
} 

우리의 가상 포인터가 왼쪽에서 오른쪽으로 이동하는 것을하고, 각 단계에서 우리는이 비트가 0 또는

1. if 문 최초의 것입니다 여부를 결정 상상의 "구축 된"정수가 y와 같다고 가정하고 우리는 2^x 비트를보고 있습니다. 그런 다음 num의 원래 값이 적어도 (y + 2^x)^2 = y^2 + y * 2 (x + 1) + 4^x이면 비트가 1입니다. 즉, 해당 점에서 num의 값이 적어도 y * 2^(x + 1) + 4^x이면 비트가 1입니다 (num의 값이 y^2만큼 떨어진 불변량이 있으므로) . 편리하게도 res = y * 2^(x + 1) 및 bit = 4^x. 우리는 필요한 다음 업데이트 고해상도 및 NUM은 불변을 유지하는 경우 우리의 상상 지점에 1 개 비트를 추가

if (num >= res + bit) { 
    num -= res + bit; 
    res = (res >> 1) + bit; 
} 
else 
    res >>= 1; 

뒤에 점을 얻는다. 마지막으로

bit >>= 2; 

비트를 업데이트하고 모든 것을 한 단계로 이동합니다.