Блог пользователя goo.gl_SsAhv

Битовое умножение
Автор goo.gl_SsAhv, 12 лет назад, По-русски

Решая задачку D монеты с отборочного russiancodecup мне понадобилась операция "битового умножения". Т.е. по сути перемножения многочленов над полем чисел где умножение это "И" а сложение это "ИЛИ". представить себе это можно так: перемножаем числа в столбик как учили в школе, а числа между двумя прямыми линиями вместо складывания "сИЛИваем". нет ли такой операции для 32-х битовых чисел в assembler? она была бы очень полезна для олимпиадок :)

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Что Вы имели в виду под "такой операцией"?

Вот это?

void OR(int *arr1, int *arr2, int *result, int size) {
	for (int i = 0; i < size; i++) {
		result[i] = arr1[i] | arr2[i];
	}
}

Или вот это?

int OR(int *arr1, int size) {
	int result = 0;
	for (int i = 0; i < size; i++) {
		result |= arr1[i];
	}
	return result;
}

UPD. Я слегка ошибся. Те операции, которые я написал, нужны только для длинного битового умножения.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Имелось ввиду что-то такое

    for (int i = 0; i < 32; i++)  
   if (a & (1<<i))  
       result = result | (b<<i)
    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      (пустая строка)
      ~~~~~
      Здесь код
      ~~~~~
      (пустая строка)

      → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      В меню комментария можно выбрать блочный элемент с кодом, чтобы не писать тильды вручную.

      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Вероятно вот это:

    int a, b, res;
while (a != 0) {
    if ((a & 1) != 0) {
        res |= b;
    }
    a >>= 1;
    b <<= 1;
}

    Ни в x86-ых ни в ARM-овых, ни в AVR32 ассемблерах я такого не помню, т.к. с одной стороны это очень просто реализуется указанным циклом, с другой стороны мало зачем нужно (поэтому в мультимедийных процах вероятно тоже нет?). Возможно в модулях для шифрования бывает, но там обычно можно вставить чип программируемой логики и в нем любые понравившиеся операции запрограмировать... %)

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      В том то и дело что мне бы без цикла это провернуть хотелось за еденицу. Объясню на примере конкретной указанной в посте задачи. Нужно решить подзадачу: дан набор из 100 монет различныйх достоинств, монет каждого типа у нас бесконечно много. Нужно для каждого i знать множество чисел до 10000 представимых монетами из набора, и не используя монеты типа i. я посчитал две динамики d1[i][j] — представима ли сумма j используя только первые i типов монет, и d2[i][j] — представима ли сумма j используя только последние i типов монет. Чтобы для фиксированного типа i получить требуемый массив, нужно "битово переменожить" вектора d1[i-1] и d2[n — i]. Используя битовое сжатие я делал это за L^2 / 32. А вот если бы была требуемая операция, я бы мог это делать за L^2/(32^2), также как перемножение чисел в длинной арифметике. Мое решение требовало порядка 312*2*10^6 операций, что немногим хуже авторского 200 * 2*10^6. Даже не имея битовой операции это можно сделать быстрее, если построить заранее массив размера 2^k, где для каждой маски длины k хранить помноженный на неё второй массив, и затем приИЛИть все блоками по k бит — 2^k*L/32+(L/K)*(L/32). Но битовая операция все-таки была бы покруче. Предпосчитать операцию для двух масок хуже, ибо будет рандомная долбёжка по памяти, а это много медленнее чем последовательное чтение двух массивов и сИЛИвание их в третий.

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        "и затем приИЛИть все блоками по k бит" О, как раз вспомнил единственную частую практическую задачу где нечто похожее есть — рассчёт CRC — делается именно так как ты говоришь.

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

        К сожалению поискав сейчас в инете даже для этой достаточно частой задачки я не нашёл упоминаний о "хардварных" реализациях расширениях для процессоров настольных компов (тех что начинались с MMX, SSE и т.п.)... Может кто-то будет удачливее, но мне попадались только ссылки на "пристёгиваемые" хардварные ускорители... :-(

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          В crc сКСОРивание. полином над полем {0,1} умножение И, сложение XOR(Исключающее ИЛИ). короче действия над скалярами по модулю 2.

          → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

нет ли такой операции для 32-х битовых чисел в assembler? она была бы очень полезна для олимпиадок :)

А как бы она пригодилась? Разве где-то кроме codejam ассемблерные вставки можно применять?

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Речь идет о выполнении свертки битов по операции или, я правильно понимаю?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Ну да, зачем тыщу синонимов приводить, я двумя способами объяснил: математически и на пальцах. Также операцию описывают программы PavelKunyavskiy и RodionGork.

    → Ответить