Arytmetyka Interwałów Bitowych

Argh. Jesteś pewien, że to muszą być podpisane liczby całkowite? To tylko wywołuje stos irytujących spraw, w których musisz coś przewrócić.

Jeśli ograniczymy się do niepodpisanych liczb całkowitych, możemy po prostu przejść po bitach, aby znaleźć maksimum. Każdy bit powyżej najwyższego bitu ustawionego w max(a_max , b_max) oczywiście nie może być włączony. Załóżmy bez utraty ogólności, że a_max > b_max. Zachowaj wszystkie bity w a_max, dopóki nie osiągniemy najwyższego bitu w b_max. Następnie zachowaj wszystkie bity obu, dopóki nie będziemy mieć elastyczności na co najmniej jedną stronę (tzn. możemy wybrać liczbę z dozwolonego zakresu, która odwróci ten bit). Jeśli druga strona nie może ustawić tego bitu na 1, ustaw go na 1 i kontynuuj (ustawienie jednego wyższego bitu zawsze bije ustawienie wszystkich niższych bitów). W przeciwnym razie Ustaw odpowiedź na (ten bit-1), który umieści 1 we wszystkich pozostałych bitach i gotowe.

Teraz robimy to samo dla minimum, z wyjątkiem tego, że unikamy ustawiania bitów przy każdej okazji, ale wykorzystujemy każdą okazję do sparowania bitów, jeśli jeden strona musi ustawić jeden.

To jest O (n) w liczbie bitów, jeśli możemy wykonać matematykę na liczbach całkowitych w czasie O(1). W przeciwnym razie jest O (n^2).

Oto Jak to działa na twoim przykładzie [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

Edit: dodawanie bitów znaków nie zmienia kolejności algorytmu, ale wymaga bardziej irytującej księgowości. Jeśli nie możesz pozbyć się bitu znaku, odwracasz strategie min i max (tj. set vs.don ' t set bits). Jeśli jest to opcjonalne, min jest po ustawieniu go, a następnie spróbuj aby Wszystko inne było wyłączone; maksymalna wartość jest wtedy, gdy ją odłączysz, a następnie spróbuj utrzymać wszystko inne ustawione.

Druga edycja: oto kolejny przykład; oba zakresy to [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

Zrobiłem to dla niepodpisanych intów. Granice nie są idealne, ale są dość ciasne. Dla 100 000 losowych wejść, mniej niż 200 było wyłączone o więcej niż 0,1% od rzeczywistego przedziału obliczonego przez pobieranie próbek. I zawsze jest konserwatywny(zawiera prawdziwe granice).

Kluczem jest użycie funkcji FindLeadingOnes jako budulca. Pozwala to wyrażać przypadki, w których znaczące bity pasują do siebie. Jest to ważne, ponieważ interwał liczb całkowitych ma właściwość na bitach wiodących, która dopasuj w górnej i dolnej granicy również dopasuj dla wszystkich wartości w przedziale. Tak więc, rozważenie wiodących pasujących bitów pozwala obliczyć najbardziej znaczące bity punktów końcowych interwału wyjściowego.

Również dla środkowych bitów, które są stałe w jednym interwale wejściowym, ale różnią się w drugim interwale wejściowym, konieczne jest zastosowanie operatora zarówno do górnej, jak i dolnej granicy, aby uzyskać interwał dla tych bitów. Jest to widoczne w iXOr.

Wreszcie górna granica dla i jest / min (Lew.górny, prawy.upper), ponieważ żaden bit, który jest zerowy w jednym z nich, nie może być jednym na wyjściu. Podobne do dolnej granicy OR.

(nie zwracaj uwagi na ToInt i ToFloat rzeczy. Robię to na stałych numerach punktowych. Jeśli tylko sprawisz, że te funkcje będą bez operacji, to będzie dobrze działać.

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)));
}

I 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));
}

I 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;
}

A oto moje FindLeadingOnes (dla mojego 16-bitowego punktu stałego. Można jednak użyć więcej bitów:

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;
}