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

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

  1. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    В регистре EAX содержится 32х-разрядное число. Если все 8 тетрад(группы по 4 разряда) различны, нужно установить EAX=-1, а если есть совпадающие - установить EAX=0. Например, для чисел 12345678h или 5A6B7C8Dh на выходе должно быть -1, а для чисел 00000000h, FFFFFFFFh или 0ABCDEF0h нужно установить EAX=0. Оптимизируем по размеру, переходы и вызовы подпрограмм использовать нельзя.
     
  2. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Записать все числа с разными тетрадами (их должно быть не много) в таблицу и упорядочить их по возрастанию. Потом можно использовать двоичный поиск по таблице.

    Но чувствую у тебя есть решение на порядок лучше.
     
  3. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Black_mirror
    Задачку можно свести к проверке наличия нулевых тетрад: сдвигаем влево через CF на 4 бита и делаем xor с исходным вектором, если есть нулевые тетрады, значит есть совпадающие тетрады. И так до первого появления нулевой тетрады.
     
  4. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    murder
    Можно сделать и таблицу, только её нужно будет добавить к размеру кода :)

    crypto
    А зачем сдвигать через CF?) Направление конечно верное, по моим прикидкам такой код без переходов команд 40 займёт, но какие-то возможности я пока видимо упустил.

    всем
    Можно решать и с переходами, такие программы в своей категории сравнивать будем.
     
  5. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Black_mirror
    Чтобы сдвиг был по циклу, тогда каждая тетрада будет сравниваться со всеми другими.
     
  6. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Произведение шести комбинаций xor. Если на выходе 0, значит есть совпадения. Если не 0, значит нету. Как не ноль превратить в -1 без перехода, пока не придумал.
     
  7. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    либо XOR либо SUB, кроме EAX еще 7 регистров EBX, ECX, EDX, ESI, EDI, EBP, ESP если в каждый скопировать EAX а потом сдвинуть каждый ROR или ROL через 4 бита тогда покроем все 32 разрядное поле, дальше не придумал
     
  8. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    Код (Text):
    1. xor edx, edx
    2. add eax, 0xFFFFFFFF
    3. adc edx, 0
    4. mov eax, 0xFFFFFFFF
    5. mul edx
    не?
     
  9. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    salc или sbb eax,eax если используется CF
     
  10. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Кажись нашёл, можно (sbb результат, (dec результат)). Если в результате был 0, то в cf будет единица, иначе 0. Теперь используем какую-нибудь операцию сдига с занесением cf в регистр. Ну а дальше всё совсем тривиально.
     
  11. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Тьфу тупанул, конечно никого сдвига не нужно, главное cf получить, а дальше просто сложить или вычесть с учётом этого флага. ^)
     
  12. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Black_mirror
    Да, флажок я из другой оперы прикрутил.
     
  13. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    n0name
    Да, вполне подходит.
     
  14. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Код (Text):
    1.     mov     edx, eax
    2.     ror     eax, 8
    3.     xor     edx, eax
    4.     mov     eax, 0
    5.     cmp     eax, edx
    6.     sbb     eax, 0
     
  15. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Это было на байты. На тетрады нужно заменить на ROR EAX, 4 :)
     
  16. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Serg50
    Это совсем не та задача, мы проверяем не то, что все тетрады равны, а то что все они уникальны.
     
  17. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Можно циклически сдвигать на 4 бита, ксорить регистр, перемножать четвёрки, и повторять это 7 раз.
     
  18. persicum

    persicum New Member

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

    persicum New Member

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

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Black_mirror
    А проверять наличие нулевой тетрады в конкретном месте можно тупо выделяя эту тетраду, ксоря с маской и сравнивая полученный результат с той же маской (потом сдвиг на 4 влево...)