Implementation of a new data type (64-bit integer)
How to design and implement a 64-bit integers, which is a new data type for C++? The new data type should support the operator +, -, *, /, and % by C++ operator overloading technique.
Here is the class design for the data type INT64:
Whenever you start a class always write the constructors and destructors first. (Ignore the operators for the time being.)
I would start by writting a copy constructor and a constructor from an ordinary integer. Try to write those and post what you get done.
Also I don't think you want the longs in "data[]" to be unsigned. If they are unsigned, you will not be able to represent negative numbers easily. (If your assignment specificly suggested they should be unsigned, leave it. Otherwise, make it signed.)
There are lots of things you will want to write. But I find that students do best if they start by defining the class members, then the constructors, then the destructors. Assingment operator should comme soon after I would think.
0
csdenisAuthor Commented:
I implement the class design and member function like this:
however, i don't know what's wrong with that, it just give out the wrong answer, do you know what's the problem of the algorithm?
class INT64 {
private:
unsigned long data[2];
public:
INT64() {data[0] = 0; data[1] = 0;};
INT64 operator= (const INT64 &val1);
INT64 operator+ (const INT64 &val1);
INT64 operator- (const INT64 &val1);
INT64 operator* (const INT64 &val1);
int operator==(const INT64 &val1);
unsigned long dataget(int i) {return data[i];};
void dataput(int i, unsigned long in_value) {data[i] = in_value;};
};
int INT64::operator==(const INT64 &val1)
{
if (data[0]==val1.data[0]&&data[1]==val1.data[1])
return 1;
else
return 0;
}
INT64 temp;
INT64 b,y,acc; //y=Y-register;b=B-register;acc=accumulator
int i,shift=0;
long constant=1;
constant=constant<<31;
b=val1;
y.data[0]=data[0];
y.data[1]=data[1];
while (shift<63){
if (b.data[0]&1==1){
acc=acc+y;
}
b.data[0]>>1;
if (b.data[1]&1==1){
b.data[0]+=constant;
}
b.data[1]>>1;
if (acc.data[0]&1==1){
b.data[1]+=constant;
}
acc.data[0]>>1;
if (acc.data[1]&1==1){
acc.data[0]+=constant;
}
acc.data[1]>>1;
shift++;
}
// final shift
b.data[0]>>1;
if (b.data[0]&1==1){
b.data[0]+=constant;
}
b.data[1]>>1;
if (acc.data[1]&1==1){
b.data[1]+=constant;
}
acc.data[0]>>1;
if (acc.data[0]&1==1){
acc.data[0]+=constant;
}
acc.data[1]>>1;
}
0
csdenisAuthor Commented:
something to clarify, the '-' operator has not been implemented.
i've just do the '+' and '*' so that i can get the string from the sreen and convert it to the INT64. However, the answer is just wrong.
the class defintion looks pretty good. Usually many of the operators would be friend functions, not class members, but that is okay. If you want to leave them as member functions I recommend you declare some as constant, as I did below. Also note that operator = can return a reference, as shown below.
class INT64 {
private:
unsigned long data[2];
public:
INT64() {data[0] = 0; data[1] = 0;};
INT64 &operator= (const INT64 &val1);
INT64 operator+ (const INT64 &val1) const;
INT64 operator- (const INT64 &val1); const
INT64 operator* (const INT64 &val1) const;
int operator==(const INT64 &val1) const;
unsigned long dataget(int i) {return data[i];} const;
void dataput(int i, unsigned long in_value) {data[i] = in_value;};
};
the == function looks fine. Does it work okay?
the = function looks fine, but it does not return a value try,
INT64 &INT64::operator= (const INT64 &val1)
{
data[0] = val1.data[0];
data[1] = val1.data[1];
return *this; // added this line and the reference in the return value.
}
The problem in operator + is that you have no default constructor so the temp variable starts out
containing garbage. You set the data[0] in temp, but you assume that data[1] is 0 at the start. It isn't!
INT64 INT64::operator+ (const INT64 &val1)
{
INT64 temp;
temp.data[0] = data[0] + val1.data[0];
if ((0xfffffff - data[0]) > val1.data[0]) {temp.data[1] += 1;}; // This line asumes data[i] is 0.
temp.data[1] += data[1] + val1.data[1];
return temp;
Before you do the multiply, I would write some other operators. Write a <<= and >>= operators for shifting bits. Also write the |, |=, &, and &= operators. Note that you really need to write |= and &=, then you can write | and & to use the others, it takes only another second or two.
0
csdenisAuthor Commented:
thanks for your help, the == operator works fine.
I have something that don't understand. you said I don't have a default constructor, but does the following are the default constructor?
class INT64 {
private:
unsigned long data[2];
public:
INT64() {data[0] = 0; data[1] = 0;}; <----Does it already a default constructor?
INT64 operator= (const INT64 &val1);
INT64 operator+ (const INT64 &val1);
INT64 operator- (const INT64 &val1);
INT64 operator* (const INT64 &val1);
int operator==(const INT64 &val1);
unsigned long dataget(int i) {return data[i];};
void dataput(int i, unsigned long in_value) {data[i] = in_value;};
};
My mistake. I didn't see that. So that is not the problem.
Looking closer I suspect that the 0xFFFFFF can't be right. Perhaps you meant 0xFFFFFFFF (5 F's not 6.) To be honest with you I'm not sure if even that is mathematically correct. You could try it and see if it works. The way I believe I've seen it done is to test if the result is less than either of the source values, if so you overflowed, like
if (temp.data[0] < val1.data[0] || temp.data[0] < val2.data[0])
actually,
if ((0xfffffff - data[0]) > val1.data[0]) {temp.data[1] += 1;};
can't be right. perhaps the first data[0] should be temp.data[0]?
0
csdenisAuthor Commented:
I have add the function to overload >>=, but I encounter some difficulty in handling <<=. how can I detect the rightmost bit of data[0] is 1 or 0??
Also, if I does not declare the member function as 'friend', error message will told me that the function can only have one parameter, why would this happen?
class INT64 {
private:
unsigned long data[2];
public:
INT64() {data[0] = 0; data[1] = 0;};
INT64 &operator= (const INT64 &val1);const
INT64 operator+ (const INT64 &val1);const
INT64 operator- (const INT64 &val1);const
INT64 operator* (const INT64 &val1);const
friend INT64 operator<<=(const INT64 &val1, int &shift_bit);const
friend INT64 operator>>=(const INT64 &val1, int &shift_bit);const
int operator==(const INT64 &val1);
unsigned long dataget(int i) {return data[i];};
void dataput(int i, unsigned long in_value) {data[i] = in_value;};
};
INT64 operator>>=(const INT64 &val1, int &shift_bit)
{
INT64 temp;
unsigned long constant=1;
constant = constant<<31;
int i;
temp = val1;
for (i=0;i<shift_bit;i++){
temp.data[0]>>1;
if (temp.data[1]&1==1){
temp.data[0]+=constant;
}
temp.data[1]>>1;
}
return temp;
}
0
csdenisAuthor Commented:
I have add the function to overload >>=, but I encounter some difficulty in handling <<=. how can I detect the rightmost bit of data[0] is 1 or 0??
Also, if I does not declare the member function as 'friend', error message will told me that the function can only have one parameter, why would this happen?
class INT64 {
private:
unsigned long data[2];
public:
INT64() {data[0] = 0; data[1] = 0;};
INT64 &operator= (const INT64 &val1);const
INT64 operator+ (const INT64 &val1);const
INT64 operator- (const INT64 &val1);const
INT64 operator* (const INT64 &val1);const
friend INT64 operator<<=(const INT64 &val1, int &shift_bit);const
friend INT64 operator>>=(const INT64 &val1, int &shift_bit);const
int operator==(const INT64 &val1);
unsigned long dataget(int i) {return data[i];};
void dataput(int i, unsigned long in_value) {data[i] = in_value;};
};
INT64 operator>>=(const INT64 &val1, int &shift_bit)
{
INT64 temp;
unsigned long constant=1;
constant = constant<<31;
int i;
temp = val1;
for (i=0;i<shift_bit;i++){
temp.data[0]>>1;
if (temp.data[1]&1==1){
temp.data[0]+=constant;
}
temp.data[1]>>1;
}
>> Also, if I does not declare the member function as 'friend', error message
>> will told me that the function can only have one parameter, why would this
>> happen?
most binary operators (operators that work on two values) can be handled in either of two ways. They can be non-member functions or they can be member functions. If they are non-member functions, then they are passed two parameters--the two values they operate on. If they are member functions, they are passed only one value. In this case, the value on the right side of the operator. the value on the left side of the operator is not passed as a parameter, instead it is the object for which the function was called for. For example, you could have a non-member operator like
Cls operator +(const Cls &Lft,const Cls &Rht);
this function takes the values on the left and right sides of the + as parameters. But if the function is a member function of Cls, it would take only the value on the right side, like
The >> = function function looks pretty good, it is close but has some problems.
1. The way it written now, it takes two parameters, That means it must be a non=member function, but you have it as member function. either make it a non-member function, or remove the parameter that comes from the left side of the operator (val1). Typically <<= is handled as a member function, but either is okay.
2. Usually the >>= function A) changes the value on the left side of the operator and B) returns a that new value. The way you have it written is more like operator >>, which does not alter the value on the left side but which returns a new value that is the shifted value. i.e.
Y = X << 1; // X stays the same and Y gets shifted value.
Y = X <<= 1; // Both X and Y get shifted value.
3. The code to calculate the "constant" works, but really is need needed. Make constant trully constant ("const") and specify it like;
const int HighBitMask = 1 << 31; // OR
const int HighBitMask = 0x80000000;
Your logic for handling shifting bits out of data[1] and into data[0] is fine. You would do allmost the same thing when shifting to the left. That is, when shifting right, you
1. shift low value 2 test low bit of high value 3 Set High bit of low value (if needed) 4 Shift high value.
for <<= reverse the high and low.
1. shift high value. 2. Test high bit of low value 3. Set low bit of high value (if needed) shift low value.
Exactly the same, but low and high (bits and ints) are reversed and the shifts are in opposite directions.
This question is getting too long. It takes to long to load. If it is okay with you, I would prefer that you e-mail me questions directly. Send a current copy of the program with each e-mail--that works well.
My address is nietod@theshop.net.
NT64 operator>>=(const INT64 &val1, int &shift_bit)
{
INT64 temp;
unsigned long constant=1;
constant = constant<<31;
int i;
temp = val1;
for (i=0;i<shift_bit;i++){
temp.data[0]>>1;
if (temp.data[1]&1==1){
temp.data[0]+=constant;
}
temp.data[1]>>1;
}
Nietod, why did you suggest making data[] signed? For the most significant dword that's fine, but for anything else that's terrible. You end up with sign bits at both bit 63 and bit 31 instead of just at 63, and you have to go out of your way to deal with that.
To see the problem, let's imagine we're building a 4-bit int out of two 2-bit ints. So let's add 3 + 3, aka 0011 + 0011.
If the LSD is signed, this is (0, -1) + (0, -1), which does not overflow, and ends up giving you (0, -2), or 0010, or 2. Which is wrong.
If the LSD is unsigned, this is (0, 3) + (0, 3), which overflows, giving you (1, 2), or 0110, or 6. Which is correct.
When you only have two dwords, it's not that big of a deal, but generally it's much easier to deal with faking a sign bit for the most significant element then faking unsigned high bits for all of the rest of the elements. Or you can explicitly use one signed element and the rest unsigned...
payn, there is no sign bit in two's compliment math, at least not in the sense you suggest. For example, consider a signed 16 integer. Is the low byte unsigned and the high byte signed?
However, on second thought, I think the best way to handle this is with unsigned math and to "manually" interpret the values as signed.
0
Question has a verified solution.
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.