fork download 
  1. #include <algorithm>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <memory>
  5. #include <string>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. class UBigInt {
  11. public:
  12.     UBigInt(const shared_ptr<vector<bool> >& bits);
  13. 	UBigInt(const unsigned long& val = 0);
  14. 	UBigInt operator +(const UBigInt& ade) const;
  15. 	UBigInt operator -(const UBigInt& sub) const;
  16. 	UBigInt operator *(const UBigInt& mer) const;
  17. 	UBigInt operator /(const UBigInt& dsr) const;
  18. 	UBigInt operator %(const UBigInt& dsr) const;
  19. 	UBigInt operator <<(const size_t& wid) const;
  20. 	UBigInt operator >>(const size_t& wid) const;
  21. 	UBigInt& operator =(const UBigInt& num);
  22. 	UBigInt& operator +=(const UBigInt& ade);
  23. 	UBigInt& operator -=(const UBigInt& sub);
  24. 	UBigInt& operator *=(const UBigInt& mer);
  25. 	UBigInt& operator /=(const UBigInt& dsr);
  26. 	UBigInt& operator %=(const UBigInt& dsr);
  27. 	UBigInt& operator <<=(const size_t& wid);
  28. 	UBigInt& operator >>=(const size_t& wid);
  29. 	bool operator ==(const UBigInt& num) const;
  30. 	bool operator <(const UBigInt& num) const;
  31. 	bool operator >(const UBigInt& num) const;
  32. 	bool operator !=(const UBigInt& num) const;
  33. 	bool operator <=(const UBigInt& num) const;
  34. 	bool operator >=(const UBigInt& num) const;
  35. 	bool isZero() const;
  36. 	unsigned long getLowULong() const;
  37. 	string toString(const unsigned int& base = 10) const;
  38. 	static UBigInt fromString(const string& str, const unsigned int& base = 10);
  39. protected:
  40. 	shared_ptr<vector<bool> > bits;
  41. 	static shared_ptr<vector<bool> > makeBits(const unsigned long& val);
  42. 	static shared_ptr<vector<bool> > add(const shared_ptr<vector<bool> >& age, const shared_ptr<vector<bool> >& ade);
  43. 	static shared_ptr<vector<bool> > subtract(const shared_ptr<vector<bool> >& min, const shared_ptr<vector<bool> >& sub);
  44. 	static shared_ptr<vector<bool> > multiply(const shared_ptr<vector<bool> >& mca, const shared_ptr<vector<bool> >& mer);
  45. 	static shared_ptr<vector<bool> > divide(const shared_ptr<vector<bool> >& dde, const shared_ptr<vector<bool> >& dsr, shared_ptr<vector<bool> >* mod = NULL);
  46. 	static shared_ptr<vector<bool> > leftShift(const shared_ptr<vector<bool> >& bits, const size_t& wid);
  47. 	static shared_ptr<vector<bool> > rightShift(const shared_ptr<vector<bool> >& bits, const size_t& wid);
  48. 	static bool less(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right);
  49. 	static bool equal(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right);
  50. 	static bool isZero(const shared_ptr<vector<bool> >& bits);
  51. 	static unsigned long getLowULong(const shared_ptr<vector<bool> >& bits);
  52. 	static unsigned int charToFigure(const char& ch);
  53. 	static char figureToChar(const unsigned int& fig);
  54. 	static shared_ptr<vector<bool> > trim(const shared_ptr<vector<bool> >& bits);
  55. };
  56.  
  57. #define ASSERT(pred) assert(#pred, pred);
  58.  
  59. void assert(const char* pred_str, const bool& pred);
  60.  
  61. UBigInt::UBigInt(const shared_ptr<vector<bool> >& bits) : bits(bits) {}
  62.  
  63. UBigInt::UBigInt(const unsigned long& val) : bits(makeBits(val)) {}
  64.  
  65. UBigInt UBigInt::operator +(const UBigInt& ade) const {
  66. 	return UBigInt(add(this->bits, ade.bits));
  67. }
  68.  
  69. UBigInt UBigInt::operator -(const UBigInt& sub) const {
  70. 	return UBigInt(subtract(this->bits, sub.bits));
  71. }
  72.  
  73. UBigInt UBigInt::operator *(const UBigInt& mer) const {
  74. 	return UBigInt(multiply(this->bits, mer.bits));
  75. }
  76.  
  77. UBigInt UBigInt::operator /(const UBigInt& dsr) const {
  78. 	return UBigInt(divide(this->bits, dsr.bits));
  79. }
  80.  
  81. UBigInt UBigInt::operator %(const UBigInt& dsr) const {
  82. 	shared_ptr<vector<bool> > mod;
  83. 	divide(this->bits, dsr.bits, &mod);
  84. 	return UBigInt(mod);
  85. }
  86.  
  87. UBigInt UBigInt::operator <<(const size_t& wid) const {
  88. 	return UBigInt(leftShift(this->bits, wid));
  89. }
  90.  
  91. UBigInt UBigInt::operator >>(const size_t& wid) const {
  92. 	return UBigInt(rightShift(this->bits, wid));
  93. }
  94.  
  95. UBigInt& UBigInt::operator =(const UBigInt& num) {
  96. 	this->bits = shared_ptr<vector<bool> >(new vector<bool>(*num.bits));
  97. 	return *this;
  98. }
  99.  
  100. UBigInt& UBigInt::operator +=(const UBigInt& add) {
  101. 	return *this = *this + add;
  102. }
  103.  
  104. UBigInt& UBigInt::operator -=(const UBigInt& sub) {
  105. 	return *this = *this - sub;
  106. }
  107.  
  108. UBigInt& UBigInt::operator *=(const UBigInt& mer) {
  109. 	return *this = *this * mer;
  110. }
  111.  
  112. UBigInt& UBigInt::operator /=(const UBigInt& dsr) {
  113. 	return *this = *this / dsr;
  114. }
  115.  
  116. UBigInt& UBigInt::operator %=(const UBigInt& dsr) {
  117. 	return *this = *this % dsr;
  118. }
  119.  
  120. UBigInt& UBigInt::operator <<=(const size_t& wid) {
  121. 	return *this = *this << wid;
  122. }
  123.  
  124. UBigInt& UBigInt::operator >>=(const size_t& wid) {
  125. 	return *this = *this >> wid;
  126. }
  127.  
  128. bool UBigInt::operator ==(const UBigInt& num) const {
  129. 	return equal(this->bits, num.bits);
  130. }
  131.  
  132. bool UBigInt::operator <(const UBigInt& num) const {
  133. 	return less(this->bits, num.bits);
  134. }
  135.  
  136. bool UBigInt::operator >(const UBigInt& num) const {
  137. 	return !equal(this->bits, num.bits) && !less(this->bits, num.bits);
  138. }
  139.  
  140. bool UBigInt::operator !=(const UBigInt& num) const {
  141. 	return !equal(this->bits, num.bits);
  142. }
  143.  
  144. bool UBigInt::operator <=(const UBigInt& num) const {
  145. 	return equal(this->bits, num.bits) || less(this->bits, num.bits);
  146. }
  147.  
  148. bool UBigInt::operator >=(const UBigInt& num) const {
  149. 	return !less(this->bits, num.bits);
  150. }
  151.  
  152. bool UBigInt::isZero() const {
  153. 	return isZero(this->bits);
  154. }
  155.  
  156. unsigned long UBigInt::getLowULong() const {
  157. 	return getLowULong(this->bits);
  158. }
  159.  
  160. string UBigInt::toString(const unsigned int& base) const {
  161. 	string res;
  162. 	shared_ptr<vector<bool> > wrk = this->bits;
  163. 	shared_ptr<vector<bool> > base_bits(makeBits(base));
  164. 	while (!isZero(wrk)) {
  165. 		shared_ptr<vector<bool> > mod;
  166. 		wrk = divide(wrk, base_bits, &mod);
  167. 		res += figureToChar(getLowULong(mod));
  168. 	}
  169. 	if (res.empty()) res += '0';
  170. 	reverse(res.begin(), res.end());
  171. 	return res;
  172. }
  173.  
  174. UBigInt UBigInt::fromString(const string& str, const unsigned int& base) {
  175. 	shared_ptr<vector<bool> > bits(makeBits(0));
  176. 	shared_ptr<vector<bool> > base_bits(makeBits(base));
  177. 	for (string::const_iterator iter = str.begin(); iter != str.end(); iter++) {
  178. 		if (iter != str.begin()) bits = multiply(bits, base_bits);
  179. 		unsigned int fig = charToFigure(*iter);
  180. 		if (fig >= base) throw string("値が範囲を逸脱している。");
  181. 		bits = add(bits, makeBits(fig));
  182. 	}
  183. 	return UBigInt(bits);
  184. }
  185.  
  186. shared_ptr<vector<bool> > UBigInt::makeBits(const unsigned long& val) {
  187. 	shared_ptr<vector<bool> > res(new vector<bool>);
  188. 	for (int i = 31; i >= 0; i--) {
  189. 		if ((val >> i) & 1) res->push_back(true);
  190. 		else if (!res->empty()) res->push_back(false);
  191. 	}
  192. 	if (res->empty()) res->push_back(false);
  193. 	return res;
  194. }
  195.  
  196. shared_ptr<vector<bool> > UBigInt::add(const shared_ptr<vector<bool> >& age, const shared_ptr<vector<bool> >& ade) {
  197. 	shared_ptr<vector<bool> > sum(new vector<bool>);
  198. 	vector<bool>::const_reverse_iterator age_iter = age->rbegin();
  199. 	vector<bool>::const_reverse_iterator ade_iter = ade->rbegin();
  200. 	bool carry = false;
  201. 	while (age_iter != age->rend() || ade_iter != ade->rend()) {
  202. 		int age_val = age_iter != age->rend() ? int(*age_iter) : 0;
  203. 		int ade_val = ade_iter != ade->rend() ? int(*ade_iter) : 0;
  204. 		int sum_val = age_val + ade_val + int(carry);
  205. 		carry = sum_val > 1;
  206. 		if (carry) sum_val -= 2;
  207. 		sum->push_back(sum_val == 1);
  208. 		if (age_iter != age->rend()) age_iter++;
  209. 		if (ade_iter != ade->rend()) ade_iter++;
  210. 	}
  211. 	if (carry) sum->push_back(true);
  212. 	if (sum->empty()) sum->push_back(false);
  213. 	reverse(sum->begin(), sum->end());
  214. 	return sum;
  215. }
  216.  
  217. shared_ptr<vector<bool> > UBigInt::subtract(const shared_ptr<vector<bool> >& min, const shared_ptr<vector<bool> >& sub) {
  218. 	shared_ptr<vector<bool> > dif(new vector<bool>);
  219. 	vector<bool>::const_reverse_iterator min_iter = min->rbegin();
  220. 	vector<bool>::const_reverse_iterator sub_iter = sub->rbegin();
  221. 	bool borrow = false;
  222. 	while (min_iter != min->rend() || sub_iter != sub->rend()) {
  223. 		int min_val = min_iter != min->rend() ? int(*min_iter) : 0;
  224. 		int sub_val = sub_iter != sub->rend() ? int(*sub_iter) : 0;
  225. 		int dif_val = min_val - sub_val - int(borrow);
  226. 		borrow = dif_val < 0;
  227. 		if (borrow) dif_val += 2;
  228. 		dif->push_back(dif_val == 1);
  229. 		if (min_iter != min->rend()) min_iter++;
  230. 		if (sub_iter != sub->rend()) sub_iter++;
  231. 	}
  232. 	if (borrow) throw string("被減数が減数より小さい。");
  233. 	reverse(dif->begin(), dif->end());
  234. 	return trim(dif);
  235. }
  236.  
  237. shared_ptr<vector<bool> > UBigInt::multiply(const shared_ptr<vector<bool> >& mca, const shared_ptr<vector<bool> >& mer) {
  238. 	shared_ptr<vector<bool> > pro(makeBits(0));
  239. 	vector<bool>::const_reverse_iterator mer_iter = mer->rbegin();
  240. 	size_t wid = 0;
  241. 	while (mer_iter != mer->rend()) {
  242. 		if (*mer_iter) pro = add(pro, leftShift(mca, wid));
  243. 		mer_iter++;
  244. 		wid++;
  245. 	}
  246. 	return pro;
  247. }
  248.  
  249. shared_ptr<vector<bool> > UBigInt::divide(const shared_ptr<vector<bool> >& dde, const shared_ptr<vector<bool> >& dsr, shared_ptr<vector<bool> >* mod) {
  250. 	if (isZero(dsr)) throw string("ゼロ除算エラー。");
  251. 	shared_ptr<vector<bool> > quo(new vector<bool>);
  252. 	shared_ptr<vector<bool> > fld(new vector<bool>);
  253. 	for (vector<bool>::const_iterator dde_iter = dde->begin(); dde_iter != dde->end(); dde_iter++) {
  254. 		fld->push_back(*dde_iter);
  255. 		fld = trim(fld);
  256. 		if (!less(fld, dsr)) {
  257. 			quo->push_back(true);
  258. 			fld = subtract(fld, dsr);
  259. 		}
  260. 		else if (!quo->empty()) quo->push_back(false);
  261. 	}
  262. 	if (quo->empty()) quo->push_back(false);
  263. 	if (mod) *mod = fld;
  264. 	return quo;
  265. }
  266.  
  267. shared_ptr<vector<bool> > UBigInt::leftShift(const shared_ptr<vector<bool> >& bits, const size_t& wid) {
  268. 	shared_ptr<vector<bool> > res(new vector<bool>(*bits));
  269. 	for (int i = 0; i < wid; i++) res->push_back(false);
  270. 	return res;
  271. }
  272.  
  273. shared_ptr<vector<bool> > UBigInt::rightShift(const shared_ptr<vector<bool> >& bits, const size_t& wid) {
  274. 	return shared_ptr<vector<bool> >(new vector<bool>(bits->begin(), bits->end() - wid));
  275. }
  276.  
  277. bool UBigInt::equal(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right) {
  278. 	bool res;
  279. 	if (left->size() != right->size()) res = false;
  280. 	else {
  281. 		vector<bool>::const_iterator left_iter = left->begin();
  282. 		vector<bool>::const_iterator right_iter = right->begin();
  283. 		for (;;) {
  284. 			if (left_iter == left->end()) {
  285. 				res = true;
  286. 				break;
  287. 			}
  288. 			else if (!*left_iter && *right_iter) {
  289. 				res = false;
  290. 				break;
  291. 			}
  292. 			else if (*left_iter && !*right_iter) {
  293. 				res = false;
  294. 				break;
  295. 			}
  296. 			left_iter++;
  297. 			right_iter++;
  298. 		}
  299. 	}
  300. 	return res;
  301. }
  302.  
  303. bool UBigInt::less(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right) {
  304. 	bool res;
  305. 	if (left->size() < right->size()) res = true;
  306. 	else if (left->size() > right->size()) res = false;
  307. 	else {
  308. 		vector<bool>::const_iterator left_iter = left->begin();
  309. 		vector<bool>::const_iterator right_iter = right->begin();
  310. 		for (;;) {
  311. 			if (left_iter == left->end()) {
  312. 				res = false;
  313. 				break;
  314. 			}
  315. 			else if (!*left_iter && *right_iter) {
  316. 				res = true;
  317. 				break;
  318. 			}
  319. 			else if (*left_iter && !*right_iter) {
  320. 				res = false;
  321. 				break;
  322. 			}
  323. 			left_iter++;
  324. 			right_iter++;
  325. 		}
  326. 	}
  327. 	return res;
  328. }
  329.  
  330. bool UBigInt::isZero(const shared_ptr<vector<bool> >& bits) {
  331. 	return bits->size() == 1 && bits->front() == false;
  332. }
  333.  
  334. unsigned long UBigInt::getLowULong(const shared_ptr<vector<bool> >& bits) {
  335. 	unsigned long res = 0;
  336. 	vector<bool>::const_iterator iter = bits->begin();
  337. 	for (int i = 0; i < 32; i++) {
  338. 		if (iter == bits->end()) break;
  339. 		if (i != 0) res <<= 1;
  340. 		res |= int(*iter);
  341. 		iter++;
  342. 	}
  343. 	return res;
  344. }
  345.  
  346. unsigned int UBigInt::charToFigure(const char& ch) {
  347. 	unsigned int res;
  348. 	if (ch >= '0' && ch <= '9') res = ch - '0';
  349. 	else if (ch >= 'A' && ch <= 'Z') res = 10 + ch - 'A';
  350. 	else if (ch >= 'a' && ch <= 'z') res = 10 + ch - 'a';
  351. 	else throw string("文字が数ではない。");
  352. 	return res;
  353. }
  354.  
  355. char UBigInt::figureToChar(const unsigned int& fig) {
  356. 	char res;
  357. 	if (fig >= 0 && fig <= 9) res = '0' + fig;
  358. 	else if (fig >= 10 && fig <= 36) res = 'A' + (fig - 10);
  359. 	else throw string("値が範囲を逸脱している。");
  360. 	return res;
  361. }
  362.  
  363. shared_ptr<vector<bool> > UBigInt::trim(const shared_ptr<vector<bool> >& bits) {
  364. 	size_t pos = 0;
  365. 	while (pos != bits->size() && bits->at(pos) == false) pos++;
  366. 	if (pos == bits->size()) pos--;
  367. 	return shared_ptr<vector<bool> >(new vector<bool>(bits->begin() + pos, bits->end()));
  368. }
  369.  
  370. void assert(const char* pred_str, const bool& pred) {
  371. 	if (pred) {
  372. 		cout << "アサート成功: " << pred_str << endl;
  373. 	}
  374. 	else {
  375. 		cerr << "アサート失敗: " << pred_str << endl;
  376. 		exit(1);
  377. 	}
  378. }
  379.  
  380. int main() {
  381. 	try {
  382. 		ASSERT(UBigInt::fromString("107777896329") + UBigInt::fromString("744936075025") == UBigInt::fromString("1540169976256") - UBigInt::fromString("687456004902"))
  383. 		ASSERT(UBigInt::fromString("2") * UBigInt::fromString("11111") == UBigInt::fromString("66666") / UBigInt::fromString("3"))
  384. 		ASSERT(UBigInt::fromString("55555555123") % UBigInt::fromString("10000") == UBigInt::fromString("5123"))
  385. 		ASSERT(UBigInt::fromString("12345678901234567890") == UBigInt::fromString("12345678901234567890"))
  386. 		ASSERT(UBigInt::fromString("999999999") < UBigInt::fromString("1000000000"))
  387. 		ASSERT(UBigInt::fromString("1000000001") > UBigInt::fromString("1000000000"))
  388. 		ASSERT(UBigInt::fromString("789AbCdEf", 16) == UBigInt::fromString("32374509039"))
  389. 		ASSERT(UBigInt::fromString("789AbCdEf", 16) - UBigInt::fromString("32374509000") == UBigInt::fromString("39"))
  390. 		ASSERT(UBigInt::fromString("1A", 16) << 1 == UBigInt::fromString("34", 16))
  391. 		ASSERT(UBigInt::fromString("1A", 16) >> 2 == UBigInt::fromString("6", 16))
  392. 	}
  393. 	catch (const string& msg) {
  394. 		cerr << msg << endl;
  395. 		return 1;
  396. 	}
  397. 	return 0;
  398. }
  399.  
Success #stdin #stdout 0s 3056KB
comments (?)
stdin 
Standard input is empty
stdout 
アサート成功: UBigInt::fromString("107777896329") + UBigInt::fromString("744936075025") == UBigInt::fromString("1540169976256") - UBigInt::fromString("687456004902")
アサート成功: UBigInt::fromString("2") * UBigInt::fromString("11111") == UBigInt::fromString("66666") / UBigInt::fromString("3")
アサート成功: UBigInt::fromString("55555555123") % UBigInt::fromString("10000") == UBigInt::fromString("5123")
アサート成功: UBigInt::fromString("12345678901234567890") == UBigInt::fromString("12345678901234567890")
アサート成功: UBigInt::fromString("999999999") < UBigInt::fromString("1000000000")
アサート成功: UBigInt::fromString("1000000001") > UBigInt::fromString("1000000000")
アサート成功: UBigInt::fromString("789AbCdEf", 16) == UBigInt::fromString("32374509039")
アサート成功: UBigInt::fromString("789AbCdEf", 16) - UBigInt::fromString("32374509000") == UBigInt::fromString("39")
アサート成功: UBigInt::fromString("1A", 16) << 1 == UBigInt::fromString("34", 16)
アサート成功: UBigInt::fromString("1A", 16) >> 2 == UBigInt::fromString("6", 16)
https://ideone.com/0YnpAW
language:
C++14 (gcc 8.3)
created:
11 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!