алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
15 ==> 16
200 ==> 256
7923 ==> 8192

Если a — данное число, x — неизвестное (степень двойки):

x = (a div 2 + 1) * 2

Откуда взял задачку?

Здравствуйте, Limonadni_Joe, Вы писали:

L_J>Если a — данное число, x — неизвестное (степень двойки):
L_J>

x = (a div 2 + 1) * 2

Откуда взял задачку?

Что-то даже близко не похоже. Прочитай внимательнее условие.

Здравствуйте, <Аноним>, Вы писали:

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192

Ну, в общем есть такая идея x — данное число, N — искомая степень двойки:

double x;
long N;

N = 2 ^ ((long)((1 / log10 (2.0F)) * log10 (x)));
if (N == x)
{
    return N;
}
else
{
    return N*2;
}

Для целого любой разрядности точно быстрее будет с циклами.

Здравствуйте, Аноним, Вы писали:

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192

Здравствуйте, gwg-605, Вы писали:

G6>Для целого любой разрядности точно быстрее будет с циклами.

Будет, но тогда этой задаче будет не место в этюдах

Здравствуйте, , Вы писали:

> алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq
> если число и есть степень двойки) данного числа, например 15 ==> 16
> 200 ==> 256
> 7923 ==> 8192

unsigned int get_nearest_2_power(unsigned int pui_value)
{
 // Возвращаем 0 в случае ошибки.

 unsigned int ui_ret;
 
 // Если число 0 или само степень двойки - возвращаем его же.
 if (!((pui_value - 1) & pui_value)) {
  return pui_value;
 }

 // Если установлен старший бит - возвращаем 0 -- боимся переполнения.
 if (pui_value & 0x80000000) {
  return 0;
 }

 __asm {
  bsr eax, pui_value
  inc eax
  mov cl, al
  mov eax, 1
  shl eax, cl
  mov ui_ret, eax
 }

 return ui_ret;
}

-- Всего хорошего!
-- Alex Alexandrov, e-mail: alexandrov_alex@fromru.com

Здравствуйте, Аноним, Вы писали:

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192

для A>=2
X = (((A-1) xor (A-2)) and (A-1))*2

---
С уважением,
Лазарев Андрей.

А>>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>>15 ==> 16
А>>200 ==> 256
А>>7923 ==> 8192

T>для A>=2
T>X = (((A-1) xor (A-2)) and (A-1))*2

Глупость какую-то написал...

Здравствуйте, Аноним, Вы писали:

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192

Для 32-разрядного:

Х |= X >> 1;
Х |= X >> 2;
Х |= X >> 4;
Х |= X >> 8;
Х |= X >> 16;
X++;

Здравствуйте, Аноним, Вы писали:

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192

1. f(0)=1 (а не нуль, ибо нуль — не степень двойки, а предел на "-бесконечность", что ни числом, ни верхней границей не является).
2. нециклического решения нет (если считать и пробег по разрядам циклом). ибо для решения задачи нужно так или иначе знать разряды числа. Разные нахождения логорифма — тоже, по сути, цикл, но завуалированный вызовом самого этого логарифма.

2moder: Забыл пароль. Можно на ящик Umaxik-а послать? Он в анкете есть.

Здравствуйте, <Аноним>, Вы писали:

log — всегда по основанию 2
X — данное число
N — искомая степень


если logX — целое:
logX = logN
если logX — дробное:
целая_часть(logX)+1 = logN

Здравствуйте, oRover, Вы писали:

R>Здравствуйте, <Аноним>, Вы писали:

R>log — всегда по основанию 2
R>X — данное число
R>N — искомая степень


R>если logX — целое:
R> logX = logN
R>если logX — дробное:
R> целая_часть(logX)+1 = logN

глупость написал вместо logN — просто N

Здравствуйте, oRover, Вы писали:

R>log — всегда по основанию 2
R>X — данное число
R>N — искомая степень


R>если logX — целое:
R> logX = logN
R>если logX — дробное:
R> целая_часть(logX)+1 = logN

А чем, извините, от этого

Автор: HeaveN
Дата: 14.09.03

отличается?

Здравствуйте, Аноним, Вы писали:

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192

Если есть операция реверсирования бит в числе (назовем ее rev), то степень двойки меньше или равной x можно вычислить так:

x = rev (x);
x = rev (-x & x);

Только rev тоже делается в цикле...

Здравствуйте, Les, Вы писали:

Les>Здравствуйте, Аноним, Вы писали:

А>>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>>15 ==> 16
А>>200 ==> 256
А>>7923 ==> 8192

Les>Для 32-разрядного:

Les>Х |= X >> 1;
Les>Х |= X >> 2;
Les>Х |= X >> 4;
Les>Х |= X >> 8;
Les>Х |= X >> 16;
Les>X++;

Для N-разрядного в любом случае можно цикл развернуть — будет без цикла.
А это — как раз развернутый цикл.
ЗЫЖ идея, конечно, хорошая

Здравствуйте, Аноним, Вы писали:


А>x = rev (x);
А>x = rev (-x & x);

1. rev( x ) = x^(-1);
2. Эти формулы не катят, для простоты в 4-ч разрядах:
x = 0011b; // Было
x = rev( x ); // x==1100b
-x; // x==0100b
-x&x; // 0100b
rev(-x&x); // 1011b ???

Здравствуйте, Вадим Никулин, Вы писали:

ВН>Здравствуйте, Аноним, Вы писали:


А>>x = rev (x);
А>>x = rev (-x & x);

ВН>1. rev( x ) = x^(-1);
ВН>2. Эти формулы не катят, для простоты в 4-ч разрядах:
ВН> x = 0011b; // Было
ВН> x = rev( x ); // x==1100b
ВН> -x; // x==0100b
ВН> -x&x; // 0100b
ВН> rev(-x&x); // 1011b ???

Не понял. Если -x&x==0100, то rev(-x&x) должно быть 0010. Или я что-то не понимаю?

Кстати, формулу -x&x можно использовать, чтобы уменьшить количество циклов:

while (x & (x-1))
x += -x&x;

Тогда цикл выполняется столько раз, сколько в x единиц -1. Только надо проверить x на равенство нулю.

Здравствуйте, Аноним, Вы писали:

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192

Ответ:

Генри Уоррен, мл. Алгоритмические трюки для программистов.
Издательский дом "Вильямс", 2003.

Глава 3. Округление к степени 2
3.1. Округление к ближайшей степени 2
стр. 58
x — целон беззнаковое число
clp2(x) = 2^(log2(x)) для x > 0
= 0 для x = 0

В ближайшее время (может и сегодня) напишу рецензию.

решение простое с использованием логарифмов.
вот мой пример с циклами.

unsigned int NextPowerOfTwo(int unsigned n)
{
    int nextPowerOf2, i = 0;
    if ((n & (n - 1)) != 0) for (; (n >> (++i)) > 0 && (nextPowerOf2 = 1 << (i + 1));); else nextPowerOf2 = n;
    return nextPowerOf2;
}

а вот как решить задачку без циклов и логарифмов? вроде до меня там писали что это невозможно. так ли это?