Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > инвертировать

Автор: Streng 4.5.2006, 07:57

У меня есть 2-х байтовое знаковое целое число. Мне нужно инвертировать в нем каждый четный бит... Как это сделать в с++?

Автор: LPBOY 4.5.2006, 08:33

Самое простое, что у меня получилось, это вот так:

Код


number = (number & 0xAAAA) | (~number & 0x5555);

Автор: likehood 4.5.2006, 08:43

А можно и так:

Код


number ^= 0xAAAA;

Автор: LPBOY 4.5.2006, 08:48

Действительно...
Только разве не так?

Код


number ^= 0x5555;

Автор: likehood 4.5.2006, 09:00

Если биты отсчитывать с нуля, то да.

Автор: Streng 4.5.2006, 10:52

Не получается
Например беру число 546-в двоичном виде это 1000100010
В ответе получается 22391 это 101011101110111

Автор: likehood 4.5.2006, 10:59

Как же не получается? Каждый четный бит (крайний правый бит нулеовй, т.е. четный) и вправду инвертирован, а нечетные биты не тронуты. Что тебе не нравится?

Автор: Streng 4.5.2006, 11:15

А разьве ответ должен быть не 1101110111? Откуда столько лишних разрядов?

Автор: likehood 4.5.2006, 11:25

Инвертируются все два байта, а не только нужная тебе часть числа (твое число дополняется слева нулями до 2-х байт).

Автор: Streng 4.5.2006, 13:25

А реально сделать так чтобы инвертировались четные байты только в самом числе?

Автор: Fazil6 4.5.2006, 13:31

главное правильная маска - и инвертируй что хочешь.

Цитата

А реально сделать так чтобы инвертировались четные байты только в самом числе?

абсолютно непонятно что ты хочешь сделать

Автор: likehood 4.5.2006, 14:21

Надо сначала узнать где находится крайняя левая еденица, для этого надо последовательно сравнивать число с 0x0001, 0x0002, 0x004, 0x008 и т.д. Затем надо сформировать нужную маску. Только зачем тебе это надо?

Автор: LuckLess 4.5.2006, 15:39

Цитата(baronp @ 4.5.2006, 14:21

)

тогда уж лучне начать слева, чем справа.
т.е. сравнивать с 0x8000 , 0x4000 , 0x2000 , 0x1000 , 0x0800 ..и т.д.

Автор: likehood 4.5.2006, 15:48

Чем это лучше? Для данного числа пожалуй, но в общем случае - все равно.

Автор: LuckLess 4.5.2006, 16:47

baronp,
если идти справа налево, но для того чтобы найти левую границу надо будет пройти ВСЕ число.
а если идти слева направо, до достаточно найти 1-й установленный разряд.
этим и лучше.

Автор: sergejzr 4.5.2006, 17:18

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

Код


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

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

Автор: likehood 4.5.2006, 17:22

Код


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

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

Автор: LuckLess 4.5.2006, 17:30

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

Код

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

Автор: likehood 4.5.2006, 17:44

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

Автор: LuckLess 4.5.2006, 18:13

посмотри сам.
во первых твой вариант давал неправельный результат.
надо было в конце еще 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

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

Автор: LuckLess 4.5.2006, 18:42

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

Автор: LuckLess 4.5.2006, 19:30

вот

Код


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);
   }

Автор: likehood 4.5.2006, 20:57

мой вариант:

Код


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

Кстати, отличная идея - взять полную маску 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

я чуть переделал.
так как с ошибкой было
у меня моя функция выиграывет почти в 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";
   

   }

Автор: likehood 4.5.2006, 21:58

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

Автор: maxim1000 4.5.2006, 23:42

а так?

Код


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);
}

Автор: Streng 5.5.2006, 00:07

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

Автор: LuckLess 5.5.2006, 00:17

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

Автор: maxim1000 5.5.2006, 00:40

странно
видать, что-то не то с измерением времени
у меня Func2 было 480
Func3 - 90
(иначе я б и не написал её сюда)
покопаюсь ещё...

Автор: maxim1000 5.5.2006, 01:18

А... всё понятно...
у меня была включена оптимизация на максимум и я убрал вывод rezult*
умный компилятор, наверное, вообще выкинул все вычисления smile

нннда... выходит, моя функция медленнее smile

а я-то думал с умным видом сказать "вот это - метод бисекции" smile