битовые операции

Ответить
IMpulSE_18
Сообщения: 1
Зарегистрирован: 16 июн 2009, 11:02

битовые операции

Сообщение IMpulSE_18 » 16 июн 2009, 11:07

люди помогите пожалуста завтра прогу сдавать очень надо

дан массив unsigned short mas[4] нужно вывести числа в которых четное количество единичных бит препод сказал что надо использовать сдвиг завтра в 9 надо сдать плиз помогите или обьясните как очень надеюсь на помощь!!

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: битовые операции

Сообщение Romeo » 16 июн 2009, 12:42

Прошу не сильно бить: решение написано "в лоб". Возможно есть более изящный способ.

Код: Выделить всё

#include <iostream>

bool DoesItHaveOddAmountOfBits(unsigned short uValue)
{
   int nBitCount = 0;
   while (uValue > 0)
   {
      if (uValue & 1) ++nBitCount;
      uValue >>= 1;
   }

   return (0 == nBitCount % 2);
}

void main()
{
   unsigned short mas[] = {45, 14, 7, 105};
   for (int i = 0; i < 4; ++i)
   {
      if (DoesItHaveOddAmountOfBits(mas[i]))
      {
         std::cout << mas[i] << std::endl;
      }
   }
}
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: битовые операции

Сообщение somewhere » 16 июн 2009, 13:24

Есть еще как минимум два на мой взгляд более простых и быстрых решения:

1) Использовать таблицу, где для каждого номера элемента N будет стоять заранее известное значение (1 - если число единиц в номер четное, и 0 - в противном случае). Разумеется целесообразно если размер параметра - 1 байт.

2) В микропроцессоре есть специальный флаг PF, он установливается в 1 если число единичных битов в операнде четное. На самом деле выполнять сотни инструкций вместо одной не рационально, а сдвиги - они вообще относительно медленные операции. Выглядеть будет примерно так:

Код: Выделить всё

bool DoesItHaveOddAmountOfBits(unsigned short uValue)
{
   int res = 0;
   asm   mov ax, uValue
   asm   or ax, ax
   asm   setp byte ptr [res]
   return res;
}
It's a long way to the top if you wanna rock'n'roll

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: битовые операции

Сообщение Romeo » 16 июн 2009, 15:36

&quot писал(а):Разумеется целесообразно если размер параметра - 1 байт.
По условию задачи параметр типа unsigned short, то есть 2 байта.
&quot писал(а):2) В микропроцессоре есть специальный флаг PF, он устанавливается в 1 если число единичных битов в операнде четное.
У меня тоже была идея написать на асм, но дело в том, что задача алгоритмическая и было оговорено преподавателем, что должен использоваться сдвиг, потому я написал на С++.
&quot писал(а): ... а сдвиги - они вообще относительно медленные операции
Позволю себе не согласиться: Правый и левый сдвиг (shr, shl) на один бит - это 2 два процессорных такта, точно также как и add и sub, or, and (в случае, когда оба операнда размещены в регистрах). На самом деле более быстрой операции, чем сдвиг на один бит просто нет.

По поводу кода на асме. Я не хотел опускаться до него, но если уж есть готовый код, то можно обсудить :)

1. Следует использовать extended регистры, работа с ними занимает меньше процессорных тактов на 32 разрядных процессорах.

2. Код or ax, ax. Ничего страшного, просто выглядит путанно. Для установки флагов есть замечательная самодокументирующая себя своим именем команда test, которая делает то же самое что и or, только не меняет регистров. Почему не использовать её, ведь код тогда становится более читабельным? (я не спорю or тоже работает, я сейчас говорю о прозрачности кода) :)
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: битовые операции

Сообщение somewhere » 16 июн 2009, 18:50

Команды MOV, AND, OR, ADD и пр. еще со времен 386 всегда выполнялась за 1 такт, на 286 уже 2 такта, а вот на современных процессорах до 0.25 тактов (4 инструкции за раз, это при идеальном случае). В то время как SHL/SHR/SAL/SAR и иже с ними за 4 такта (3 такта если находятся в кеше 1 уровня). В моей библиотеке сжатия по хаффману мне удалось отказаться от 2-ух инструкций сдвигов в пользу MOV для табличных расчетов и это дало прирост в 30%. Экспериментально вычисленное время выполнения сдвиговых операций на одноядерном процессоре в среднем составляет 4.8 такта на инструкцию. До сих пор кстати руководствую многими рекомендациями по оптимизации от AMD для 486/586 процессоров и убеждаюсь что они на самом деле правы. Так например не раз убеждался что

Код: Выделить всё

sub ecx, 1
jnz @xxx
быстрее чем loop. Ну и еще довольно много прочих хитростей. А вот самая быстрая команда все таки NOP ;)
&quot писал(а):Код or ax, ax. Ничего страшного, просто выглядит путанно
Это старая привычка, со времен когда еще не было инструкции test :) И все таки считаю, что данная задача является плохим уроком по работе со сдвиговыми операциями, уж лучше старый добрый bitfuck или хотябы преобразование RGB555 -> RGB888 и обратно
It's a long way to the top if you wanna rock'n'roll

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: битовые операции

Сообщение Romeo » 17 июн 2009, 10:02

&quot писал(а):Команды MOV, AND, OR, ADD и пр. еще со времен 386 всегда выполнялась за 1 такт, на 286 уже 2 такта, а вот на современных процессорах до 0.25 тактов (4 инструкции за раз, это при идеальном случае). В то время как SHL/SHR/SAL/SAR и иже с ними за 4 такта (3 такта если находятся в кеше 1 уровня). В моей библиотеке сжатия по хаффману мне удалось отказаться от 2-ух инструкций сдвигов в пользу MOV для табличных расчетов и это дало прирост в 30%. Экспериментально вычисленное время выполнения сдвиговых операций на одноядерном процессоре в среднем составляет 4.8 такта на инструкцию.
somewhere, ну ты силён, я последний раз программировал на чистом асме в чистом DOS на четвёках :) Причём руководствовался интеактивной документашкой techhelp, была такая раньше, она описывала все параметры команд для двоек и троек, потому я и сказал, что 2 такта. Но даже тогда, сдвиг работал два такта (при условии, что сдвиг на делается на один бит и количество бит, то есть единичка, занесены в регистр). Почему на современных процессорах это время увеличилось, интересно?
&quot писал(а):быстрее чем loop. Ну и еще довольно много прочих хитростей.
Ага, это известный факт. Ещё есть очень правильная рекомендация всячески уходить от джампов, например используя сложение с переполнением и вычитание с заёмом (adc, sbb) - при хитро продуманном алгоритме это позволяет в некотрых случаях красиво переделать конструкцию if, в состав которой входит джамп. Вообще там много нюансов есть, к сожалению не все уже помню, так как сейчас нас asm не пишу.
&quot писал(а):А вот самая быстрая команда все таки NOP
Трудно поспорить, я про NOP забыл даже :)
&quot писал(а):старый добрый bitfuck или хотябы преобразование RGB555 -> RGB888 и обратно
Сейчас ты человека совсем запугаешь, он к нас не придёт больше :)
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Ответить