socket/BigInt.hpp

#ifndef BIG_INT_HPP
#define BIG_INT_HPP
#include "semi_bitset.hpp"
#include <cstdlib>
#include <string>
#include <iostream>
#include <cassert>
template<size_t size = dynamic>
class BigInt{
private:
	int signum = 1;
	semi_bitset<size> bits;
public:
	inline BigInt() : bits(1){}
	inline BigInt(size_t _size, bool dummy) : bits(_size){
		
	}
	inline BigInt(int o) : BigInt(2,false){
		if(o < 0){signum = -1;o *= -1;}
		bits.data[bits.length() - 1] = (unsigned int)o;
	}
	inline BigInt(unsigned int o) : BigInt(2,false){
		bits.data[bits.length() - 1] = o;
	}
	inline BigInt(long long o) : BigInt(3,false){
		if(o < 0){signum = -1;o = 0ULL - o;}
		bits.data[bits.length() - 1] = (o & lower_half);
		bits.data[bits.length() - 2] = (o >> 32);
	}
	inline BigInt(unsigned long long o) : BigInt(3,false){
		bits.data[bits.length() - 1] = (o & lower_half);
		bits.data[bits.length() - 2] = (o >> 32);
	}
	template<std::size_t osize>
	inline BigInt<size> add(const BigInt<osize>& o)const{
		static_assert(size == osize);
		BigInt<size> ret;
		uint64_t carry = 0;
		for(size_t i = size - 1;i >= 0;i--){
			uint64_t res = (*this)[i] + o[i] + carry;
			carry = (res >> 32);
			ret[i] = res & lower_half;
			if(i == 0)break;
		}
		return ret;
	}
	template<size_t osize>
	inline BigInt<size + osize> mult(const BigInt<osize>& o)const{
		BigInt<size + osize> ret;
		uint64_t mat[size][size] = {0};
		uint64_t carry = 0;
		for(size_t i = 0;i < size;i++){
			for(size_t ih = size - 1;ih != ~(0ULL);ih--){
				mat[size - i - 1][ih] = (*this)[i] * o[ih] + carry;
				carry = mat[size - i - 1][ih] >> 32;
				mat[size - i - 1][ih] &= lower_half;
				if(ih == 0)break;
			}
		}
		for(size_t i = 0;i < size;i++){
			for(size_t ih = 0;ih < size + osize;ih++){
				std::cout << mat[i][ih] << " ";
			}
			std::cout << std::endl;
		}
		carry = 0;
		for(std::int64_t i = size - 1;i > -((std::int64_t)size);i--){
			uint64_t accum = 0;
			for(std::int64_t ih = 0;ih < size;ih++){
				accum += ((i + ih) >= size || (i + ih) < 0) ?  0 : mat[ih][i + ih];
			}
			accum += carry;
			ret[i + osize] = accum & lower_half;
			//std::cout << accum << " ";
			carry = accum >> 32;
			if(i == 0)break;
		}
		return ret;
	}
	
	inline BigInt<size> div(unsigned int o)const{
		uint64_t carry = 0;
		BigInt<size> ret;
		for(size_t i = 0;i < size;i++){
			uint64_t res = ((*this)[i] + (carry << 32)) / o;
			carry = (*this)[i] % o;
			ret[i] = res;
		}
		return ret;
	}
	inline unsigned int mod(unsigned int o)const{
		uint64_t carry = 0;
		for(size_t i = 0;i < size;i++){
			carry = (this->operator[](i) + (carry << 32)) % o;
		}
		return (unsigned int)(carry & lower_half);
	}
	inline std::uint64_t& operator[](size_t i){
		return bits.data[i];
	}
	
	inline const std::uint64_t& operator[](size_t i)const{
		return bits.data[i];
	}
	inline bool isZero()const{
		for(size_t i = 0;i < size;i++){
			if(this->operator[](i))return false;
		}
		return true;
	}
	
};
template<size_t osize>
inline std::ostream& operator<<(std::ostream& s, const BigInt<osize>& o){
	std::string a = "";
	BigInt<osize> dis = o;
	while(!dis.isZero()){
		a = std::to_string(dis.mod(10)) + a;
		dis = dis.div(10);
	}
	return s << a;
}
#endif