Changeset 3783


Ignore:
Timestamp:
Jan 14, 2015, 1:12:47 AM (7 years ago)
Author:
sam
Message:

math: add bitwise operators for bigints, comparison operators, unary
plus and minus, subtraction, and a lot of unit tests.

Location:
trunk/src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/lol/math/bigint.h

    r3782 r3783  
    9595    explicit bigint(bigint<M,T> const &x)
    9696    {
    97         for (int i = 0; i < (N < M) ? N : M; ++i)
     97        for (unsigned int i = 0; i < (N < M) ? N : M; ++i)
    9898            m_digits[i] = x.m_digits[i];
    9999
     
    101101        {
    102102            T padding = x.is_negative() ? digit_mask : (T)0;
    103             for (int i = M; i < N; ++i)
     103            for (unsigned int i = M; i < N; ++i)
    104104                m_digits[i] = padding;
    105105        }
     
    107107
    108108    /*
     109     * bigint bitwise not: we just flip all bits except the unused one.
     110     */
     111    bigint<N,T> operator ~() const
     112    {
     113        bigint<N,T> ret;
     114        for (unsigned int i = 0; i < N; ++i)
     115            ret.m_digits[i] = m_digits[i] ^ digit_mask;
     116        return ret;
     117    }
     118
     119    /*
     120     * bigint bitwise AND: just perform a bitwise AND on all digits.
     121     */
     122    bigint<N,T> & operator &=(bigint<N,T> const &x)
     123    {
     124        for (unsigned int i = 0; i < N; ++i)
     125            m_digits[i] &= x.m_digits[i];
     126    }
     127
     128    inline bigint<N,T> operator &(bigint<N,T> const &x) const
     129    {
     130        return bigint<N,T>(*this) &= x;
     131    }
     132
     133    /*
     134     * bigint bitwise OR: just perform a bitwise OR on all digits.
     135     */
     136    bigint<N,T> & operator |=(bigint<N,T> const &x)
     137    {
     138        for (unsigned int i = 0; i < N; ++i)
     139            m_digits[i] |= x.m_digits[i];
     140    }
     141
     142    inline bigint<N,T> operator |(bigint<N,T> const &x) const
     143    {
     144        return bigint<N,T>(*this) |= x;
     145    }
     146
     147    /*
     148     * bigint bitwise XOR: just perform a bitwise XOR on all digits.
     149     */
     150    bigint<N,T> & operator ^=(bigint<N,T> const &x)
     151    {
     152        for (unsigned int i = 0; i < N; ++i)
     153            m_digits[i] ^= x.m_digits[i];
     154    }
     155
     156    inline bigint<N,T> operator ^(bigint<N,T> const &x) const
     157    {
     158        return bigint<N,T>(*this) ^= x;
     159    }
     160
     161    /*
     162     * bigint unary plus: a no-op
     163     */
     164    inline bigint<N,T> operator +() const
     165    {
     166        return *this;
     167    }
     168
     169    /*
     170     * bigint unary minus: flip bits and add one
     171     */
     172    bigint<N,T> operator -() const
     173    {
     174        bigint<N,T> ret;
     175        T carry(1);
     176        for (unsigned int i = 0; i < N; ++i)
     177        {
     178            T digit = (m_digits[i] ^ digit_mask) + carry;
     179            ret.m_digits[i] = digit & digit_mask;
     180            carry = (digit & ~digit_mask) ? T(1) : T(0);
     181        }
     182        return ret;
     183    }
     184
     185    /*
    109186     * bigint addition: we add the digits one-to-one, carrying overflows,
    110      * and replace digits with padding if one of the two operands is
    111      * shorter.
    112      */
    113     template<int M>
     187     * and pad missing digits if one of the two operands is shorter.
     188     */
     189    template<unsigned int M>
    114190    bigint<(N > M) ? N : M, T> operator +(bigint<M,T> const &x) const
    115191    {
     
    118194        T x_padding = x.is_negative() ? digit_mask : (T)0;
    119195        T carry(0);
    120         for (int i = 0; i < (N > M) ? N : M; ++i)
     196        for (unsigned int i = 0; i < ((N > M) ? N : M); ++i)
    121197        {
    122198            T digit = (i < N ? m_digits[i] : padding)
     
    129205    }
    130206
     207    /*
     208     * bigint subtraction: a combination of addition and unary minus;
     209     * we add the result of flipping digits and adding one.
     210     */
     211    template<unsigned int M>
     212    bigint<(N > M) ? N : M, T> operator -(bigint<M,T> const &x) const
     213    {
     214        bigint<(N > M) ? N : M, T> ret;
     215        T padding = is_negative() ? digit_mask : (T)0;
     216        T x_padding = x.is_negative() ? digit_mask : (T)0;
     217        T carry(1);
     218        for (unsigned int i = 0; i < ((N > M) ? N : M); ++i)
     219        {
     220            T digit = (i < N ? m_digits[i] : padding)
     221                    + ((i < M ? x.m_digits[i] : x_padding) ^ digit_mask)
     222                    + carry;
     223            ret.m_digits[i] = digit & digit_mask;
     224            carry = (digit & ~digit_mask) ? T(1) : T(0);
     225        }
     226        return ret;
     227    }
     228
     229    /*
     230     * bigint equality operator: just use memcmp.
     231     * FIXME: we could easily support operands of different sizes.
     232     */
     233    inline bool operator ==(bigint<N,T> const &x) const
     234    {
     235        return memcmp(m_digits, x.m_digits, sizeof(m_digits)) == 0;
     236    }
     237
     238    inline bool operator !=(bigint<N,T> const &x) const
     239    {
     240        return !(*this == x);
     241    }
     242
     243    /*
     244     * bigint comparison operators: take a quick decision if signs
     245     * differ. Otherwise, compare all digits.
     246     */
     247    bool operator >(bigint<N,T> const &x) const
     248    {
     249        if (is_negative() ^ x.is_negative())
     250            return x.is_negative();
     251        for (unsigned int i = 0; i < N; ++i)
     252            if (m_digits[i] != x.m_digits[i])
     253                return m_digits[i] > x.m_digits[i];
     254        return false;
     255    }
     256
     257    bool operator <(bigint<N,T> const &x) const
     258    {
     259        if (is_negative() ^ x.is_negative())
     260            return is_negative();
     261        for (unsigned int i = 0; i < N; ++i)
     262            if (m_digits[i] != x.m_digits[i])
     263                return m_digits[i] < x.m_digits[i];
     264        return false;
     265    }
     266
     267    inline bool operator >=(bigint<N,T> const &x) const
     268    {
     269        return !(*this < x);
     270    }
     271
     272    inline bool operator <=(bigint<N,T> const &x) const
     273    {
     274        return !(*this > x);
     275    }
     276
    131277private:
     278    /* Allow other types of bigints to access our private members */
     279    template<unsigned int, typename> friend class bigint;
     280
    132281    inline bool is_negative() const
    133282    {
     
    140289};
    141290
     291typedef bigint<8, uint32_t> int248_t;
     292typedef bigint<16, uint32_t> int496_t;
     293typedef bigint<32, uint32_t> int992_t;
     294
    142295} /* namespace lol */
    143296
  • trunk/src/t/math/bigint.cpp

    r3782 r3783  
    4747    }
    4848
    49     lolunit_declare_test(empty_bigint_is_zero)
    50     {
    51         bigint<0> a, b(1), c(-1);
    52 
    53         lolunit_assert_equal((int)a, 0);
    54         lolunit_assert_equal((int)b, 0);
    55         lolunit_assert_equal((int)c, 0);
     49    lolunit_declare_test(operator_equal)
     50    {
     51        bigint<> a(-1), b(0), c(1);
     52
     53        lolunit_assert(a == a);
     54        lolunit_assert(!(a == b));
     55        lolunit_assert(!(a == c));
     56
     57        lolunit_assert(!(b == a));
     58        lolunit_assert(b == b);
     59        lolunit_assert(!(b == c));
     60
     61        lolunit_assert(!(c == a));
     62        lolunit_assert(!(c == b));
     63        lolunit_assert(c == c);
     64    }
     65
     66    lolunit_declare_test(operator_notequal)
     67    {
     68        bigint<> a(-1), b(0), c(1);
     69
     70        lolunit_assert(!(a != a));
     71        lolunit_assert(a != b);
     72        lolunit_assert(a != c);
     73
     74        lolunit_assert(b != a);
     75        lolunit_assert(!(b != b));
     76        lolunit_assert(b != c);
     77
     78        lolunit_assert(c != a);
     79        lolunit_assert(c != b);
     80        lolunit_assert(!(c != c));
     81    }
     82
     83    lolunit_declare_test(operator_smaller)
     84    {
     85        bigint<> a(-10), b(-1), c(0), d(1), e(10);
     86
     87        lolunit_assert(!(a < a));
     88        lolunit_assert(a < b);
     89        lolunit_assert(a < c);
     90        lolunit_assert(a < d);
     91        lolunit_assert(a < e);
     92
     93        lolunit_assert(!(b < a));
     94        lolunit_assert(!(b < b));
     95        lolunit_assert(b < c);
     96        lolunit_assert(b < d);
     97        lolunit_assert(b < e);
     98
     99        lolunit_assert(!(c < a));
     100        lolunit_assert(!(c < b));
     101        lolunit_assert(!(c < c));
     102        lolunit_assert(c < d);
     103        lolunit_assert(c < e);
     104
     105        lolunit_assert(!(d < a));
     106        lolunit_assert(!(d < b));
     107        lolunit_assert(!(d < c));
     108        lolunit_assert(!(d < d));
     109        lolunit_assert(d < e);
     110
     111        lolunit_assert(!(e < a));
     112        lolunit_assert(!(e < b));
     113        lolunit_assert(!(e < c));
     114        lolunit_assert(!(e < d));
     115        lolunit_assert(!(e < e));
     116    }
     117
     118    lolunit_declare_test(operator_smaller_or_equal)
     119    {
     120        bigint<> a(-10), b(-1), c(0), d(1), e(10);
     121
     122        lolunit_assert(a <= a);
     123        lolunit_assert(a <= b);
     124        lolunit_assert(a <= c);
     125        lolunit_assert(a <= d);
     126        lolunit_assert(a <= e);
     127
     128        lolunit_assert(!(b <= a));
     129        lolunit_assert(b <= b);
     130        lolunit_assert(b <= c);
     131        lolunit_assert(b <= d);
     132        lolunit_assert(b <= e);
     133
     134        lolunit_assert(!(c <= a));
     135        lolunit_assert(!(c <= b));
     136        lolunit_assert(c <= c);
     137        lolunit_assert(c <= d);
     138        lolunit_assert(c <= e);
     139
     140        lolunit_assert(!(d <= a));
     141        lolunit_assert(!(d <= b));
     142        lolunit_assert(!(d <= c));
     143        lolunit_assert(d <= d);
     144        lolunit_assert(d <= e);
     145
     146        lolunit_assert(!(e <= a));
     147        lolunit_assert(!(e <= b));
     148        lolunit_assert(!(e <= c));
     149        lolunit_assert(!(e <= d));
     150        lolunit_assert(e <= e);
     151    }
     152
     153    lolunit_declare_test(operator_greater)
     154    {
     155        bigint<> a(-10), b(-1), c(0), d(1), e(10);
     156
     157        lolunit_assert(!(a > a));
     158        lolunit_assert(!(a > b));
     159        lolunit_assert(!(a > c));
     160        lolunit_assert(!(a > d));
     161        lolunit_assert(!(a > e));
     162
     163        lolunit_assert(b > a);
     164        lolunit_assert(!(b > b));
     165        lolunit_assert(!(b > c));
     166        lolunit_assert(!(b > d));
     167        lolunit_assert(!(b > e));
     168
     169        lolunit_assert(c > a);
     170        lolunit_assert(c > b);
     171        lolunit_assert(!(c > c));
     172        lolunit_assert(!(c > d));
     173        lolunit_assert(!(c > e));
     174
     175        lolunit_assert(d > a);
     176        lolunit_assert(d > b);
     177        lolunit_assert(d > c);
     178        lolunit_assert(!(d > d));
     179        lolunit_assert(!(d > e));
     180
     181        lolunit_assert(e > a);
     182        lolunit_assert(e > b);
     183        lolunit_assert(e > c);
     184        lolunit_assert(e > d);
     185        lolunit_assert(!(e > e));
     186    }
     187
     188    lolunit_declare_test(operator_greater_or_equal)
     189    {
     190        bigint<> a(-10), b(-1), c(0), d(1), e(10);
     191
     192        lolunit_assert(a >= a);
     193        lolunit_assert(!(a >= b));
     194        lolunit_assert(!(a >= c));
     195        lolunit_assert(!(a >= d));
     196        lolunit_assert(!(a >= e));
     197
     198        lolunit_assert(b >= a);
     199        lolunit_assert(b >= b);
     200        lolunit_assert(!(b >= c));
     201        lolunit_assert(!(b >= d));
     202        lolunit_assert(!(b >= e));
     203
     204        lolunit_assert(c >= a);
     205        lolunit_assert(c >= b);
     206        lolunit_assert(c >= c);
     207        lolunit_assert(!(c >= d));
     208        lolunit_assert(!(c >= e));
     209
     210        lolunit_assert(d >= a);
     211        lolunit_assert(d >= b);
     212        lolunit_assert(d >= c);
     213        lolunit_assert(d >= d);
     214        lolunit_assert(!(d >= e));
     215
     216        lolunit_assert(e >= a);
     217        lolunit_assert(e >= b);
     218        lolunit_assert(e >= c);
     219        lolunit_assert(e >= d);
     220        lolunit_assert(e >= e);
    56221    }
    57222};
Note: See TracChangeset for help on using the changeset viewer.