Задачка::Проверка бита

← →
Rouse_ © (2014-10-14 20:14) [40]

Есть еще один вариант не методом Гаусса решается, но в принципе - задача решена :)

← →
MBo © (2014-10-14 20:17) [41]

> Юрий Зотов © (14.10.14 20:04) [35]
> А логарифм как, по скорости?

Не быстрый, но и не катастрофа

Result := Round(Log2(DWord(Value)));

DeBruijn 1516 BSR 1437 BinSearch 1344 SHR 6734 Log2 7079

← →
Inovet © (2014-10-14 20:18) [42]

> [38] Kerk © (14.10.14 20:11)

Ну да всегда же делится на 2.

← →
Ega23 © (2014-10-14 20:42) [43]

> Угу, оно... забыл что вы тут все умные, каюсь. Задачка -так себе :)

Тащемта, я подумал что ты как-то хитро стебёшься например.

← →
jack128 © (2014-10-14 21:17) [44]

> function GetIndexBsr(Value: DWORD): Byte; assembler;
> asm
> bsr eax, eax
> end;

тут из-за того, что дельфи вставляет пролог/эпилог - результат медленее, чем мог бы быть.

← →
Dimka Maslov © (2014-10-14 21:36) [45]

> Интринсики же есть _BitScanReverse64

А если я хочу несколько команд? А если надо оптимизировать? А ведь может от этого в Win7 "Оценка продолжительности копирования файлов" в три раза дольше, чем само копирование?

← →
NoUser © (2014-10-14 21:39) [46]

XE2 простое консольное приложение 64 бита ;)

function GetIndexBsr64(Value: NativeUInt): NativeUInt; asm .NOFRAME bsr rcx, rcx mov rax, rcx end;

← →
Rouse_ © (2014-10-14 21:44) [47]

> jack128 © (14.10.14 21:17) [44]
> тут из-за того, что дельфи вставляет пролог/эпилог - результат
> медленее, чем мог бы быть.

Жек, ты конечно молоток, что асм начал изучать, но не говори глупостей плз :)

← →
Rouse_ © (2014-10-14 21:54) [48]

> NoUser © (14.10.14 21:39) [46]

Повбивав бы :)
bsr rax, rcx

← →
MBo © (2014-10-14 22:01) [49]

> А если я хочу несколько команд? А если надо оптимизировать?

А что этому противоречит? Компилятор VS развернет интринсик в эффективный для целевой платформы код, возможно, в тот же BSR

← →
NoUser © (2014-10-14 22:22) [50]

> Rouse_ © (14.10.14 21:54) [48]
Та це я так тоненько над
mov eax, N
посміявся ))

← →
Sha © (2014-10-14 22:48) [51]

> MBo ©

немного изменил )

function BitIndexBinS2(Value: Integer): Integer; var a: byte; begin a:=byte((Value and $FFFF0000)<>0); //бит в старшем слове +16 a:=byte((Value and $FF00FF00)<>0) + a + a; //бит в старшем байте одного из слов +8 a:=byte((Value and $F0F0F0F0)<>0) + a + a; //бит в старшем ниббле одного из байтов +4 a:=byte((Value and $CCCCCCCC)<>0) + a + a; //бит в одном из старших битов ниббла +2 a:=byte((Value and $AAAAAAAA)<>0) + a + a; //бит на нечетном месте +1 Result:=a; end;

результат на E-6850:

BSR 312
DeBruijn 328
BinSearch 748
BinSearch2 390
SHR 1779

← →
jack128 © (2014-10-14 23:23) [52]

> Жек, ты конечно молоток, что асм начал изучать, но не говори
> глупостей плз :)

а дело не в асме, а в дельфе. Я действительно тут неправильно понял логику компилятора, когда он вставляет, а когда нет пролог в асм код.

← →
Dimka Maslov © (2014-10-14 23:24) [53]

> XE2 простое консольное приложение 64 бита ;)

У меня Visual C++ же

> А что этому противоречит?

Правилу не изобретать лишних сущностей. Ведь кроме BSR существует достаточное количество других инструкций, при последовательном вызове которых вместо простого и понятного кода получится каша из кучи вызовов. Ну а кроме того, нет ничего сложного в портировании команд ассемблера, а не вызовов функций. В добавок, у меня одна платформа и я не собираюсь переносить свой проект на другую. Так что, на мой взгляд, замена прямого ассемблера кривым - очередной шаг в неправильную сторону.

← →
Dimka Maslov © (2014-10-14 23:35) [54]

Ну а кроме того, компилятор, который на функцию
long long Inc(long long& N) { return ++N; }

генерирует код
mov qword ptr [rsp+8],rcx push rdi mov rax,qword ptr [N] mov rax,qword ptr [rax] inc rax mov rcx,qword ptr [N] mov qword ptr [rcx],rax mov rax,qword ptr [N] mov rax,qword ptr [rax] pop rdi ret

вместо казалось бы
mov rax, qword ptr [ecx] inc rax mov qword ptr [ecx], eax ret

На мой взгляд далёк от оптимального

← →
Rouse_ © (2014-10-14 23:48) [55]

Конечно далек, ибо оптимальный это: lea rcx, [rcx + 1] :)

← →
Dimka Maslov © (2014-10-14 23:57) [56]

А вот и нет:

function _Inc(var N: Integer): Integer; asm lea eax, [eax+1] end;
выдаёт полную чушь
N как был, так и остаётся, а возвращается его адрес, вместо значения

← →
Rouse_ © (2014-10-15 00:01) [57]

Да, ошибся, реф не увидел...

← →
jack128 © (2014-10-15 00:08) [58]

> Ну а кроме того, компилятор, который на функцию

Это в релизе ?? У мя на 2013 в релизе такой код генерится

int _tmain(int argc, _TCHAR* argv[]) { __debugbreak(); long long n; std::cin >> n; Inc(n); // !!!!!!!!!!!!!!!!!!!!!!!!!!!! твоя функция std::cout << n; return 0; }

int _tmain(int argc, _TCHAR* argv[]) { 000000013FF31270 sub rsp,38h 000000013FF31274 mov rax,qword ptr [__security_cookie (013FF35000h)] 000000013FF3127B xor rax,rsp 000000013FF3127E mov qword ptr [rsp+28h],rax __debugbreak(); 000000013FF31283 int 3 long long n; std::cin >> n; 000000013FF31284 mov rcx,qword ptr [__imp_std::cin (013FF33078h)] 000000013FF3128B lea rdx,[n] 000000013FF31290 call qword ptr [__imp_std::basic_istream<char,std::char_traits<char> >::operator>> (013FF33050h)] Inc(n); 000000013FF31296 mov rdx,qword ptr [n] /// !!!!!!!!!!!!!!!!!!!!!!!!!!!! грузим из памяти в регистр std::cout << n; 000000013FF3129B mov rcx,qword ptr [__imp_std::cout (013FF33070h)] Inc(n); 000000013FF312A2 inc rdx /// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! увеличиваем на единичку 000000013FF312A5 mov qword ptr [n],rdx // пишем обратно в память std::cout << n; 000000013FF312AA call qword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (013FF33048h)] return 0; 000000013FF312B0 xor eax,eax }

> У меня Visual C++ же
Ну так dll"кой на крайняк ), а то просто слинковать с внешним *.obj, или это тоже в V$2013 запретили?

>Sha © (14.10.14 22:48) [51]
Сильно зависит от процессора и режима сборки.
В дебаг-режиме твой код приводит после test к setnz вместо условного перехода jz, но на моей машине это оказывается хуже исходного варианта. А в релизе - не знаю, что получается, но лучше ;)

i5-4670 XE3 Debug BSR 343 DeBruijn 390 BinSearch 546 BinSearch2 827 SHR 3229 Log2 3603 Release BSR 203 DeBruijn 187 BinSearch 374 BinSearch2 312 SHR 812 Log2 3354

MBo © (15.10.14 09:24) [60]

у меня D7 не вставляет ничего лишнего, работает прямо с байтами, использует только операции setnz и add

> работает прямо с байтами, использует только операции setnz и add
Да, так и есть (в debug, в release я не знаю, как проконтролировать)

Search2
Unit1.pas.76: a:=byte((Value and $FF00FF00)<>0) + a + a; //бит в старшем байте одного из слов +8 005AE6DE F745FC00FF00FF test [ebp-$04],$ff00ff00 005AE6E5 0F95C0 setnz al 005AE6E8 0245F7 add al,[ebp-$09] 005AE6EB 0045F7 add [ebp-$09],al

Search
Unit1.pas.65: if (Value and $FF00FF00)<>0 then result:=result+8; // бит в старшем байте одного из слов 005AE68B F745FC00FF00FF test [ebp-$04],$ff00ff00 005AE692 7404 jz $005ae698 005AE694 8345F808 add dword ptr [ebp-$08],$08

Ужас эти новые версии.
В D7 все действия только с регистрами.

Если нет доступа к встроенному ассеблеру, то первое, что приходит в голову, це

const int magic[64] = { 0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4, 62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5, 63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11, 46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6 }; return magic[(0x03f79d71b4cb0a89ull * value) >> 58];

Вот с логарифмом версия

{ union { double d; struct { unsigned int mantissal : 32; unsigned int mantissah : 20; unsigned int exponent : 11; unsigned int sign : 1; }; } ud; ud.d = (double)(bb); return ud.exponent - 1023; }

Еще вариантьі тут
https://chessprogramming.wikispaces.com/BitScan

> jack128 © (15.10.14 00:08) [58]

В релизе. И вообще пример не показательный. И вообще когда дельфийский отладчик заходит в сишный код, становится страшно от того, что там понапихано, а главное зачем. Я вот свой старый проект, который до сих пор жил в 2005 студии собрал в 2013. Мало того, он стал в 1.5 раза больше, так ещё и заметно медленнее на больших задачах.

> NoUser © (15.10.14 00:13) [59]

На самый крайняк можно вспомнить TurboPascal3.0 в которым не было ассемблера, но можно было напрямую в кодах писать.

Задачка::Проверка бита Найти похожие ветки