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

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