Поиск ближайшего к степени двойки

[Admin]

Есть сигнал длины len

Хочется получить len_real, которая больше len и равна 2^N.

Тоесть надо найти ближайщую длинну к len  и кратную по размеру 2^N.

Я пока кроме просто while и сравнения ничего не могу придумать.
А это долго.

[CBapor]

Есть сигнал длины len

Хочется получить len_real, которая больше len и равна 2^N.

Тоесть надо найти ближайщую длинну к len  и кратную по размеру 2^N.

Я пока кроме просто while и сравнения ничего не могу придумать.
А это долго.

Похитрить с битами.
К примеру, если в двоичном представлении числа больше одной еденицы, то соседний ноль со старшей еденицей устанавливаем в 1, а остальные в 0.
 Или что-то вроде этого

[CBapor]

Во есче придумал - методом дихотомии.
пусть N разрядность чисел. L исходная длинна
тогда берем K1=2**(N/2)
Если K1 > L то следующее число K2=2**(N/4)
и т.п. и так пока k[m] и k[m-1] не будут соседними степеними двойки.

Прилизать алгоритм наверно и сам сможеш

К примеру для 64-разрядных чисел потребуется не более 6 -ти сравнений

наверно удобно степени двойки хранить в константном масиве
типа
const int mass[]={1,2,4,...,0x10,...};
ведь разрядность числа заранее изверсна

[Admin]

я пока вот этим обхожусь

int order=1;
while(pow(2,order)<len)
{
   order++;
}

[CBapor]

я пока вот этим обхожусь

int order=1;
while(pow(2,order)<len)
{
   order++;
}

  В среднем используемый тобой метод простого перербора дает N/2 число сравнений. (N- разрядность).  Т.е. для 32 разрядного числа это будет примерно 16 сравнений. В худшем случае это будет 32 сравнения.
  Дихотомия даст 5 сравнений как в среднем так и в худшем.
  Для оценки среднего предполагается, что len равномерно распределена по своему диапазону.
   Другое дело, если априори известно , что len невелико, (то есть имеем распределение, отличное от равномерного), тогда простой перебор может иметь преемущество в производительности.

[CBapor]

вот написал дихотомию

Код:

#include <stdio.h>
int main()
{
	unsigned len,middle,left,right;	 

	scanf("%u",&len);
	left=0,right=31;
	if( len > (1u<<right) )
	{
		printf("len is too big\n");
		return 1;
	}
	if(len <= 1u )//особый случай
		right=0;
	else
		while(left+1 < right)
		{
			middle=(left+right)/2u;

			if(len <= (1u<<middle))
				right=middle;
			else
				left=middle;
		}
	printf("power= %u new len=%u\n",right,(1u<<right));
	return 0;
}

[CBapor]

Ну а самый простой подход
  1<<((unsigned)(log2(len)+1))

[lepsai]

только log()  - дороговато

[rGlory]

я пока вот этим обхожусь

int order=1;
while(pow(2,order)<len)
{
   order++;
}

А если так:

Код:

int order = 1;
if( len ) len--;
while( len ) {
   len <<= 1;
   order >>= 1;
}

[sikuda]

А представление твоего числа в двоичной системе не подойдет:
1000100100 это между 2 в 10 и 2 в 9.

[basileus]

Вижу, среди новичков модно поднимать старые темы.
Закрою тему.
Rnd2Pwr=-len&(len+len);
Это платформонезависимое решение для целого. Несколько тактов. Если компилятор плох, то можно попробовать
Rnd2Pwr=-len&(len<<1);

Для отдельных процессоров (f.e i586+) можно написать ассемблерную функцию возращающую  номер старшего ненулевого бита, инкремент значение и установка в обнулённом регистре бита с этим новым значением)

Понимание, что есть число, сильно улучшает код.
Для плавающей запятой это +1 к экспоненте и 1 в мантиссе.

[serge]

Вижу, среди новичков модно поднимать старые темы.
Закрою тему.
Rnd2Pwr=-len&(len+len);
...

Код:

-5 & 10 == 10 != 8

Не бьёт!

[m_ax]

len_real = 2^N;
N = ceil(ln(len)/ln(2));

Может так 

[Winstrol]

http://en.wikipedia.org/wiki/Power_of_two#Algorithm_to_convert_any_number_into_nearest_power_of_two_number
 

[miha-ha]

дополню:

Код:

unsigned fun(unsigned x)
{
   x = x - 1;
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >> 16);

   return x = x + 1;
}

а вообще настоятельно рекомендую почитать: http://obuk.ru/compbook/52-algoritmicheskie-trjuki-dlja.html