naf-알고리즘

?

• 각 자릿수가 +1, 0, -1로 구성
• 덧셈과 뺄섬의 연산을 최소화하기 위해서 사용

ex)
19가 있다고 가정하면 다음과 같이 표현 가능

19 = 1×2⁴ + 0×2³ + 0×2² + (-1)×2¹ + 1×2⁰
   = [1, 0, 0, -1, 1] (naf)​

1,0,-1을 활용하여서 19를 naf을 활용하여서 표현할 수 있음!

구현

while (k > 0) {
    if (k%2) {
        ai = 2 - (k % 4);
        k = k - ai;
    } else {
        ai = 0;
    }
    k = k / 2;
}

• 기본적으로 비트를 1칸씩 이동시키면서 나아감(k=k/2)
• k가 홀수인 경우에는 ai의 값을 2-(k%4) 연산을 통해서 각 비트의 값을 변화해 준다.

만약 k = 7이면,
k % 4 = 3 → ai = -1 → k = 7 - (-1) = 8

만약 k = 5이면,
k % 4 = 1 → ai = 1 → k = 5 - 1 = 4