Задачка 2^n => n (без BSF/BSR, переходов и таблиц)

В регистре разрядностью N(можно решать задачу для некоторого конкретного N) имеется число вида 2^n (с одним единичным разрядом). Нужно построить функцию, которая(без BSF/BSR, переходов и таблиц) вычислит номер единичного бита. Или хотя бы взаимооднозначно отобразит множество чисел вида 2^n во множество чисел 0 .. (N-1). В последнем случае нужно построить и обратную функцию.
Например, пусть для N=8, нам удалось построить такую функцию:

Код (Text):

1. 00000001 -> 000   0
2. 00000010 -> 001   1
3. 00000100 -> 010   2
4. 00001000 -> 101   3
5. 00010000 -> 011   4
6. 00100000 -> 111   5
7. 01000000 -> 110   6
8. 10000000 -> 100   7

Теперь нужно либо построить функцию которая из второго столбца получит первый, либо получит из него третий столбец(тогда построение обратной функции будет уже тривиальным).

 

На ум лезет подсчет кол-ва единиц в числе x-1 через умножения на магик-намберы...
Хотя для небольших N, это м.б. и не лучший способ

 

Для одной тетрады можно по битовой табличке MagicNumber сделать:
x4 = (MagicNumber >> y4*3) & 7; //MagicNumber = 0x3002044

 

//del
(пересмотрел алгоритм Копперсмита и понял, что он содержит в себе циклы)

 

DEEP
Смешно. Хотел придумать ещё больший overkill для наглядности, но Ваш вариант переплюнуть не смог. В пределах двадцати байт и двадцати тактов x86 этот алгоритм реализуете? Потому что первая половина задания реализуется где-то в таких пределах, если не меньше.

 

l_inc
Ну вообще-то я говорил серьёзно, подумав о на самом деле произвольном N.
А теперь вот всю ночь не усну — буду думать, как вообще возможно аппроксимировать логарифм с приемлемой экстраполяцией (т.к. ТС явно указывает на неограниченность N) на фиксированных двадцати тактах ЦП, без циклов.

 

DEEP
Ваш вариант в любом случае — перебор. Кроме того:

Но могу уточнить вопрос: "В пределах двадцати байт и двадцати тактов x86 для N=32 этот алгоритм реализуете?"
Рассчитываете, что теперь уснёте раньше?

 

А почему без BSF/BSR, переходов и таблиц?

Код (Text):

1. cnt_shl=1
2. mov edx,-1 ; -1 останется если в eax не 2^n
3. xor ecx,ecx
4. N=32
5. REPEAT N
6.     cmp eax,cnt_shl
7.     cnt_shl=cnt_shl shl 1
8.     cmovz edx,ecx
9.     inc ecx
10. ENDM

 

l_inc
Ладно, тогда ещё одна идея на сон грядущий, уже из области дискры, а не матана.

Рассмотрим биты регистра. Модифицируем таблицу из поста [1], и обозначим её за T:

Код (Text):

1. 00000001 -> 000
2. 00000010 -> 001
3. 00000100 -> 010
4. 00001000 -> 011
5. 00010000 -> 100
6. 00100000 -> 101
7. 01000000 -> 110
8. 10000000 -> 111

Составим новую таблицу T` в log2(N) строк, где справа в i-й строке будет взведён i-й бит, а слева будет битовая маска, составленная OR`ом из всех левых частей таблицы T, для которых в правой части T этот бит взведён.
Так, для T из поста [0], имеем T`:

Код (Text):

1. 10101010 -> 001
2. 11001100 -> 010
3. 11110000 -> 100

В итоге, мы можем построить функцию из [1] за логарифмическое время.


Так, для N=8, задача решается за 8 тактов:

Код (Text):

1. TEST AL, 11110000b;
2. SETNE CL;
3. TEST AL, 11001100b;
4. SETNE BL;
5. TEST AL, 10101010b;
6. SETNE AL;
7. LEA EAX, [EAX + ECX*4];
8. LEA EAX, [EAX + EBX*2];

[UPD #1:]
Ах да, на всякий случай поясню принцип действия.
Всё что мы делаем — это набираем номер искомого бита поразрядно.
Если

то это значит, что в номере взведён i-тый разряд.

[UPD #2:]
Код для N=32 (вход — EAX, выход — ECX):

Код (Text):

1. XOR EDX, EDX;
2.  
3. TEST EAX, 11111111111111110000000000000000b;
4. SETNE DL;
5. MOV ECX, EDX;
6.  
7. TEST EAX, 11111111000000001111111100000000b;
8. SETNE DL;
9. LEA ECX, [ECX*2 + EDX];
10.  
11. TEST EAX, 11110000111100001111000011110000b;
12. SETNE DL;
13. LEA ECX, [ECX*2 + EDX];
14.  
15. TEST EAX, 11001100110011001100110011001100b;
16. SETNE DL;
17. LEA ECX, [ECX*2 + EDX];
18.  
19. TEST EAX, 10101010101010101010101010101010b;
20. SETNE DL;
21. LEA ECX, [ECX*2 + EDX];

Итого — 16 тактов.

 

DEEP
Это всё уже было. Самый быстрый вариант такой. С табличкой в n байт. Теперь табличка почему-то не допускается, но без неё среднюю колонку ни в правую не перевести ни в левую (из таблицы первого поста).

 

l_inc
Ну вот, опять не ко двору.

Злые вы, уйду я от вас =)

 

l_inc

Но "квазитаблицу" <= 32 бит, наверное неразумно запрещать, т.к. она по сути не отличается от прочих "выкрутасов" с magic number'ами

 

leo
Думаю, что "квазитаблицу" и не запрещали. Но, наверное, решение должно всё-таки как-то масштабироваться хотя бы на 32, а может и на 64 бита. Не выльются ли выкрутасы с квазитаблицей в выкрутасы с таблицей без значительных накладных?
DEEP

Да ладно. Обещаю не критиковать дальнейшие предложения.

 

Что касается получения из первого столбца второго(где числа уникальны, но не упорядочены), то там требуется всего две команды. А вот пример побитового восстановления первого столбца из второго(для 32 разрядов можно поступить аналогично, только магических чисел понадобится 5 и добавится еще 10 команд):

Код (Text):

1. 10000000 <- 100  
2. 01000000 <- 110  
3. 00100000 <- 111  
4. 00010000 <- 011  
5. 00001000 <- 101  
6. 00000100 <- 010  
7. 00000010 <- 001  
8. 00000001 <- 000
9.  
10. eax - число от 0 до 7 из второго столбца
11.  
12. mov edx, not 11101000b
13. mov ecx, not 01110100b
14. mov ebx, not 00111010b
15.  
16. shr eax,1
17. sbb esi,esi
18. xor ebx,esi
19.  
20. shr eax,1
21. sbb esi,esi
22. xor ecx,esi
23.  
24. neg eax
25. xor eax,edx
26.  
27. and eax,ebx
28. and eax,ecx

 

Код (Text):

1. ; Ktobyvydumali?
2. magic_rabbit dq 4340000000000000h, 4340000000000000h
3.  
4. movd xmm0, eax
5. orpd xmm0, [magic_rabbit]
6. subsd xmm0, [magic_rabbit]
7. pextrw eax, xmm0, 3
8. shr eax, 4
9. sub eax, 400h

 

l_inc

Не выльются, т.к. идея с квазитаблицей заключается не в том, чтобы применять ее к каждой тетраде, а в том, чтобы свести задачку к поиску нужной тетрады - а эта задачка элементарно решается методом умножения. Например, для 32 бит:

Код (Text):

1. ;eax - вх.число
2. lea ecx,[eax*2-1] ;преобразуем 0100..0 в 0111..1
3. and ecx,11111111h ;выдяляем младшие биты каждой тетрады
4. imul ecx,11111111h ;суммируем эти биты
5. shr ecx,28         ;получаем кол-во тетрад, включая искомую
6. lea ecx,[ecx*4-4]  ;число бит до тетрады с установленным битом
7.  
8. mov edx,ecx
9. shr eax,ecx         ;выделяем тетраду
10. lea ecx,[eax+eax*2] ;индекс таблицы
11. mov eax,0x3002044   ;таблица
12. shr eax,ecx
13. and eax,7           ;номер бита в тераде
14. add eax,edx         ;номер бита в дворде

 

leo
Ну что сказать. Это... круто.

 

leo
Можно несколько улучшить, если вычислять номер бита в байте:

Код (Text):

1. imul ecx,eax,17171717h
2. shr ecx,29; 2^n -> 0 1 2 5 3 7 6 4  0 1 2 5 3 7 6 4  0 1 2 5 3 7 6 4  0 1 2 5 3 7 6 4
3. lea ecx, [101 110 011 111 100 010 001 000 0001000b + ecx*3];таблица перестановки + вычисление сдвига
4. shr ecx,cl
5. and ecx,7;теперь числа в правильном порядке
6.  
7. lea eax,[eax*2-1]
8. and eax,01010101h
9. imul eax,01010101h
10. shr eax,24
11. lea eax,[eax*8-8+ecx]

Небольшая оптимизация второй части:

Код (Text):

1. shr eax,cl
2. imul eax,00081018h
3. shr eax,24
4. add eax,ecx

 

Black_mirror
Первая идея с использованием imul для независимого вычисления смещения внутри байта\тетрады - это круто, но "оптимизация второй части" опять вносит зависимость и тем самым снижает ценность первой. Поэтому лучше обе части оставить независимыми и вернуться к тетрадам, т.к. это позволит еще больше упростить первую часть и вообще отказаться от таблицы:

Код (Text):

1. ;eax - вх.число, не равное 0
2. lea ecx,[eax*2-1]  ;преобразуем 0100..0 в 0111..1
3. imul eax,11111111h ;загоняем искомую тетраду вверх в 28-31 биты
4. and ecx,11111111h  ;выдяляем младшие биты каждой тетрады
5. imul ecx,11111111h ;суммируем эти биты
6. cdq                ;edx=-1 для тетрады 1000b, иначе =0
7. shr eax,29         ;= 0,1,2,4
8. shr ecx,28         ;кол-во тетрад, включая искомую
9. add eax,edx        ;= 0,1,2,3
10. lea eax,[eax+ecx*4-4] ;искомый номер бита

В итоге обе части должны выполняться паралельно и общее время будет определяться задержкой вычисления номера тетрады

 

del