fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. struct binary
  6. {
  7.     void display() const { for( int d : digits ) std::cout << d ; std::cout << '\n' ; }
  8.     binary operator+ ( const binary& that ) const ;
  9.  
  10.     /*private:*/ std::vector<int> digits ;
  11. };
  12.  
  13. binary binary::operator+ ( const binary& that ) const
  14. {
  15.    auto n = std::max( digits.size(), that.digits.size() ) ; // larger size
  16.    n += 1 ; // may overflow, so one more
  17.  
  18.    std::vector<int> first( digits.rbegin(), digits.rend() ) ;
  19.    // first now contains the first set of digits in reverse order
  20.    first.resize(n) ; // make its size equal to the larger size (add zeroes at the end)
  21.  
  22.    std::vector<int> second( that.digits.rbegin(), that.digits.rend() ) ;
  23.    // second now contains the second set of digits in reverse order
  24.    second.resize(n) ; // make its size equal to the larger size (add zeroes at the end)
  25.  
  26.    binary result ;
  27.    result.digits.resize(n) ;
  28.  
  29.    // simulate hand-addition with carry
  30.    // but left to right because digits are reversed
  31.    int carry = 0 ;
  32.    for( std::size_t i = 0 ; i < first.size() ; ++i ) // for each digit
  33.    {
  34.        int& d = result.digits[i] ;
  35.        d = first[i] + second[i] + carry ; // add the two digits, carry
  36.        // a digit must be either 0 or 1; so
  37.        if( d > 1 ) { carry = d / 2 ; d %= 2 ; } // adjust for overflow
  38.        else carry = 0 ;
  39.    }
  40.  
  41.    // if the most significant (in reverse order) digit is zero, remove it
  42.    if( result.digits.back() == 0 ) result.digits.pop_back() ;
  43.    // reverse the digits of the result
  44.    std::reverse( result.digits.begin(), result.digits.end() ) ;
  45.  
  46.    return result ;
  47. }
  48.  
  49. int main()
  50. {
  51.     const binary a { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } } ;
  52.     a.display() ;
  53.  
  54.     const binary b { { 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } } ;
  55.     b.display() ;
  56.  
  57.     const binary c = a + b ;
  58.     c.display() ;
  59. }
  60.  
Success #stdin #stdout 0s 3032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
11111111111111111
10011111111111
100010011111111110
https://ideone.com/KIEHCw
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!