Задачка об уникальных тетрадах

Тема в разделе "WASM.A&O", создана пользователем Black_mirror, 11 мар 2010.

  1. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Вовсе и нельзя. cmc != not
     
  2. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    А что, собственно, мешает анализировать t0^t1^...t7 - ксор всех тетрад? Если хотя бы пара одинакова, то должен быть нуль, иначе - нет, верно?
     
  3. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Из интеловского мана
     
  4. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    medstrax1
    Последние 3 команды вроде можно заменить на:
    Код (Text):
    1. DEC EAX
    2. CDQ
    3. XCHG EAX,EDX
    если не ошибаюсь, будет на 2 байта короче.
     
  5. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    PSR1257
    сперва надо подготовить все возможные комбинации, потом поксорить попарно, потом проэндить в кучу. я даж алгос написал, но ТС еще на первой странице сказал, что решением от persicum он удовлетворен (кстати, красивое решение). не пойму о чем спор уже 4ую страницу?
     
  6. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Я ерунду напейсал, глюк.
     
  7. Medstrax

    Medstrax Забанен

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    673
    Код Black_mirror с циклом можно чуть улучшить, если заменить
    NEG CL
    SBB EAX,EAX
    NOT EAX
    на
    cmp cl,1
    sbb eax,eax
     
  8. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Black_mirror
    Я тоже подумывал про CDQ+XCHG, но до DEC не догадался :dntknw:

    Получается на 1 байт короче
     
  9. Medstrax

    Medstrax Забанен

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    673
    Круто, респект
     
  10. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    medstrax1
    С POPCNT у меня пока только такое безобразие получается размером в 59 байт, на правильность не проверял:
    Код (Text):
    1.         or edx,-1
    2.         mov cl,4
    3.         btr dx,ax
    4. repeat 7
    5.         shl eax,cl
    6.         btr dx,ax
    7. end repeat
    8.         popcnt eax,edx
    9.         cmp al,25
    10.         sbb eax,eax
     
  11. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Или вот такое, размером в 57 байт, тоже не проверял:
    Код (Text):
    1.         or edx,-1
    2.         mov cl,4
    3.         btr edx,eax
    4. repeat 7
    5.         shl eax,cl
    6.         btr edx,eax
    7. end repeat
    8.         shrd eax,edx,16
    9.         and eax,edx
    10.         popcnt eax,eax
    11.         cmp al,9
    12.         sbb eax,eax
     
  12. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    murder
    neg eax + not eax = sub eax, 1
    neg eax + cmc != sub eax, 1
     
  13. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Блин, какие все тут крутые, бедный дельфоасмер persicum сгорает от стыда...
    Ну ни че, вот рекордное по простоте понимания решение без битовых операций,
    тока простая логика

    Код (Text):
    1.  mov ebx,eax //origin
    2.  mov cl,4
    3.  mov edi,0x11111111 //global sum
    4.  
    5.  ----repeat 7 times----
    6.  ror eax,cl
    7.  mov edx,eax
    8.  xor edx,ebx
    9.  mov esi,edx  //local sum
    10.  shr edx,1
    11.  or  esi,edx
    12.  shr edx,1
    13.  or  esi,edx
    14.  shr edx,1
    15.  or  esi,edx
    16.  and edi,esi
    17. -----end repeat-----
    18.  
    19.  mov eax,edi
    20.  xor eax,0x11111111
    21.  neg eax
    22.  sbb eax,eax
     
  14. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    KeSqueer
    Там нужен только флаг cf поэтому можно использовать либо cmp eax,1 либо sub eax,1. Размер одинаковый, но на 1 инструкцию меньше.

    логика такая
    Код (Text):
    1. if eax=0 then
    2.   cf=1
    3. else
    4.   cf=0
     
  15. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Об этом же medstrax1 писал(а) в 87 посте.
     
  16. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    murder
    OK, убедили.
     
  17. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    хехе, вариант с вращением регистра меня тоже заинтересовал и я привел простое, без наворотов и крутизны, решение
     
  18. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    persicum
    В твоём решении кода наворочено в 2 раза более чем нужно. Во первых повторять 7 раз нету никакого смысла, достаточно всего 4. Во вторых флаг можно хранить в старшем разряде тетрады, тогда локальные суммы можно подсчитывать так:
    Код (Text):
    1. lea esi,[edx*3]
    2. or esi,edx
    3. lea edx,[esi*5]
    4. or esi,edx
    В общем код требуется хорошо почистить.
     
  19. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    нагло вру, должно быть edx*2 и esi*4
     
  20. Medstrax

    Medstrax Забанен

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    673
    Здесь вроде вместо shl - shr нужен. Как и предыдущем примере.