problemscpp
A collection of my answers to algorithm problems in c++.
Public 成员函数 | Private 成员函数 | Private 属性 | 友元 | 所有成员列表
BigInt类 参考

高精度整数 更多...

#include <templates.h>

Public 成员函数

 BigInt ()
 
 BigInt (const BigInt &bi)
 
 BigInt (const char *str)
 
 BigInt (const string &str)
 
 BigInt (int n)
 
 BigInt (long long n)
 
 BigInt (long n)
 
 BigInt (short n)
 
 BigInt (unsigned int n)
 
 BigInt (unsigned long long n)
 
 BigInt (unsigned long n)
 
 BigInt (unsigned short n)
 
bool operator!= (const BigInt &bi) const
 
BigInt operator% (const BigInt &bi) const
 
BigInt & operator%= (const BigInt &bi)
 
BigInt operator* (const BigInt &bi) const
 
BigInt & operator*= (const BigInt &bi)
 
BigInt operator+ (const BigInt &bi) const
 
BigInt & operator++ ()
 
BigInt operator++ (int)
 
BigInt & operator+= (const BigInt &bi)
 
BigInt operator- () const
 
BigInt operator- (const BigInt &bi) const
 
BigInt & operator-- ()
 
BigInt operator-- (int)
 
BigInt & operator-= (const BigInt &bi)
 
BigInt operator/ (const BigInt &bi) const
 
BigInt & operator/= (const BigInt &bi)
 
bool operator< (const BigInt &bi) const
 
bool operator<= (const BigInt &bi) const
 
bool operator== (const BigInt &bi) const
 
bool operator> (const BigInt &bi) const
 
bool operator>= (const BigInt &bi) const
 

Private 成员函数

 BigInt (const vector< unsigned short > &vec, bool positive)
 
unsigned long get_size () const
 
vector< unsigned short > operator* (unsigned short n) const
 
unsigned short operator[] (unsigned long) const
 

Private 属性

bool positive = true
 
vector< unsigned short > vec = {}
 

友元

ostream & operator<< (ostream &os, const BigInt &)
 
istream & operator>> (istream &is, const BigInt &)
 

详细描述

高精度整数

在文件 templates.h 第 23 行定义.

构造及析构函数说明

◆ BigInt() [1/13]

BigInt::BigInt ( const vector< unsigned short > &  vec,
bool  positive 
)
private

在文件 templates.cpp 第 31 行定义.

32 : positive(positive) {
33 int end_i = vec.size() - 1;
34 while(end_i >= 0 && vec[end_i] == 0) {
35 end_i--;
36 }
37 this->vec = vector<unsigned short>();
38 for(int i = 0; i <= end_i; i++) {
39 this->vec.push_back(vec[i]);
40 }
41 if(this->vec.empty()) {
42 this->vec.push_back(0);
43 }
44}
BigInt::positive
bool positive
Definition: templates.h:25
BigInt::vec
vector< unsigned short > vec
Definition: templates.h:26

引用了 vec.

◆ BigInt() [2/13]

BigInt::BigInt ( short  n)

在文件 templates.cpp 第 46 行定义.

46 {
47 if(n < 0) {
48 positive = false;
49 n = -n;
50 }
51 vec = vector<unsigned short>();
52 stringstream ss;
53 ss << n;
54 char ch;
55 while(ss >> ch) {
56 vec.push_back(ch - '0');
57 }
58}

引用了 positive , 以及 vec.

◆ BigInt() [3/13]

BigInt::BigInt ( int  n)

在文件 templates.cpp 第 60 行定义.

60 {
61 if(n < 0) {
62 positive = false;
63 n = -n;
64 }
65 vec = vector<unsigned short>();
66 stringstream ss;
67 ss << n;
68 char ch;
69 while(ss >> ch) {
70 vec.push_back(ch - '0');
71 }
72}

引用了 positive , 以及 vec.

◆ BigInt() [4/13]

BigInt::BigInt ( long  n)

在文件 templates.cpp 第 74 行定义.

74 {
75 if(n < 0) {
76 positive = false;
77 n = -n;
78 }
79 vec = vector<unsigned short>();
80 stringstream ss;
81 ss << n;
82 char ch;
83 while(ss >> ch) {
84 vec.push_back(ch - '0');
85 }
86}

引用了 positive , 以及 vec.

◆ BigInt() [5/13]

BigInt::BigInt ( long long  n)

◆ BigInt() [6/13]

BigInt::BigInt ( unsigned short  n)

在文件 templates.cpp 第 100 行定义.

100 {
101 vec = vector<unsigned short>();
102 do {
103 vec.push_back(n % 10);
104 n /= 10;
105 } while(n != 0);
106}

引用了 vec.

◆ BigInt() [7/13]

BigInt::BigInt ( unsigned int  n)

在文件 templates.cpp 第 108 行定义.

108 {
109 vec = vector<unsigned short>();
110 do {
111 vec.push_back(n % 10);
112 n /= 10;
113 } while(n != 0);
114}

引用了 vec.

◆ BigInt() [8/13]

BigInt::BigInt ( unsigned long  n)

在文件 templates.cpp 第 116 行定义.

116 {
117 vec = vector<unsigned short>();
118 do {
119 vec.push_back(n % 10);
120 n /= 10;
121 } while(n != 0);
122}

引用了 vec.

◆ BigInt() [9/13]

BigInt::BigInt ( unsigned long long  n)

◆ BigInt() [10/13]

BigInt::BigInt ( const string &  str)

在文件 templates.cpp 第 132 行定义.

132 {
133 int start_i = str.length() - 1;
134 while(start_i >= 0 && isdigit(str[start_i]) != 0) {
135 vec.push_back(str[start_i] - '0');
136 start_i--;
137 }
138 if(str[0] == '-') {
139 positive = false;
140 }
141}

引用了 positive , 以及 vec.

◆ BigInt() [11/13]

BigInt::BigInt ( const char *  str)

在文件 templates.cpp 第 143 行定义.

143 {
144 int start_i = strlen(str) - 1;
145 while(start_i >= 0 && isdigit(str[start_i]) != 0) {
146 vec.push_back(str[start_i] - '0');
147 start_i--;
148 }
149 if(str[0] == '-') {
150 positive = false;
151 }
152}

引用了 positive , 以及 vec.

◆ BigInt() [12/13]

BigInt::BigInt ( const BigInt &  bi)

在文件 templates.cpp 第 154 行定义.

154 {
155 int end_i = bi.vec.size() - 1;
156 while(end_i >= 0 && bi.vec[end_i] == 0) {
157 end_i--;
158 }
159 this->vec = vector<unsigned short>();
160 for(int i = 0; i <= end_i; i++) {
161 this->vec.push_back(bi.vec[i]);
162 }
163 if(this->vec.empty()) {
164 this->vec.push_back(0);
165 }
166 this->positive = bi.positive;
167}

引用了 positive , 以及 vec.

◆ BigInt() [13/13]

BigInt::BigInt ( )

在文件 templates.cpp 第 384 行定义.

384 {
385 vec = vector<unsigned short>();
386 positive = true;
387}

引用了 positive , 以及 vec.

被这些函数引用 operator*(), operator+(), operator++(), operator-() , 以及 operator--().

成员函数说明

◆ get_size()

unsigned long BigInt::get_size ( ) const
private

在文件 templates.cpp 第 27 行定义.

27{ return vec.size(); }

引用了 vec.

被这些函数引用 operator+(), operator-(), operator<() , 以及 operator>().

◆ operator!=()

bool BigInt::operator!= ( const BigInt &  bi) const

在文件 templates.cpp 第 313 行定义.

313 {
314 if(this->positive == bi.positive) {
315 return this->vec != bi.vec;
316 }
317 return true;
318}

引用了 positive , 以及 vec.

◆ operator%()

BigInt BigInt::operator% ( const BigInt &  bi) const

在文件 templates.cpp 第 266 行定义.

266{ return *this; }

◆ operator%=()

BigInt & BigInt::operator%= ( const BigInt &  bi)

在文件 templates.cpp 第 344 行定义.

344 {
345 *this = *this % bi;
346 return *this;
347}

◆ operator*() [1/2]

BigInt BigInt::operator* ( const BigInt &  bi) const

在文件 templates.cpp 第 235 行定义.

235 {
236 unsigned max_len = 0;
237 vector<vector<unsigned short>> vecs(bi.vec.size());
238 for(int i = 0; i < bi.vec.size(); i++) {
239 vector<unsigned short> vi(i, 0);
240 vector<unsigned short> ai = *this * bi.vec[i];
241 vi.insert(vi.end(), ai.begin(), ai.end());
242 vecs[i] = vi;
243 max_len = max(max_len, static_cast<unsigned>(vi.size()));
244 }
245 vector<unsigned short> ans;
246 unsigned short c = 0;
247 for(int i = 0; i < max_len; i++) {
248 unsigned int v = 0;
249 for(int j = 0; j < vecs.size(); j++) {
250 v += i < vecs[j].size() ? vecs[j][i] : 0;
251 }
252 v += c;
253 c = v / 10;
254 v %= 10;
255 ans.emplace_back(v);
256 }
257 while(c > 0) {
258 ans.emplace_back(c % 10);
259 c /= 10;
260 }
261 return BigInt(ans, (*this).positive == bi.positive);
262}

引用了 BigInt(), positive , 以及 vec.

◆ operator*() [2/2]

vector< unsigned short > BigInt::operator* ( unsigned short  n) const
private

在文件 templates.cpp 第 219 行定义.

219 {
220 vector<unsigned short> res;
221 unsigned short c = 0;
222 for(const auto v: this->vec) {
223 unsigned short num = n * v + c;
224 c = num / 10;
225 num %= 10;
226 res.emplace_back(num);
227 }
228 while(c > 0) {
229 res.emplace_back(c % 10);
230 c /= 10;
231 }
232 return res;
233}

引用了 vec.

◆ operator*=()

BigInt & BigInt::operator*= ( const BigInt &  bi)

在文件 templates.cpp 第 334 行定义.

334 {
335 *this = *this * bi;
336 return *this;
337}

◆ operator+()

BigInt BigInt::operator+ ( const BigInt &  bi) const

在文件 templates.cpp 第 169 行定义.

169 {
170 if(this->positive && !bi.positive) {
171 return *this - -bi;
172 }
173 if(!this->positive && bi.positive) {
174 return bi - -*this;
175 }
176 vector<unsigned short> v;
177 unsigned short carry = 0;
178 for(long long i = 0; i < max(this->get_size(), bi.get_size()) || carry != 0; i++) {
179 const unsigned short this_num = i < this->get_size() ? (*this)[i] : 0;
180 const unsigned short bi_num = i < bi.get_size() ? bi[i] : 0;
181 unsigned short sum = this_num + bi_num;
182 sum += carry;
183 carry = sum / 10;
184 sum %= 10;
185 v.push_back(sum);
186 }
187 auto ret = BigInt(v, this->positive);
188 return ret;
189}
BigInt::get_size
unsigned long get_size() const
Definition: templates.cpp:27

引用了 BigInt(), get_size() , 以及 positive.

◆ operator++() [1/2]

BigInt & BigInt::operator++ ( )

在文件 templates.cpp 第 363 行定义.

363 {
364 *this += 1;
365 return *this;
366}

◆ operator++() [2/2]

BigInt BigInt::operator++ ( int  )

在文件 templates.cpp 第 373 行定义.

373 {
374 auto ret = BigInt(*this);
375 *this += 1;
376 return ret;
377}

引用了 BigInt().

◆ operator+=()

BigInt & BigInt::operator+= ( const BigInt &  bi)

在文件 templates.cpp 第 324 行定义.

324 {
325 *this = *this + bi;
326 return *this;
327}

◆ operator-() [1/2]

BigInt BigInt::operator- ( ) const

在文件 templates.cpp 第 361 行定义.

361{ return BigInt(this->vec, !this->positive); }

引用了 BigInt(), positive , 以及 vec.

◆ operator-() [2/2]

BigInt BigInt::operator- ( const BigInt &  bi) const

在文件 templates.cpp 第 191 行定义.

191 {
192 if(this->positive != bi.positive) {
193 return *this + -bi;
194 }
195 if(!this->positive) {
196 return -bi - -*this;
197 }
198 if(*this < bi) {
199 return -(bi - *this);
200 }
201 vector<unsigned short> v;
202 unsigned short borrow = 0;
203 for(long long i = 0; i < max(this->get_size(), bi.get_size()); i++) {
204 short this_num = i < this->get_size() ? (*this)[i] : 0;
205 const short bi_num = i < bi.get_size() ? bi[i] : 0;
206 this_num -= borrow;
207 short diff = this_num - bi_num;
208 borrow = 0;
209 while(diff < 0) {
210 borrow++;
211 diff += 10;
212 }
213 v.push_back(diff);
214 }
215 auto ret = BigInt(v, true);
216 return ret;
217}

引用了 BigInt(), get_size() , 以及 positive.

◆ operator--() [1/2]

BigInt & BigInt::operator-- ( )

在文件 templates.cpp 第 368 行定义.

368 {
369 *this -= 1;
370 return *this;
371}

◆ operator--() [2/2]

BigInt BigInt::operator-- ( int  )

在文件 templates.cpp 第 379 行定义.

379 {
380 auto ret = BigInt(*this);
381 *this -= 1;
382 return ret;
383}

引用了 BigInt().

◆ operator-=()

BigInt & BigInt::operator-= ( const BigInt &  bi)

在文件 templates.cpp 第 329 行定义.

329 {
330 *this = *this - bi;
331 return *this;
332}

◆ operator/()

BigInt BigInt::operator/ ( const BigInt &  bi) const

在文件 templates.cpp 第 264 行定义.

264{ return *this; }

◆ operator/=()

BigInt & BigInt::operator/= ( const BigInt &  bi)

在文件 templates.cpp 第 339 行定义.

339 {
340 *this = *this / bi;
341 return *this;
342}

◆ operator<()

bool BigInt::operator< ( const BigInt &  bi) const

在文件 templates.cpp 第 293 行定义.

293 {
294 if(this->positive != bi.positive) {
295 return !this->positive;
296 }
297 if(!this->positive && !bi.positive) {
298 return -*this > -bi;
299 }
300 if(this->get_size() != bi.get_size()) {
301 return this->get_size() < bi.get_size();
302 }
303 return !(*this >= bi);
304}

引用了 get_size() , 以及 positive.

◆ operator<=()

bool BigInt::operator<= ( const BigInt &  bi) const

在文件 templates.cpp 第 322 行定义.

322{ return *this == bi || *this < bi; }

◆ operator==()

bool BigInt::operator== ( const BigInt &  bi) const

在文件 templates.cpp 第 306 行定义.

306 {
307 if(this->positive == bi.positive) {
308 return this->vec == bi.vec;
309 }
310 return false;
311}

引用了 positive , 以及 vec.

◆ operator>()

bool BigInt::operator> ( const BigInt &  bi) const

在文件 templates.cpp 第 268 行定义.

268 {
269 if(this->positive != bi.positive) {
270 return this->positive;
271 }
272 if(!this->positive && !bi.positive) {
273 return -*this < -bi;
274 }
275 if(this->get_size() != bi.get_size()) {
276 return this->get_size() > bi.get_size();
277 }
278
279 for(int i = get_size() - 1; i >= 0; --i) {
280 if((*this)[i] > bi[i]) {
281 return true;
282 }
283 if((*this)[i] < bi[i]) {
284 return false;
285 }
286 if((*this)[i] < bi[i]) {
287 return false;
288 }
289 }
290 return false;
291}

引用了 get_size() , 以及 positive.

◆ operator>=()

bool BigInt::operator>= ( const BigInt &  bi) const

在文件 templates.cpp 第 320 行定义.

320{ return *this == bi || *this > bi; }

◆ operator[]()

unsigned short BigInt::operator[] ( unsigned long  i) const
private

在文件 templates.cpp 第 29 行定义.

29{ return vec[i]; }

引用了 vec.

友元及相关函数文档

◆ operator<<

ostream & operator<< ( ostream &  os,
const BigInt &  bi 
)
friend

在文件 templates.cpp 第 349 行定义.

349 {
350 if(!bi.positive) {
351 os << '-';
352 }
353 for(auto it = bi.vec.rbegin(); it != bi.vec.rend(); ++it) {
354 os << *it;
355 }
356 return os;
357}

◆ operator>>

istream & operator>> ( istream &  is,
const BigInt &   
)
friend

在文件 templates.cpp 第 359 行定义.

359{ return is; }

类成员变量说明

◆ positive

bool BigInt::positive = true
private

在文件 templates.h 第 25 行定义.

被这些函数引用 BigInt(), operator!=(), operator*(), operator+(), operator-(), operator<(), operator==() , 以及 operator>().

◆ vec

vector<unsigned short> BigInt::vec = {}
private

在文件 templates.h 第 26 行定义.

被这些函数引用 BigInt(), get_size(), operator!=(), operator*(), operator-(), operator==() , 以及 operator[]().

该类的文档由以下文件生成:
制作者 doxygen 1.9.2