VPF::инвертировать - Форум программистов

sergejzr

Дата 4.5.2006, 17:18 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360

Берёшь своё число, определяешь следущую степень двойки, отнимаешь еденицу и делаешь &

Код


int number =32540;//твоё число
int x=1;
while((x<<=1)<=number);//ищем степень 
x--; //вычитаем единицу
number ^= (x&0x5555); //ксорим

где то так "с лёту"

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

likehood

Дата 4.5.2006, 17:22 (ссылка)

(нет голосов)

Загрузка ...

666

Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24

Код


    unsigned short x = 0x45, mask = 1, i=0;
    for (; x >= mask; i++)
        mask <<= 1;

В итоге i содержит номер старшей еденицы числа х, только х конечно же беззнаковое (для операции сравнения), а не знаковое, как было заявлено.

LuckLess

Дата 4.5.2006, 17:30 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1

тоже самое, только быстрее.

Код

    
unsigned short x = 0x45, mask = 0x8000, i=0;
    for (; !(x&mask); i++)
        mask >>= 1;

Это сообщение отредактировал(а) LuckLess - 4.5.2006, 17:43

likehood

Дата 4.5.2006, 17:44 (ссылка)

(нет голосов)

Загрузка ...

666

Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24

точно быстрее? мой цикл требует 7 итераций а твой 9 (7+9=16==sizeof(short))

LuckLess

Дата 4.5.2006, 18:13 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1

посмотри сам.
во первых твой вариант давал неправельный результат.
надо было в конце еще 1 битовый здвиг делать в обр. сторону.

во вторых твой вариант не может работать с маской unsigned short , так как она переполняеться!!
поэтому в примерах маска 4 байта.
сделал и себе маску 4 байты , так как если сделать ее 2 , то вычисления становяться медленнее в 4-5 раз, чего и следовало ожидать.
вот сравни результаты.

Код


#include <iostream>
#include <windows.h>
typedef unsigned short ushort;

ushort func1(ushort x)
   {
   unsigned int mask = 1;
   for (; x >= mask;)
        mask <<= 1;
   mask >>= 1;
   return mask;
   }

ushort func2(ushort x)
   {
   if (x==0) return 1;
   unsigned int mask = 0x8000;
   for (; !(x&mask);)
      mask >>= 1;
   return mask;
   }


void main (void)
   {
   unsigned int t1 = 0, t2 = 0;
   int val1 = 0, val2 = 0;
   t1 = GetTickCount();
   for (int k = 0; k < 500; ++k)
      for (ushort i = 0; i != 0xffff; ++i)
         val1 += func1(i);
   t1 = GetTickCount() - t1;

   t2 = GetTickCount();
   for (int k = 0; k < 500; ++k)
      for (ushort i = 0; i != 0xffff; ++i)
         val2 += func2(i);
   t2 = GetTickCount() - t2;

   std::cout << val1 << " " << t1 << "\n"
      << val2 << " " << t2;

   }

likehood

Дата 4.5.2006, 18:34 (ссылка)

(нет голосов)

Загрузка ...

666

Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24

На счет переполнения - согласен, лучше маску делать с запасом.
Что касается дополнительного сдвига, то это зависит от того, что ты потом с этой маской будешь делать. Нам ведь нужна такая маска: ....10101010, а как ее получить в твоем алгоритме? Ведь не на основе же вычесленной mask'и.
Скорость твоего варианта больше (в основном благодаря замене сравнения битовой операцией), это так. Но надо решить всю задачу целиком и сравнить, тогда и посмотрим.
ЗЫ !(x&mask) - хорошо придумал, я бы так просто не догадался.

LuckLess

Дата 4.5.2006, 18:42 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1

чесно говоря я уже забыл зачем мы ее считали эту маску))
приду домой минут через 30, напишу полностью задачу))
и ты напиши.
сравним скорости ))

LuckLess

Дата 4.5.2006, 19:30 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1

вот

Код


ushort Func2(ushort val)
   {
   if (!val) return 0;
   unsigned int finalMask= 0;
   unsigned int curMask = 0x10000;
   while ( !(val&curMask) ) finalMask |= curMask>>=1;
   return (val^0x5555)&(~finalMask);
   }

Это сообщение отредактировал(а) LuckLess - 4.5.2006, 19:34

likehood

Дата 4.5.2006, 20:57 (ссылка)

(нет голосов)

Загрузка ...

666

Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24

мой вариант:

Код


ushort Func1(ushort val)
{
    if (!val) return 0;
    uint curMask = 1, finalMask = 0xFFFFFFFF;
    while (val >= curMask) {
        finalMask <<= 1;
        curMask <<= 1;
    }
    return val ^ (0x5555 & (~finalMask));    
}

likehood

Дата 4.5.2006, 21:33 (ссылка)

(нет голосов)

Загрузка ...

666

Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24

Кстати, отличная идея - взять полную маску 0х5555 и обрезать нужное число разрядов.
Я то сначала хотел получать эту маску по одному биту в цикле, а тут взял...

Код


0x5555 & (~finalMask)

...и никаких проблем!

Добавлено @ 21:34
Что касается скорости, твой вариант где-то в 1.5 раза быстрее, так что и вправду лучше начинать со старших разрядов. Правда в твоем коде есть одна неточность, из-за чего иногда получается неверный результат. Вот мой вариант твоего кода:

Код


ushort Func2(ushort val)    
{
   if (!val) return 0;
   unsigned int finalMask= 0;
   unsigned int curMask = 0x80000;
   while ( !(val&curMask) ) { finalMask |= curMask; curMask>>=1; }
   return (val^0x5555)&(~finalMask);    
}

Кстати, только щас заметил пост sergej.z'а, как же я его проглядел?
Отличная идея - вычесть из маски 1 - намного красивее моего варианта.
Но Func2 все же должен работать быстрее.

LuckLess

Дата 4.5.2006, 21:45 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1

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

Код


typedef unsigned short ushort;
typedef unsigned int uint;

ushort Func2(ushort val)
   {
   if (!val) return 0;
   uint finalMask= 0;
   uint curMask = 0x8000;
   while ( !(val&curMask) ) finalMask |= curMask,curMask>>=1;
   return (val^0x5555)&(~finalMask);
   }

ushort Func1(ushort val)
{
    if (!val) return 0;
    uint curMask = 1, finalMask = 0xFFFFFFFF;
    while (val >= curMask) {
        finalMask <<= 1;
        curMask <<= 1;
    }
    return val ^ (0x5555 & (~finalMask));    
}


void main(void)
   {
   uint rezult1 = 0, rezult2 = 0;
   uint time1 = 0, time2 = 0;

   for (int i = 0; i < 0x10000; ++i)
      if (Func1(i) != Func2(i))
         {
         std::cout << "error " << i << "\n"
            <<Func1(i) << " " << Func2(i);
         return;
         }

   time1 = GetTickCount();
   for (int loops = 0; loops < 1000; ++loops)
      for (ushort i = 0;;++i)
         {
         rezult1 += Func1(i);
         if (i == 0xffff) break;
         }
   time1 = GetTickCount() - time1; 

   time2 = GetTickCount();
   for (int loops = 0; loops < 1000; ++loops)
      for (ushort i = 0;;++i)
         {
         rezult2 += Func2(i);
         if (i == 0xffff) break;
         }
   time2 = GetTickCount() - time2; 

   std::cout << "Rezult for Func1 = " << rezult1 << " time = " << time1 << "\n"
      << "Rezult for Func2 = " << rezult2 << " time = " << time2 << "\n";
   

   }

Это сообщение отредактировал(а) LuckLess - 4.5.2006, 21:46

likehood

Дата 4.5.2006, 21:58 (ссылка)

(нет голосов)

Загрузка ...

666

Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24

Выигрыш, конечно, зависит от компилера и его настроек, но все равно разница очевидна.

maxim1000

Дата 4.5.2006, 23:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110

а так?

Код


ushort Func3(ushort val)
{
    if (!val) return 0;
    int log=0;
    uint tempval=val;
    if(tempval>=1<<8)
    {
      log+=8;
      tempval>>=8;
    }
    if(tempval>=1<<4)
    {
      log+=4;
      tempval>>=4;
    }
    if(tempval>=1<<2)
    {
      log+=2;
      tempval>>=2;
    }
    if(tempval>=1<<1)
    {
      log+=1;
      tempval>>=1;
    }
    if(tempval)
      log+=1;
    uint finalMask=(1<<log)-1;
    return (val^0x5555)&(finalMask);
}

--------------------

qqq

Streng

Дата 5.5.2006, 00:07 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 38
Регистрация: 27.4.2006

Репутация: нет
Всего: нет

Большое спасибо за помощь!!!

LuckLess

Дата 5.5.2006, 00:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1

maxim1000,
результаты

Код


#include <iostream>
#include <string>
#include <windows.h>

typedef unsigned short ushort;
typedef unsigned int uint;


ushort Func2(ushort val)
   {
   if (!val) return 0;
   uint finalMask= 0;
   uint curMask = 0x8000;
   while ( !(val&curMask) ) finalMask |= curMask,curMask>>=1;
   return (val^0x5555)&(~finalMask);
   }

ushort Func1(ushort val)
   {
   if (!val) return 0;
   uint curMask = 1, finalMask = 0xFFFFFFFF;
   while (val >= curMask) {
      finalMask <<= 1;
      curMask <<= 1;
      }
   return val ^ (0x5555 & (~finalMask));    
   }

ushort Func3(ushort val)
{
    if (!val) return 0;
    int log=0;
    uint tempval=val;
    if(tempval>=1<<8)
    {
      log+=8;
      tempval>>=8;
    }
    if(tempval>=1<<4)
    {
      log+=4;
      tempval>>=4;
    }
    if(tempval>=1<<2)
    {
      log+=2;
      tempval>>=2;
    }
    if(tempval>=1<<1)
    {
      log+=1;
      tempval>>=1;
    }
    if(tempval)
      log+=1;
    uint finalMask=(1<<log)-1;
    return (val^0x5555)&(finalMask);
}


void main(void)
   {
   uint rezult1 = 0, rezult2 = 0, rezult3 = 0;;
   uint time1 = 0, time2 = 0, time3 = 0;

   for (int i = 0; i < 0x10000; ++i)
      if (Func1(i) != Func2(i) || Func2(i) != Func3(i))
         {
         std::cout << "error " << i << "\n"
            <<Func1(i) << " " << Func2(i) << " " << Func3(i);
         return;
         }

   time1 = GetTickCount();
   for (int loops = 0; loops < 1000; ++loops)
      for (ushort i = 0;;++i)
         {
         rezult1 += Func1(i);
         if (i == 0xffff) break;
         }
   time1 = GetTickCount() - time1; 

   time2 = GetTickCount();
   for (int loops = 0; loops < 1000; ++loops)
      for (ushort i = 0;;++i)
         {
         rezult2 += Func2(i);
         if (i == 0xffff) break;
         }
   time2 = GetTickCount() - time2; 

   time3= GetTickCount();
   for (int loops = 0; loops < 1000; ++loops)
      for (ushort i = 0;;++i)
         {
         rezult3 += Func3(i);
         if (i == 0xffff) break;
         }
   time3 = GetTickCount() - time3; 

   std::cout << "Rezult for Func1 = " << rezult1 << " time = " << time1 << "\n"
         << "Rezult for Func2 = " << rezult2 << " time = " << time2 << "\n"
         << "Rezult for Func3 = " << rezult3 << " time = " << time3 << "\n";

   }

8000
1000
2000

т.е. моя функция пока впереди планеты всей smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »