"Вам "шашечки" или ехать?" Пойми -- быстро - длинный код (стараются развернуть циклы, убрать лишние проверки), короткий код - наглядно, не самое быстрое исполнение Понимаю, что дальше длинный код, который так не любит ТС, но преимущества - принимаю решение о том, есть ли единичные биты сразу среди 16 или 8 битов и остальные прелести параллельной обработки Код (Text): test eax,eax jz quit; "облом" test ax,ax; проверяем 1 и 2 байт jz a3 test al,al jz a1; проверили сразу 8 бит - ничего нет - идем далее a2: mov ch,al mov cl,al neg cl and al,cl; выделили крайний справа единичный бит --- табличное преобразование номера бита --- тут делаешь свои темные делишки --- mov al,ch not cl; cl=al-1 and al,cl; обнулили крайний справа единичный бит jnz a2 a1: test ah,ah jz a3; проверили сразу 8 бит - ничего нет - идем далее a4: mov ch,ah mov cl,ah neg cl and ah,cl; выделили крайний справа единичный бит --- табличное преобразование номера бита --- добавляем к номеру бита 8 --- тут делаешь свои темные делишки --- mov ah,ch not cl; cl=ah-1 and ah,cl; обнулили крайний справа единичный бит jnz a4 a3: bswap eax; проверяем 3-ий и 4-ый байты test ax,ax jz quit test ah,ah; проверяем 3-ий байт jz a5; проверили сразу 8 бит - ничего нет - идем далее a6: mov ch,ah mov cl,ah neg cl and ah,cl; выделили крайний справа единичный бит --- табличное преобразование номера бита --- добавляем к номеру бита 16 --- тут делаешь свои темные делишки --- mov ah,ch not cl; cl=ah-1 and ah,cl; обнулили крайний справа единичный бит jnz a6 test al,al jz quit a5: mov ch,al mov cl,al neg cl and al,cl; выделили крайний справа единичный бит --- табличное преобразование номера бита --- добавляем к номеру бита 24 --- тут делаешь свои темные делишки --- mov al,ch not cl; cl=al-1 and al,cl; обнулили крайний справа единичный бит jnz a5 quit: ЗЫ. А вообще, метод предложеный crypto, наверное, еще быстрее...
Mikl__ Тогда уж и я внесу свою ИМХО-лепту: Создаешь таблицу из 256*9 записей длины 9, в которой для каждого байта B будет храниться запись вида N,I1,...,IN, где N - количество единичных битов в байте, I1,...,IN - номера позиций этих битов. За одно обращение ты получаешь для данного байта B адрес соответствующей ему записи, в цикле получаешь все позиции (цикл будет оптимальным, поскольку лишнего в нем ничего не будет). Для следующего байта делаешь то же самое, только к номерам позиций добавляешь 8 и т.д. Сравниваешь предварительно байт с 0.
Mikl__ Я подумал, что решение весьма громоздко, поскольку не знаю контекста (что за "темные делишки"). Потому и удалил, а ты прочитать успел
crypto А как насчет этого - идея сырая, но смысл как у кода Хемминга Код (Text): test eax,eax jz exit; бит равных 1 нет совсем test eax,55555555h setz bl; единичные биты нечетные test eax,33333333h setz bh test eax,0F0F0F0Fh setz cl; test eax,0000FFFFh setz ch --- анализ bl, bh, cl, cd и вывод номера каких битов=1
Размер таблицы можно значительно сократить, если учесть, что все 8 бит установлены только в одном числе (-1), которое можно проверить явно. и на номера бит можно отвести по 3 бита (на число бит тоже 3 бита). 3*(7+1)=24 = 3 байта на каждую запись
Great Спасибо за оптимизацию, только это приведет к дополнительным вычислениям: Кол-во данных*Кол-во кода >= CONST (Неопределенность Гейзенберга для программирования).
реализация зависит от "выходного формата", можно использовать и bt, если дополнить подпрограмму "сканирование бит" ещё каким-нибудь кодом. P.S. ещё зависит от объёма данных (а вдруг не eax
А чего тестить? Оставлю bsf. Гребенка хороша для каких-нить олимпиадных задач и когда запрещено пользоваться bsf. А байтовый вариант требует 256 ветвтлений, что я тоже кодить не буду.. А вот как улучшить bsf предложений не было...
persicum Отставляй Только учти, что bsf\bsr - сложные инструкции и их латентность сильно варьируется на разных процах (2 тика в Core-2, 8 в AMD и P4, и аж 16 в P4E). btc побыстрее, но тоже не "сахар" (1-2-9 тиков соотв-но). Можешь сам прикинуть на каком проце при скольки ед.битах связка bsf+btc будут выигрывать или проигрывать простому циклу с shr PS: неизвестно, что там у тебя скрывается под "темными делишками" с найденным битом - может тут и оптимизировать то незачем...
да ничего особо "криминального" - просто написал очередную прогу для раздувания объемов информации. Валяется на ник фронт ру. Учитывая, что цены на носители стремительно падают, не такое уж и большое зло... Объем работы, зависящий от найденного бита, зависит от наличия SSE2. Если оно есть, то тогда я разумеется стараюсь загрузить все xmm регистры по максимуму и с ними хорошенько поработать, а если нет, ну тогда пара асмовских комманд - тут действительно поиск бита может быть time consuming. Но мне не жалко тех товарищей, у которых нетути sse2...
В догонку, определение номера выделенного бита в eax, при этом не используем bs Код (Text): xor ebx,ebx test eax,eax jz quit test eax,10101010101010101010101010101010b setnz bh shr ebx,1 test eax,11001100110011001100110011001100b setnz bh shr ebx,1 test eax,11110000111100001111000011110000b setnz bh shr ebx,1 test eax,11111111000000001111111100000000b setnz bh shr ebx,1 test eax,11111111111111110000000000000000b setnz bh shr ebx,4; в ebx номер бита
Опять у тебя все не полюдски, на этот раз нужно перевернуть этот код с головы на ноги. Начинать вместо test eax,eax с test eax,FFFFFFFFh, что одно и тоже, но эстетика и математическая полнота требуют. Потом двигать влево, потом тестить FFFF0000, FF00FF00, F0F0F0F0 и т.д. Но и ты учти, что наивысшая энтропия достигается при равновероятном числе нулей и единиц, стало быть латентность test,jz,shr нужно удвоить, ибо эта связка будет в половине случаев работать в холостую.А bsf не работает в холостую, на нулях не вспотыкается.
persicum Мог бы мне и не отвечать, но на самом деле приятно, что "изобрел коды Рида-мюллера =)))" хотя в #25 я писал "смысл как у кода Хемминга" - какие-то ассоциации с корректирующими кодами в голове крутились Где было "не по-людски" в первый раз? "Начинать вместо test eax,eax " - если нет взведенного бита - то и проверять нечего - quit, а уж как обнаружить в eax ноль - через and, or, add - дело вкуса. "Потом двигать влево" - установить бит в bh, затем сдвинуть влево, чтобы следующая инструкция setnz bh сбросила все результаты в ноль/единицу? - а вот при сдвиге ebx вправо все результаты накапливаются в bl. Далее persicum пишет, вероятно, для leo, хотя Цитата из leo в #31, а вот моя в #6
Мдя, со сдвигом влево код длиннее получается =((( Зато все по правильному, по кашерному =))) Код (Text): xor ebx,ebx test eax,$FFFFFFFF jz @nobit test eax,$FFFF0000 setnz bl or bh,bl shl ebx,1 test eax,$FF00FF00 setnz bl or bh,bl shl ebx,1 test eax,$F0F0F0F0 setnz bl or bh,bl shl ebx,1 test eax,$CCCCCCCC setnz bl or bh,bl shl ebx,1 test eax,$AAAAAAAA setnz bl or bh,bl shr ebx,8 //----в ebx - номер бита @nobit:
Придумал!!! Заместа трех коммандочек Код (Text): setnz bl or bh,bl shl ebx,1 можно использовать две их штук: Код (Text): setnz cl lea ebx,[ecx+ebx*2] Так што паритет, хотя твой вариант с bh опять-таки был довольно изобретательным...
persicum Код (Text): ;Выделение самого правого единичного бита (число в eax, результат в ecx) mov ecx,eax neg ecx and ecx,eax ... xor eax,ecx; удаляем самый правый единичный бит
Наверное, слова насчет "правильности" ты сочел просто за стеб, но по мне этож ведь схема Горнера, а в ней логичнее стартовать с коффициентов наивысших степеней и умножать, а не делить. На счет NEG - без поллитра не сообразить, ща запущу отладчик и посмотрю, что там с битами делается... На первый взгляд напоминает Брезенхема - непонятно как, но работает.=)))
