Подтвердить что ты не робот

Побитовая интервальная арифметика

Недавно я прочитал интересный нить в группе новостей D, которая в основном просит,

Учитывая два (подписанных) целых числа a & isin; [a min, a max], b & isin; [b min, b max], что является самым трудным интервалом для | б?

Я думаю, что если интервальная арифметика может быть применена к общим побитовым операторам (предполагая бесконечные биты). Побитовые NOT и сдвиги тривиальны, так как они просто соответствуют -1 & минус; x и 2 n x. Но побитовое-AND/OR намного сложнее из-за сочетания поразрядных и арифметических свойств.

Существует ли алгоритм полиномиального времени для вычисления интервалов побитового-AND/OR?

Примечание:

  • Предположим, что все побитовые операции выполняются в линейном времени (количества бит), а test/set бит - постоянное время.
  • Алгоритм грубой силы работает в экспоненциальном времени.
  • Поскольку ~(a | b) = ~a & ~b, решение проблемы с поразрядным и -NOT подразумевает поразрядное ИЛИ.
  • Хотя содержание этого потока предполагает min {a | b} = max (a min, b min), это не самая узкая граница. Просто рассмотрите [2, 3] | [8, 9] = [10, 11].)
  • На самом деле для работы с беззнаковой арифметикой достаточно, так как мы можем разбить подписанный интервал на отрицательные и неотрицательные подмножества и использовать законы Мормага и коммутативность только побитовые-AND, -OR и -AND-NOT случаи на неотрицательных интервалах должны быть решен.
4b9b3361

ОТВЕТЫ

Ответ 1

Для интервала [a min, max] неотрицательных целых чисел мы можем вычислить поразрядный минимум a 0, где бит независимо устанавливаются равными 0, когда это возможно в пределах интервала. Точно так же мы можем вычислить поразрядный максимум a 1, где биты устанавливаются на 1 как можно больше в интервале. Для [b min, b max] мы делаем то же самое и получаем b 0 и b 1. Тогда интервал результата [a 0 | b 0, a 1 | б <суб > 1суб > ].

Легко проверить бит, значения которого он может взять для a от [a min, max]. Для бит n, если все биты m с m >= n согласуются в min и max, тогда значение принудительно, иначе оно может быть 0 или 1.

Это можно сделать в O (n).

Записанный случай оставлен в качестве упражнения для читателя. Первым шагом является предоставление определения того, что означают побитовые операторы для отрицательных целых чисел.

Изменить: К сожалению, это неверно: рассмотрите случай, когда [a min, max] = [b min, b max] = [1,2]. Тогда a | b может быть либо 1, 2, либо 3, но побитовое минимальное значение равно 0.

Ответ 2

Argh. Вы уверены, что их нужно подписать целыми числами? Это просто поднимает груду раздражающих случаев, когда вам приходится переворачивать вещи.

Если мы ограничимся целыми числами без знака, мы можем просто спуститься по битам, чтобы найти максимум. Любой бит выше самого высокого бита, установленный в max(a_max , b_max), очевидно, не может быть включен. Предположим без ограничения общности, что a_max > b_max. Храните все биты в a_max, пока мы не достигнем наивысшего бита в b_max. Затем сохраните все биты обоих, пока мы не получим гибкость, по крайней мере, на одной стороне (т.е. Мы можем выбрать число в допустимом диапазоне, который будет перебрасывать этот бит). Если другая сторона не может установить бит в 1, установите его на 1 и продолжайте движение (установка одного более высокого бита всегда будет бить, устанавливая все младшие бит). В противном случае задайте свой ответ (этот бит - 1), который поместит 1 во все остальные биты, и вы закончите.

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

Это O (n) в количестве бит, если мы можем сделать математику по целым числам в O (1) раз. В противном случае это O (n ^ 2).

Вот как это работает на вашем примере из [2,3] | [8,9]

101 -> 1xx works
10 to 11 -> x1x always set ; 11x doesn't fit in a so we're not done
11 can set last bit -> 111
100 -> 1xx must be set
10 to 11 -> x1x must be set ; 11x doesn't fit so we're not done
10 has xx0 as does 100 -> xx0 works -> 110

Изменить: добавление битов знака не изменяет порядок алгоритма, но для этого требуется более раздражающая бухгалтерская отчетность. Если вы не можете избавиться от знакового бита, тогда вы переключаете минимальные и максимальные стратегии (т.е. Устанавливаете против битов). Если это необязательно, минимальное значение устанавливается, когда вы устанавливаете его, а затем пытаетесь сохранить все остальное без изменений; max - это когда вы его отменили, а затем попытайтесь сохранить все остальное.

Второе редактирование: здесь другой пример; оба диапазона: [1001, 1100]:

Must keep first bit -> 1xxx
Can set 2nd bit -> x1xx
Other _could have but did not need to_ set 2nd bit -> set 2nd bit -1 -> xx11
-> 1111 is max
Must keep first bit -> 1xxx
Neither needs 2nd bit -> x0xx
Neither needs 3rd bit -> xx0x
Both need 4th bit -> xxx1
-> 1001 is min

Ответ 3

Я просто сделал это для unsigned ints. Границы не идеальны, но довольно плотные. Для 100 000 случайных входов менее 200 были отключены более чем на 0,1% от фактического интервала, вычисленного с помощью выборки. И он всегда консервативен (содержит реальные границы).

Ключ должен использовать функцию FindLeadingOnes как строительный блок. Это позволяет выражать случаи, когда значимые биты соответствуют друг другу. Это важно, поскольку интервал целых чисел имеет свойство в старших битах, которые соответствуют верхней и нижней границам, также соответствуют всем значениям в интервале. Таким образом, учитывая, что ведущие совпадающие биты позволяют вычислять наиболее значимые биты конечных точек выходного интервала.

Кроме того, для средних битов, которые являются постоянными в течение одного интервала ввода, но изменяются в другом интервале ввода, необходимо применить оператор к верхней и нижней границам, чтобы получить интервал для этих битов. Это видно в iXOr.

Наконец, верхняя граница для AND равна min (left.upper, right.upper), потому что ни один бит в одном из них не может быть одним из них. Аналогично для нижней границы OR.

(Не обращайте внимания на вещи ToInt и ToFloat. Я на самом деле делаю это по номерам с фиксированной точкой. Если вы просто сделаете эти функции без операций, это будет нормально работать.

interval iAnd(const interval lv, const interval rv)
{
    unsigned int ll = ToInt(lv.lower), lu = ToInt(lv.upper), rl = ToInt(rv.lower), ru = ToInt(rv.upper);

    unsigned int lvx = FindLeadingOnes(~(ll ^ lu));
    unsigned int rvx = FindLeadingOnes(~(rl ^ ru));
    unsigned int constmask = (lvx | rvx);

    return interval(ToFloat((ll & rl) & constmask), ToFloat(std::min(lu, ru)));
}

и OR:

interval iOr(const interval lv, const interval rv)
{
    unsigned int ll = ToInt(lv.lower), lu = ToInt(lv.upper), rl = ToInt(rv.lower), ru = ToInt(rv.upper);

    unsigned int lvx = FindLeadingOnes(ll & lu) | FindLeadingOnes(~ll & ~lu);
    unsigned int rvx = FindLeadingOnes(rl & ru) | FindLeadingOnes(~rl & ~ru);
    unsigned int constmask = (lvx | rvx);

    return interval(ToFloat(std::max(ll, rl)), ToFloat((lu | ru) | ~constmask));
}

и XOR:

interval iXOr(const interval lv, const interval rv)
{
    unsigned int ll = ToInt(lv.lower), lu = ToInt(lv.upper), rl = ToInt(rv.lower), ru = ToInt(rv.upper);

    unsigned int lvx = FindLeadingOnes(ll & lu) | FindLeadingOnes(~ll & ~lu);
    unsigned int rvx = FindLeadingOnes(rl & ru) | FindLeadingOnes(~rl & ~ru);
    unsigned int constmask = (lvx | rvx);
    interval iout(ToFloat((ll ^ rl) & constmask), ToFloat((lu ^ ru) & constmask)); // Not sure which is larger; interval constructor sorts them.

    iout.extend(ToFloat(ToInt(iout.upper) | ~constmask)); // Now that the upper is known, extend it upward for the lsbs.

    return iout;
}

И вот моя FindLeadingOnes (для моей 16-битной фиксированной точки. Вы можете использовать больше бит, хотя:

unsigned int FindLeadingOnes(unsigned int v)
{
    for(unsigned int mask = 0x8000; mask != 0xffff; mask |= mask >> 1u) {
        if ((mask & v) != mask)
            return (mask << 1u) & 0xffff;
    }

    return 0xffff;
}