Added the right-shift computation

Signed-off-by: Olivier Gayot <og@satcom1.com>

2 files changed, 75 insertions, 0 deletions

diff --git a/number.cpp b/number.cpp
index c3dd33c..75fd0f8 100644
--- a/number.cpp
+++ b/number.cpp
@@ -184,6 +184,42 @@ number::operator<<(std::uint32_t shift) const
     return result;
 }
 
+number
+number::operator>>(std::uint32_t shift) const
+{
+    number result(*this);
+
+    /*
+     * Since, internally, we store 32-bits-wide integers, we can just get rid
+     * of "shift / 32" first integers.
+     */
+    for (unsigned int i = 0; i < shift / 32; ++i) {
+        if (result == 0) {
+            return 0;
+        }
+
+        result._operands.pop_front();
+    }
+
+    shift %= 32;
+
+    std::uint32_t carry = 0;
+
+    for (auto it = result._operands.rbegin(); it != result._operands.rend(); ++it) {
+        auto &operand = *it;
+
+        std::uint32_t tmp = ((1ull * operand) >> shift) | carry;
+
+        carry = ((1ull * operand) << (32 - shift));
+
+        operand = tmp;
+    }
+
+    result.shrink_to_fit();
+
+    return result;
+}
+
 /* }}} */
 /* Comparison operators {{{ */
 
@@ -266,6 +302,14 @@ number::operator<<=(std::uint32_t n)
 }
 
 number &
+number::operator>>=(std::uint32_t n)
+{
+    *this = *this >> n;
+
+    return *this;
+}
+
+number &
 number::operator++()
 {
     *this = *this + 1;
@@ -275,6 +319,14 @@ number::operator++()
 
 /* }}} */
 
+void
+number::shrink_to_fit()
+{
+    while (_operands.back() == 0) {
+        _operands.pop_back();
+    }
+}
+
 std::ostream &
 operator<<(std::ostream &os, const number &n)
 {
diff --git a/number.h b/number.h
index 5043f1b..b1edbd6 100644
--- a/number.h
+++ b/number.h
@@ -63,6 +63,14 @@ public:
     number operator<<(std::uint32_t n) const;
 
     /**
+     * \brief Return a number equals to this number where n bits have been
+     * shifted to the right.
+     *
+     * \param n Number of bits to shift.
+     */
+    number operator>>(std::uint32_t) const;
+
+    /**
      * \brief Tell whether the number passed as parameter is strictly less than
      * this number.
      *
@@ -130,11 +138,26 @@ public:
     number &operator<<=(std::uint32_t);
 
     /**
+     * \brief Shift the number n bits to the right.
+     *
+     * \param n Number of bits to shift.
+     */
+    number &operator>>=(std::uint32_t);
+
+    /**
      * \brief Increment this number.
      */
     number &operator++();
 
 private:
+    /**
+     * \brief Remove unused leading 0 operands.
+     *
+     * Call this method after shrinking the number so that leading 0 operands
+     * are removed.
+     */
+    void shrink_to_fit();
+
      /* First item is the least significant. */
     std::list<std::uint32_t> _operands;
 };