C++: степень двойки, ближайшая сверху к заданному числу

Вот, народу понадобилась функция для расчёта размера буферов, чтоб кратными степени 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;
}

Если надо проверить, является ли натуральное число value степенью двойки, вот красивая функция. Она считает ноль степенью двойки, если это не так, добавьте дополнительное условие в тело is_power_of_two.

#include <iostream>
using namespace std;

int is_power_of_two (int value) {
 return !(value & (value - 1));
}

int main() {
 cout << endl << is_power_of_two(0); //0 и 1 - степень двойки
 cout << endl << is_power_of_two(1); 
 cout << endl << is_power_of_two(12);
 cout << endl << is_power_of_two(127);
 cout << endl << is_power_of_two(128);
 cin.sync(); cin.get(); return 0;
}

27.03.2012, 12:19 [18650 просмотров]