Here I am tasked with creating an UnsignedBigInteger class that can handle numbers bigger than a long. Am allowed to use a byte array as the internal representation, uint8_t[].
What I came up with is a UnsignedBigInteger type storing the integer inside an array of uint8_t buckets. I work in 64bit architecture (-m64 flag to the compiler).
I ran into a problem while trying to code an operator- between two of my custom objects. We are dealing with unsigned integers, say a and b: when a < b, a - b should follow the rules of modular arithmetic (refer to this question for further info on modular arithmetic).
Here is my attempt:
#include <cstdio>
#include <cstdint>
#include <limits>
#include <cassert>
class UnsignedBigInteger {
public:
constexpr static unsigned long long two_fifty_five{0xffULL}; // 0xff = 0d00000255 = 2^(8) - 1
constexpr static unsigned long long max_ull{std::numeric_limits<unsigned long long int>::max()};
UnsignedBigInteger() = default;
UnsignedBigInteger(const unsigned long long value) {
printf("value = %llu\n", value);
unsigned long long shift{two_fifty_five};
for (size_t i=0; i!=len; ++i) {
_value[i] = (value & shift) >> (8 * i);
printf("_value[%lu] in binary: %llb - shift: %llb\n", i, _value[i], shift);
shift <<= 8;
};
// above is equivalent to:
// _value[0] = value & 0xff;
// _value[1] = value & (0xff << 8);
// _value[2] = value & (0xff << 16);
// ... _value[6] = value & (0xff << 56);
}
unsigned long long int get() const {
unsigned long long int result{};
for (size_t i=0; i!=len; ++i) {
result += (_value[i] << (8*i));
printf("get result[%lu] = %llu, or in binary %llb\n", i, result, result);
}
return result;
}
UnsignedBigInteger operator-(const UnsignedBigInteger& addend) const {
UnsignedBigInteger result{};
for (size_t i=0; i!=len; ++i) {
result._value[i] = (_value[i] - addend._value[i]) % two_fifty_five;
(this->get() < addend.get()) && (result._value[i] == 0) ?
(result._value[i] = two_fifty_five) : true;
printf("subtraction result, buckets: _value[%lu]: %llb\n", i, result._value[i]);
}
printf("subtraction result obtained with get(): %llu\n", result.get());
return result;
}
private:
constexpr static size_t len = 7;
uint8_t _value[len];
};
int main() {
// verify you are in 64-bit environment
constexpr static unsigned long long max_ull{std::numeric_limits<unsigned long long int>::max()};
assert(max_ull == 18'446'744'073'709'551'615ULL); // = 2^64 - 1 = billions of billions
printf("ULLONG_MAX is set for 64bit arithmetics: %llu - binary: %llb\n\n", max_ull, max_ull);
printf("Define two UnsignedBigInteger objects: \n");
UnsignedBigInteger a{13ULL}, b{27ULL};
printf("\nSubtract them:\n");
UnsignedBigInteger a_minus_b = a - b;
printf("\nSUBTRACTION RESULT, FROM MAIN() PROGRAM, IS CORRECT:\n");
printf("a - b = %llu --- in binary %llb\n\n", a_minus_b, a_minus_b);
// should behave like this:
printf("\nAttempting to reproduce modular arithmetic for unsigned integer subtraction, as below:\n");
unsigned int five = 5, seven = 7;
unsigned int aa = five - seven;
printf("uint aa = 5 - 7 = %u\n", aa);
}
Here is the runnable version of MWE above on godbolt link.
It can be seen from the output console that the result of the subtraction is given correctly from the main program (follows modular arithmetic), while the printf from the get() function I set up during debugging seems unable to handle numbers higher than 24-bits (see total break of pattern in chunk of output below, get result[3]).
get result[0] = 242, or in binary 11110010
get result[1] = 65522, or in binary 1111111111110010
get result[2] = 16777202, or in binary 111111111111111111110010
get result[3] = 18446744073709551602, or in binary 1111111111111111111111111111111111111111111111111111111111110010
get result[4] = 241, or in binary 11110001
get result[5] = 65521, or in binary 1111111111110001
get result[6] = 16777201, or in binary 111111111111111111110001
subtraction result obtained with get(): 16777201
SUBTRACTION RESULT, FROM MAIN() PROGRAM, IS CORRECT:
a - b = 72057594037927922
I am puzzled because get() should be the output interface for UnsignedBigInteger. What I print in main is a unsigned long long, which is converted from UnsignedBigInteger implicitly as I did not even set up a type conversion operator.
std::coutinstead ofprintf. One wrong move with theprintfformat specifier can cause output to display differently (or cause undefined behavior). The godbolt link shows warnings about this.warning: format specifies type 'unsigned long long' but the argument has type 'UnsignedBigInteger' [-Wformat]-- That is very suspicious, asprintfhas no idea whatUnsignedBigIntegeris. Unless there was some type of casting operator defined inUnsignedBigIntegerwhich I am missing, this usage ofprintfis undefined behavior.result += (_value[i] << (8 * i));-- What if8 * iexceeds the number of bits represent by auint8_t? Shifting a value greater than the number of bits is undefined behavior._value[i] << (8*i)the left operand is implicitly promoted toint(and the right operand is alreadysize_t)