Pers.narod.ru. Алгоритмы. Степень двойки, ближайшая сверху к заданному числу

Вот, народу понадобилась функция для расчёта размера буферов, чтоб кратными степени 2 были... посмотрел - парятся, какие-то циклические возведения числа в степень и рекурсии выдумывают... меж тем, на побитовых операциях можно сделать простое и красивое решение:

#include <iostream.h>

long clp2(long x) { 
 //Ищет и возвращает ближайшую к x сверху степень двойки
 //Вообще говоря, предполагает, что число 32-разрядное
 x--;
 for (int p=1; p<32; p<<=1) x |= (x >> p);
 return ++x;
}

void main () {
 long x;
 cout << "x=";
 cin >> x;
 cout << clp2(x);
}

Можно, конечно, попытаться быть ещё круче, раз всё равно предполагаем 32-разрядный long, предположим и 64-разрядный double:

long clp2(long x) { 
 union { double f; long i[2]; } convert;
 convert.f = x;
 if ((convert.i[1] & 0xFFFFF) | convert.i[0]) return 1<<((convert.i[1]>>20) - 0x3FE);
 else return x;
}

Как видите, здесь вообще нет цикла, но есть union и один-единственный условный оператор.

Единственный "минус" - будет работать не во всех средах, так, в старом Borland C++ 3.1 не сработало, а вот в C++ Builder 6 - уже да. Также быстродействие будет зависеть от аппаратной реализации типа double.

Но и классическому "школьному" решению с вычислением степеней двойки нельзя отказать в достоинствах, тем более, что вычисление степеней в данном случае тоже можно оптимизировать операцией побитового сдвига:

long clp2(long x) {
 long p2=1;
 while (1) {
  if (p2>=x) return p2;
  p2<<=1;
 }
 return 0;
}

Рейтинг@Mail.ru

вверх гостевая; E-mail
Hosted by uCoz