Печать страницы - Поиск ближайшего к степени двойки

Название: Поиск ближайшего к степени двойки
Отправлено: Admin от Февраль 01, 2005, 14:33

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

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

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

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

Название: Re: Поиск ближайшего к степени двойки
Отправлено: CBapor от Март 01, 2005, 11:28

Цитата: "Admin"

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

Название: Re: Поиск ближайшего к степени двойки
Отправлено: CBapor от Март 01, 2005, 11:44

Во есче придумал - методом дихотомии.
пусть 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 от Март 01, 2005, 12:45

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

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

Название: Поиск ближайшего к степени двойки
Отправлено: CBapor от Март 02, 2005, 03:01

Цитата: "Admin"

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

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

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

Название: Поиск ближайшего к степени двойки
Отправлено: CBapor от Март 02, 2005, 03:57

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

Код:


#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 от Март 02, 2005, 06:17

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

Название: Поиск ближайшего к степени двойки
Отправлено: lepsai от Май 31, 2005, 00:31

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

Название: Поиск ближайшего к степени двойки
Отправлено: rGlory от Сентябрь 30, 2005, 23:49

Цитата: "Admin"

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

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

А если так:

Код:


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

Название: Re: Поиск ближайшего к степени двойки
Отправлено: sikuda от Июнь 19, 2008, 17:02

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

Название: Re: Поиск ближайшего к степени двойки
Отправлено: basileus от Октябрь 03, 2008, 13:24

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

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

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

Название: Re: Поиск ближайшего к степени двойки
Отправлено: serge от Март 24, 2009, 12:16

Цитата: basileus от Октябрь 03, 2008, 13:24

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

Код:

-5 & 10 == 10 != 8

Не бьёт!

Название: Re: Поиск ближайшего к степени двойки
Отправлено: m_ax от Март 24, 2009, 21:57

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

Может так ???

Название: Re: Поиск ближайшего к степени двойки
Отправлено: Winstrol от Март 25, 2009, 11:18

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

Название: Re: Поиск ближайшего к степени двойки
Отправлено: miha-ha от Март 25, 2009, 15:49

дополню:

Код:

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

Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Admin от Февраль 01, 2005, 14:33