алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равно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;
}

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

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

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

1) линейный поиск

unsigned f(unsigned const x)
{
    unsigned y = 1;
    while(y<x && y!=0) // обратите внимание на проверку нуля! мы можем нарваться на переполнение
        y <<= 1;
    return y;
}

2) двоичный поиск

unsigned f(unsigned const x)
{
    unsigned i=0, j=sizeof(unsigned)*CHAR_BIT; // ищем в интервале [i,j)
    while(i<j)
    {
        unsigned const m=(i+j)/2;
        unsigned const y=1<<m;
        
        if(x < y)
            j=m;
        else if(y < x)
            i=m+1;
        else
        {
            i=m;
            break;
        }
    }
    return 1<<i;
}

3) двоичный поиск, переосмысленный

unsigned f(unsigned const x, unsigned const bit = sizeof(unsigned)*CHAR_BIT/2)
{
    if(bit==0)
        return 1;
    else if(x < (1<<bit))
        return f(x, bit/2);
    else
        return f(x>>bit, bit/2)<<bit;
}

4) логарифмы

unsigned f(unsigned const x)
{
    return 1<<(unsigned)ceil(log(x)/log(2));
}

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

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

А lookup массивы разрешено использовать?

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

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

Для IEEE'шных double (64 бита) и 32-битных unsigned int'ов <= 2^31 :

// Number of leading zeroes
int nlz( unsigned k ) 
{
    union 
    {
        unsigned asInt[2]; 
        double asDouble; 
    }; 
    
    asDouble = static_cast<double>( k ) + 0.5; 
    return 1054 - (asInt[1] >> 20); 
} 

unsigned top2( unsigned n )
{
  return 1 << ( 32 - nlz( n - 1 ) );
}

P.S. Все (c) Hacker's Delight

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

А>алгоритм без циклов для нахождения степени двойки, бОльшей (ну или равноq если число и есть степень двойки) данного числа, например
А>15 ==> 16
А>200 ==> 256
А>7923 ==> 8192
Не знаю, на сколько явными не должны быть циклы, но я б слепил что-нить подобное:
int func(int input_num)
{
char buf[100];
itoa(input_num,buf,2);
int length = strlen(buf);
output_num = 1;
output_num <<= length-1;
if (output_num < input_num)
{
output_num *= 2;
}
return output_num;
}

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

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

Подумал спокойно — вывод, моё решение можно отправлять в КУ в раздел ещё один пример индусского кода

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

C>Подумал спокойно — вывод, моё решение можно отправлять в КУ в раздел ещё один пример индусского кода

Зато прикольно. Я думал это стёб такой

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

E>Зато прикольно. Я думал это стёб такой

Спасибо, что так подумали — у меня бывает иногда, включаю тупого неожиданно сам для себя, а потом удивляюсь, как мне вообще такое в голову могло придти, вроде не курил ничего . Хотя в 1 случае из 10, такой "нестандартный" взгляд приводит к интересным результатам.

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

ВН>Здравствуйте, 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 надо сначала уменьшить на 1, чтобы удовлетворить условию "ну или равноq если число и есть степень двойки". Если этого не сделать, то легко видеть, что, например, для 16 алгоритм выдаст ответ 32 вместо правильных 16.

ЗЫ. Все-таки лучше bsr-а ничего не придумаешь, так что кое-где ассемблер все же рулит . Интересно, существует ли код на C++, который заставит студию использовать bsr?