Привет!

Можно ли округлить число до степени двойки вверх в одно выражение?
Например:
1 -> 2
2 -> 2
3 -> 4
12 -> 16
15 -> 16
18 -> 32
33 -> 64
и т.д.

пока лучшее, что я придумал

int   size_align( int  size)
{
    register int      k;
    register int      l;
    
    for (k = size; (l = k & (k - 1)) != 0; k = l);
    
    return (size + (k - 1)) & (~(k - 1));
}

Хотелось бы в обойтись без цикла.

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

M>Привет!

M>Можно ли округлить число до степени двойки вверх в одно выражение?
M>пока лучшее, что я придумал

int   size_align( int  size)
{
    register int      k;
    register int      l;
    
    for (k = size; (l = k & (k - 1)) != 0; k = l);
    
    return (size + (k - 1)) & (~(k - 1));
}

так попроще вроде ...

DWORD   size_align( DWORD  size)
{
    size--;
    for (DWORD d=0x80000000; (d & size) == 0 ; d>>=1);
    return d<<1;
}

а без цикла, думаю, облизнёшься

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

M>Можно ли округлить число до степени двойки вверх в одно выражение?
M>Например:
M>1 -> 2
M>2 -> 2
M>3 -> 4
M>12 -> 16
M>15 -> 16
M>18 -> 32
M>33 -> 64
M>и т.д.

M>пока лучшее, что я придумал

M>Хотелось бы в обойтись без цикла.

size:=1 shl ceil(ln(size)/ln(2));

Только вряд-ли это будет быстрее

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

Вариант 1
Идея такая: нужно найти старший значащий бит, затем проверить, не равно ли наше число 2**номер_бита (случай 2 -> 2), и если нет — увеличить номер.
Искать номер старшего значащего бита можно с помощью бинарного поиска.

Вариант 2
Создать заранее массив степеней двойки, а потом искать в нем:

const int nSize = 32;
std::vector<unsigned int> aPowers(nSize, 0);
for(int i = 1; i < nSize; ++i)
   aPowers[i] = aPowers[i-1]*2;

...

int   size_align( int  size, const std::vector<unsigned int>& aPowers)
{
   return *lower_bound(aPowers.begin(), aPowers.end(), size);
}

Итого получаем логарифмическую сложность.
Только надо быть поаккуратнее с преобразованиями unsigned int -> int

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

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

B>Вариант 1
B>Идея такая: нужно найти старший значащий бит, затем проверить, не равно ли наше число 2**номер_бита (случай 2 -> 2), и если нет — увеличить номер.

ИМХО, лучше так

if ((size & (size - 1)) == 0)
{
    return size;
}

B>Искать номер старшего значащего бита можно с помощью бинарного поиска.

Скорее всего этот вариант в общем случае по быстрее будет, чем мой вариант.
Хотя мой вариант будет быстрее, если в числе не более 7-8 установленных битов.
Т.е. 00110000 найдет за две итерации.
Бинарный за пять (если число 32-ух битное).

Просто я подумал, если можно легко получить значение для младшего бита:

(size ^ (size - 1)) & size

То и должно быть для старшего...

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

M>Привет!

M>Можно ли округлить число до степени двойки вверх в одно выражение?

Если ввести операцию @, которая расставляет биты в обратном порядке, то кажется так (не будет работать только на нуле):

result=size|@~((@~size)^(@~size+1));

Может кто придумает как реализовать @~ одним Си-шным выражением?..

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

M>Можно ли округлить число до степени двойки вверх в одно выражение?

M>Хотелось бы в обойтись без цикла.

Ну, без цикла — или таблицей, или последовательность if, или так:

unsigned char bin_ceil(unsigned char c)
{
    return
        (c - 1 |
        c >> 1 |
        c >> 2 |
        c >> 3 |
        c >> 4 |
        c >> 5 |
        c >> 6 |
        c >> 7) + 1; // Идея понятна?
}

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

M>Привет!

M>Можно ли округлить число до степени двойки вверх в одно выражение?
M>Например:
M>1 -> 2

1 — это тоже степень двойки, так что, по идее, дожна оставаться как есть.

M>2 -> 2
M>3 -> 4
M>12 -> 16
M>15 -> 16
M>18 -> 32
M>33 -> 64
M>и т.д.

Вот вариант для чисел 1 < N <= 2**31

return ((N - 1) << 1) & ~(N - 1);

Итого:

return (N == 1) ? 2 : --N, (N << 1) & ~N;

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

L>Вот вариант для чисел 1 < N <= 2**31

L>

L>return ((N - 1) << 1) & ~(N - 1);
L>

L>Итого:
L>

L>return (N == 1) ? 2 : --N, (N << 1) & ~N;
L>

Блин, опять поторопился. Forget it.

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

M>Привет!

M>Можно ли округлить число до степени двойки вверх в одно выражение?

M> ...

Очень длинно, но не более 6 сравнений

long size_align2(long size)
{
    if(size <=0)
        return 0;
    else        

    if( size<=0x4000) // 0x1 0x4000
        if( size<=0x40) // 0x1 0x40
            if( size<=0x4) // 0x1 0x4
                if( size<=0x1) // 0x1 0x1
                    return 0x1;
                else // 0x4 0x2
                    if( size<=0x2) // 0x2 0x2
                        return 0x2;
                    else // 0x4 0x3
                        return 0x4;
            else // 0x40 0x5
                if( size<=0x10) // 0x8 0x10
                    if( size<=0x8) // 0x8 0x8
                        return 0x8;
                    else // 0x10 0x9
                        return 0x10;
                else // 0x40 0x11
                    if( size<=0x20) // 0x20 0x20
                        return 0x20;
                    else // 0x40 0x21
                        return 0x40;
        else // 0x4000 0x41
            if( size<=0x400) // 0x80 0x400
                if( size<=0x100) // 0x80 0x100
                    if( size<=0x80) // 0x80 0x80
                        return 0x80;
                    else // 0x100 0x81
                        return 0x100;
                else // 0x400 0x101
                    if( size<=0x200) // 0x200 0x200
                        return 0x200;
                    else // 0x400 0x201
                        return 0x400;
            else // 0x4000 0x401
                if( size<=0x1000) // 0x800 0x1000
                    if( size<=0x800) // 0x800 0x800
                        return 0x800;
                    else // 0x1000 0x801
                        return 0x1000;
                else // 0x4000 0x1001
                    if( size<=0x2000) // 0x2000 0x2000
                        return 0x2000;
                    else // 0x4000 0x2001
                        return 0x4000;
    else // 0x40000000 0x4001
        if( size<=0x400000) // 0x8000 0x400000
            if( size<=0x40000) // 0x8000 0x40000
                if( size<=0x10000) // 0x8000 0x10000
                    if( size<=0x8000) // 0x8000 0x8000
                        return 0x8000;
                    else // 0x10000 0x8001
                        return 0x10000;
                else // 0x40000 0x10001
                    if( size<=0x20000) // 0x20000 0x20000
                        return 0x20000;
                    else // 0x40000 0x20001
                        return 0x40000;
            else // 0x400000 0x40001
                if( size<=0x100000) // 0x80000 0x100000
                    if( size<=0x80000) // 0x80000 0x80000
                        return 0x80000;
                    else // 0x100000 0x80001
                        return 0x100000;
                else // 0x400000 0x100001
                    if( size<=0x200000) // 0x200000 0x200000
                        return 0x200000;
                    else // 0x400000 0x200001
                        return 0x400000;
        else // 0x40000000 0x400001
            if( size<=0x4000000) // 0x800000 0x4000000
                if( size<=0x1000000) // 0x800000 0x1000000
                    if( size<=0x800000) // 0x800000 0x800000
                        return 0x800000;
                    else // 0x1000000 0x800001
                        return 0x1000000;
                else // 0x4000000 0x1000001
                    if( size<=0x2000000) // 0x2000000 0x2000000
                        return 0x2000000;
                    else // 0x4000000 0x2000001
                        return 0x4000000;
            else // 0x40000000 0x4000001
                if( size<=0x10000000) // 0x8000000 0x10000000
                    if( size<=0x8000000) // 0x8000000 0x8000000
                        return 0x8000000;
                    else // 0x10000000 0x8000001
                        return 0x10000000;
                else // 0x40000000 0x10000001
                    if( size<=0x20000000) // 0x20000000 0x20000000
                        return 0x20000000;
                    else // 0x40000000 0x20000001
                        return 0x40000000;


};

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

B>Вариант 2
B>Создать заранее массив степеней двойки, а потом искать в нем:

Только можно обойтись без стд::вектора

template< class N > // беззнаковый!
N highest_bit(N n)
{
  const size_t count = sizeof(N) * CHAR_BIT;
  static const table[count];
  static bool init = false;
  if(!init)
  {
    size_t i; N b = 1;
    for(size_t i = 0; i < count; ++i, b <<= 1) table[i] = b;
    init = true;
  }

  return *lower_bound(table, table+count, n);
}

Здравствуйте, menify, Вы писали:
M>Можно ли округлить число до степени двойки вверх в одно выражение?

Log2(Size)=T;
if (T!=(int)T) T++;
return 2^T;