1

Тема: двоичное возведение в степень

Я чет не понял зачем сложный if.. онж по сути добавляет итерацию цикла лишнюю после каждого срабатывания n&1

while (n)
        if (n & 1) {
            res *= a;
            --n;
        }
        else {
            a *= a;
            n >>= 1;
        }

не прощели так? прост проходимся по числам вида n^(2^k) , если нужно - домножаем

while(n) {
    if(n & 1)
        res *= a;
    a *= a;
    n = n >> 1;
}

2

Re: двоичное возведение в степень

Ок, добавлю и такой вариант, хотя мне он не кажется логичным smile Один иф по сравнению с временем работы умножения мало что меняет, но лучше, конечно, привести и более оптимизированный вариант. Спасибо за фидбэк.

3

Re: двоичное возведение в степень

Да на самом деле умножений тут ровно столько же кроме случая когда n == 1.  просто пользуемся фактом что перед нечетным всегда четное.

4

Re: двоичное возведение в степень

Хм.. а мне на оборот какт странно было читать про n/2 и n/2.. прост раскладываем n не на n/2 и n/2 а сразу в сумму степеней двойки. Впрочем не суть)