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

[IMpulSE_18]

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

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

[Romeo]

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

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

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

[somewhere]

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

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

[Romeo]

Разумеется целесообразно если размер параметра - 1 байт.

По условию задачи параметр типа unsigned short, то есть 2 байта.

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

У меня тоже была идея написать на асм, но дело в том, что задача алгоритмическая и было оговорено преподавателем, что должен использоваться сдвиг, потому я написал на С++.

... а сдвиги - они вообще относительно медленные операции

Позволю себе не согласиться: Правый и левый сдвиг (shr, shl) на один бит - это 2 два процессорных такта, точно также как и add и sub, or, and (в случае, когда оба операнда размещены в регистрах). На самом деле более быстрой операции, чем сдвиг на один бит просто нет.

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

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

2. Код or ax, ax. Ничего страшного, просто выглядит путанно. Для установки флагов есть замечательная самодокументирующая себя своим именем команда test, которая делает то же самое что и or, только не меняет регистров. Почему не использовать её, ведь код тогда становится более читабельным? (я не спорю or тоже работает, я сейчас говорю о прозрачности кода)

[somewhere]

Команды 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

Код or ax, ax. Ничего страшного, просто выглядит путанно

Это старая привычка, со времен когда еще не было инструкции test И все таки считаю, что данная задача является плохим уроком по работе со сдвиговыми операциями, уж лучше старый добрый bitfuck или хотябы преобразование RGB555 -> RGB888 и обратно

[Romeo]

Команды 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 такта. Но даже тогда, сдвиг работал два такта (при условии, что сдвиг на делается на один бит и количество бит, то есть единичка, занесены в регистр). Почему на современных процессорах это время увеличилось, интересно?

быстрее чем loop. Ну и еще довольно много прочих хитростей.

Ага, это известный факт. Ещё есть очень правильная рекомендация всячески уходить от джампов, например используя сложение с переполнением и вычитание с заёмом (adc, sbb) - при хитро продуманном алгоритме это позволяет в некотрых случаях красиво переделать конструкцию if, в состав которой входит джамп. Вообще там много нюансов есть, к сожалению не все уже помню, так как сейчас нас asm не пишу.

А вот самая быстрая команда все таки NOP

Трудно поспорить, я про NOP забыл даже

старый добрый bitfuck или хотябы преобразование RGB555 -> RGB888 и обратно

Сейчас ты человека совсем запугаешь, он к нас не придёт больше