Solved

Implementation of a new data type (64-bit integer)

Posted on 1998-11-15
17
326 Views
Last Modified: 2010-04-01
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:

class INT64{
      private:
            unsigned long data[2];
      public:
            INT64();                  //constructor
            friend INT64 operator+(const INT64 &val1, const INT64 &val2);
            friend INT64 operator-(const INT64 &val1, const INT64 &val2);
            friend INT64 operator*(const INT64 &val1, const INT64 &val2);
            friend INT64 operator/(const INT64 &val1, const INT64 &val2);
            friend INT64 operator%(const INT64 &val1, const INT64 &val2);
            friend int operator==(const INT64 &val1, const INT64 &val2);
            ostream & operator<<(ostream & outs, const INT64 & val);
            istream & operator>>(istream & ins, INT64 & val);
};


Can anyone help me to implement the member functions inside the class?
0
Comment
Question by:csdenis
17 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 1177952
We can help some, but for school work we cannot give you the answer (that is unethical ad grounds for removal from the site.)
0
 
LVL 22

Expert Comment

by:nietod
ID: 1177953
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.)


0
 
LVL 2

Expert Comment

by:abesoft
ID: 1177954
>I would start by writting a copy constructor and a constructor from an ordinary integer.  

You will also want to write an assignment operator, I would think...
0
 
LVL 22

Expert Comment

by:nietod
ID: 1177955
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
 

Author Comment

by:csdenis
ID: 1177956
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 INT64::operator= (const INT64 &val1)
{
   data[0] = val1.data[0];
   data[1] = val1.data[1];
}

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;};
       temp.data[1] += data[1] + val1.data[1];
       return temp;

  }

INT64 INT64::operator- (const INT64 &val1){

      INT64 temp;

      temp.data[1] = data[1]-val1.data[1];
      temp.data[0] = data[0]-val1.data[0];

      return temp;

  }

INT64 INT64::operator* (const INT64 &val1){

      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
 

Author Comment

by:csdenis
ID: 1177957
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.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1177958
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;

       }

0
 
LVL 22

Expert Comment

by:nietod
ID: 1177959
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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 

Author Comment

by:csdenis
ID: 1177960
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;};
      };



0
 
LVL 22

Expert Comment

by:nietod
ID: 1177961
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
 

Author Comment

by:csdenis
ID: 1177962
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
 

Author Comment

by:csdenis
ID: 1177963
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
 
LVL 22

Accepted Solution

by:
nietod earned 200 total points
ID: 1177964
>> 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

Cls Cls::operator +(const Cls &Rht) const;

make sense?
0
 
LVL 22

Expert Comment

by:nietod
ID: 1177965
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;
0
 
LVL 22

Expert Comment

by:nietod
ID: 1177966
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;
     }

     return temp;

     }
0
 
LVL 1

Expert Comment

by:payn
ID: 1177967
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...

0
 
LVL 22

Expert Comment

by:nietod
ID: 1177968
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

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

707 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now