Очень, очень интересно!!! В какой книженции ты все это вычитал? Достойная замена может быть для btc. А вот логарифмировать регистр ecx предполагается с помощью все той же команды bsf =))) Шутка... Блин, а нельзя вот так вот быстро и чтобы был сразу нужный номер бита? Хотя да, для единичных бит действительно можно построить байтовую таблицу логарифмов. Но лазать в нее придется в худшем случае целых 4 раза, тут не грех вспомнить и о гребенке. А если без таблицы? Мож сопр поможет? Сопр должен мгновенно двоичный лог брать. Или вот, можно через сопр преобразовать целое в single и посмотреть у него экспоненту.
persicum Рекомендую, Генри Уорен "Алгоритмические трюки для программистов" (Henry Warren "Hacker's Delight")
persicum Если ты про сопроцессор, то забудь. Недавно разбирался с потерей точности в Фортран-проге. Залез в библиотеку Интела и обнаружил, что они уже с 7-й версии считают логарифм и синусы через SSE. Так быстрее. А главное точнее. У сопра в LN(2) последний бит неверный :-(
valterg Дробный логарифм здесь не нужен. А целый - это двоичная экспонента числа, получается ес-но точно (при fild), но ес-но не быстрее, а дольше bsf\bsr, т.к. число нужно загрузить, выгрузить, загрузить эксп-ту и вычесть смещение (про fxtract и говорить нечего - это вообще тормоз)
persicum При последовательном получении номеров бит также можно учесть, что если сейчас был бит с номером 15, то у следующих битов 5-ый бит равен 1 и т.д.
В продолжение темы: Код (Text): ... unsigned char a, b, c, d; unsigned long f; // abcdabcdabcdabcdabcdabcdabcdabcd binary ... a = 0;b = 0;c = 0;d = 0; if (f & 0x80000000) a |= 0x80; if (f & 0x8000000) a |= 0x40; if (f & 0x800000) a |= 0x20; if (f & 0x80000) a |= 0x10; if (f & 0x8000) a |= 0x08; if (f & 0x800) a |= 0x04; if (f & 0x80) a |= 0x02; if (f & 0x8) a |= 0x01; if (f & 0x40000000) b |= 0x80; if (f & 0x4000000) b |= 0x40; if (f & 0x400000) b |= 0x20; if (f & 0x40000) b |= 0x10; if (f & 0x4000) b |= 0x08; if (f & 0x400) b |= 0x04; if (f & 0x40) b |= 0x02; if (f & 0x4) b |= 0x01; if (f & 0x20000000) c |= 0x80; if (f & 0x2000000) c |= 0x40; if (f & 0x200000) c |= 0x20; if (f & 0x20000) c |= 0x10; if (f & 0x2000) c |= 0x08; if (f & 0x200) c |= 0x04; if (f & 0x20) c |= 0x02; if (f & 0x2) c |= 0x01; if (f & 0x10000000) d |= 0x80; if (f & 0x1000000) d |= 0x40; if (f & 0x100000) d |= 0x20; if (f & 0x10000) d |= 0x10; if (f & 0x1000) d |= 0x08; if (f & 0x100) d |= 0x04; if (f & 0x10) d |= 0x02; if (f & 0x1) d |= 0x01; A такой расчёт можно оптимизировать по скорости? Видятся два варианта расчёта: 1-й: "сдвинутый" Код (Text): eax = f bh = a bl = b ch = c cl = d ; #1 rcl eax,1 rcl bh,1 rcl eax,1 rcl bl,1 rcl eax,1 rcl ch,1 rcl eax,1 rcl cl,1 ; #2 rcl eax,1 rcl bh,1 rcl eax,1 rcl bl,1 rcl eax,1 rcl ch,1 rcl eax,1 rcl cl,1 ... ; #8 rcl eax,1 rcl bh,1 rcl eax,1 rcl bl,1 rcl eax,1 rcl ch,1 rcl eax,1 rcl cl,1 2-й: "тестовый" Код (Text): eax = f bh = a bl = b ch = c cl = d test eax,0x80000000 jz @@: Or Bh,0x80 @@: test eax,0x8000000 jz @@: Or Bh,0x40 @@: ... test eax,0x10 jz @@: Or Cl,0x2 @@: test eax,0x1 jz @@: Or Cl,0x1 @@: Есть ли ещё варианты с учетом того что обрабатывается большой поток данных ? Имеет ли смысл "отлавливать" нулевые значения и пропускать дальнейшие проверки eax?
Это классическая задачка на сборку\раздвижку бит с использованием умножения на константу. Умножение f*magic это по сути сумма из N сдвинутых чисел f, где N и сдвиги определяются кол-вом и позициями единичных бит константы magic. Пример Код (Text): mov eax,[f] and eax,88888888h ;выделяем нужные биты imul eax,2481h ;умножаем на magic = 1001001001b, чтобы биты собрались в группы по 4 and eax,0F000F000h ;выделяем 2 нужные группы mov edx,eax ;сдвигаем и объединяем shr eax,12 shr edx,24 or edx,eax mov [a],edx Для b,c,d аналогично - только меняются константы в and и shr. Для лучшего распараллеливания можно одновременно (вперемежку) выполнять выделение пар чисел a,b и затем c,d или даже все 4 сразу
Mikl__ Аналогичного добра много и в онлайне: http://www.jjj.de/bitwizardry/bitwizardrypage.html http://aggregate.org/MAGIC/ http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
Интересно когда нить появится команды асма для подсчёта количества бит, есть ряд алгоритмов котором эта команда сильна помогла.
Кто подскажет какая самая быстрый код для подсчёта кол. бит, можно х86 в плоть до SSE но не выше. X:=i; dec(x,(x shr 1) AND $5555555555555555); x:= (x AND $3333333333333333) + ((x shr 2) AND $3333333333333333); x:= (x + (x shr 4)) AND $0f0f0f0f0f0f0f0f; inc(x,x shr 8); inc(x,x shr 16); inc(x,x shr 32); x:=x and $FF; // 50 takt athlon XP 2200 } x:= (x AND $55555555) + ((x AND $AAAAAAAA) shr 1); x:= (x AND $33333333) + ((x AND $CCCCCCCC) shr 2); x:= (x AND $0F0F0F0F) + ((x AND $F0F0F0F0) shr 4); x:= (x AND $00FF00FF) + ((x AND $FF00FF00) shr 8); x:= (x AND $0000FFFF) + ((x AND $FFFF0000) shr 16); это два варианта, нужен самый быстрый, можно асме но только что бы можно было в делфи вставить.
persicum А почему именно на 65536? А если L1 всего 32К, не лучше ли тогда использовать таблицу на 256 значений?
Из AMD Code Optimization Guide Код (Text): unsigned int popcount(unsigned int v) { unsigned int retVal; __asm { MOV EAX,[v] ;v MOV EDX,EAX ;v SHR EAX,1 ;v>>1 AND EAX,055555555h ;(v>>1)&0x55555555 SUB EDX,EAX ;w=v-((v>>1)&0x55555555) MOV EAX,EDX ;w SHR EDX,2 ;w>>2 AND EAX,033333333h ;w&0x33333333 AND EDX,033333333h ;(w>>2)&0x33333333 ADD EAX,ED ;x=(w&0x33333333)+((w>>2)&0x33333333) MOV EDX,EAX ;x SHR EAX,4 ;x>>4 ADD EAX,EDX ;x+(x>>4) AND EAX,00F0F0F0Fh ;y=(x+(x>>4)&0x0F0F0F0F) IMUL EAX,001010101h ;y*0x01010101 SHR EAX,24 ;result=(y*0x01010101)>>24 MOV retVal,EAX } return(retVal); }
На атлонах http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf страница 247
