/* vim: ts=4 sw=4 sts=4 fenc=utf-8 ff=unix :
 * =============================================================================
 *  number
 *  Copyright (c)  2005 - 2009 kei-n
 *  URL : http://sys0tem.homelinux.com/
 * =============================================================================
 */
module sal.util.number;

import std.stdio;

public import std.conv;

/**
 * 指定された16進数文字を, int の値に変換します.
 * 変換に失敗した場合, -1 を返します.
 *
 * Params:
 *  c = 変換する文字
 * Return:
 *  変換後の文字
 */
public
int hexToNumber(in char c)
{
	if (('0' <= c) && (c <= '9'))
	{
		return c - '0';
	}
	if (('a' <= c) && (c <= 'f'))
	{
		return 10 + (c - 'a');
	}
	if (('A' <= c) && (c <= 'F'))
	{
		return 10 + (c - 'A');
	}
	return -1;
}
unittest
{
	string sL = "0123456789abcdef";
	string sC = "0123456789ABCDEF";
	for (int i = 0; i < sL.length; i++)
	{
		assert(hexToNumber(sL[i]) == i);
		assert(hexToNumber(sC[i]) == i);
	}
	assert(hexToNumber('x') == -1);
}


/**
 * 指定された8進数文字を, int の値に変換します.
 * 変換に失敗した場合, -1 を返します.
 *
 * Params:
 *  c = 変換する文字
 * Return:
 *  変換後の文字
 */
public
int octToNumber(in char c)
{
	if (('0' <= c) && (c <= '7'))
	{
		return c - '0';
	}
	return -1;
}
unittest
{
	string s = "01234567";
	for (int i = 0; i < s.length; i++)
	{
		assert(octToNumber(s[i]) == i);
	}
	assert(octToNumber('8') == -1);
}



/**
 * 任意精度整数.
 * 基本必要な場合にのみコピーが実施されます.
 */
struct bigint
{
	public:

	// =========================================================================
	//  各演算子オーバーロード
	// =========================================================================
	// 演算子 ~e	opCom		: 不正.
	// 演算子 *e	opStar		: 不正.
	// 演算子 e++	opPostInc	: e += 1 にて実装.
	// 演算子 e--	opPostDec	: e -= 1 にて実装.
	// 演算子 ~     opCat       : 不正.

	/**
	 * 演算子 +e.
	 *
	 * Return:
	 *  本オブジェクトの参照
	 */
	bigint opPos()
	{
		return this;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res;
		for (int i = 0; i < val.length; i++)
		{
			res = val[i];
			assert(+val[i] == cast(long)(+res));
		}
	}


	/**
	 * 演算子 -e.
	 *
	 * Return:
	 *  符号反転した値
	 */
	bigint opNeg()
	{	bigint result;
		result.sign   = -this.sign;
		result.values = this.values.dup;
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res;
		for (int i = 0; i < val.length; i++)
		{
			res = val[i];
			assert((-val[i]) == cast(long)(-res));
		}
	}


	/**
	 * cast(type).
	 *
	 * Return:
	 *  値
	 */
	long opCast()
	{
		return to!(long)();
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res;
		for (int i = 0; i < val.length; i++)
		{
			res = val[i];
			res    += long.max;
			val[i] += long.max;
			assert((val[i]) == cast(long)(res));
		}
	}


	/**
	 * 演算子 +.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opAdd(T)(T val)
	{	// += を利用
		bigint result;
		result = this;
		result.opAddAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				res  = tmp1 + tmp2;
				assert((val[i] + val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * 演算子 -.
	 *
	 * Params:
	 *  val = 被減算値
	 * Return:
	 *  演算結果
	 */
	bigint opSub(T)(T val)
	{	// -= を利用
		bigint result;
		result = this;
		result.opSubAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				res  = tmp1 - tmp2;
				assert((val[i] - val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * 演算子 *.
	 *
	 * Params:
	 *  val = 被乗算値
	 * Return:
	 *  演算結果
	 */
	bigint opMul(T)(T val)
	{	// *= を利用
		bigint result;
		result = this;
		result.opMulAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				res  = tmp1 * tmp2;
				assert((val[i] * val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * / オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opDiv(T)(T val)
	{	// /= を利用
		bigint result;
		result = this;
		result.opDivAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				if (tmp2 == 0)
				{	// / 0 はスキップ
					continue;
				}
				res  = tmp1 / tmp2;
				assert((val[i] / val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * % オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opMod(T)(T val)
	{	// %= を利用
		bigint result;
		result = this;
		result.opModAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				if (tmp2 == 0)
				{	// / 0 はスキップ
					continue;
				}
				res  = tmp1 % tmp2;
				assert((val[i] % val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * & オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opAnd(T)(T val)
	{
		bigint result;
		result = this;
		result.opAndAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				res  = tmp1 & tmp2;
				assert((val[i] & val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * | オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opOr(T)(T val)
	{
		bigint result;
		result = this;
		result.opOrAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				res  = tmp1 | tmp2;
				assert((val[i] | val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * ^ オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opXor(T)(T val)
	{
		bigint result;
		result = this;
		result.opXorAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				res  = tmp1 ^ tmp2;
				assert((val[i] ^ val[j]) == cast(long)(res));
			}
		}
	}


	/**
	 * << オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opShl(T)(T val)
	{
		bigint result;
		result = this;
		result.opShlAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res;
		for (int i = 0; i < val.length; i++)
		{
			res = val[i];
			for (int j = 0; j < 35; j++)
			{
				assert((val[i] << j) == cast(long) (res <<  j));
				assert((val[i] >> j) == cast(long) (res << -j));
			}
		}
	}


	/**
	 * >> オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opShr(T)(T val)
	{
		bigint result;
		result = this;
		result.opShrAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, int.min, int.max, long.min, long.max ];
		bigint res;
		for (int i = 0; i < val.length; i++)
		{
			res = val[i];
			for (int j = 0; j < 35; j++)
			{
				assert((val[i] >> j) == cast(long) (res >>  j));
				assert((val[i] << j) == cast(long) (res >> -j));
			}
		}
	}


	/**
	  TODO
	 * >>> オーバーロード.
	 *
	 * Return:
	 *  演算結果
	 */
	bigint opUShr(T)(T val)
	{
		bigint result;
		result = this;
		result.opUShrAssign(val);
		return result;
	}
	unittest
	{
		long[] val = [ 0L, /* int.min */, int.max, long.min, long.max ];
		long   tmp;
		bigint res;
		for (int i = 0; i < val.length; i++)
		{
			tmp = val[i];
			res = val[i];
			for (int j = 0; j < 35; j++)
			{
				assert((tmp >>> j) == cast(long) (res >>>  j));
				assert((tmp <<  j) == cast(long) (res >>> -j));
			}
		}
		int intVal = int.min;
		res = intVal;
		for (int j = 0; j < 32; j++)
		{
			assert((intVal >>> j) == cast(long) (res >>>  j));
		}
	}


	/**
	 * ==, != のオーバーロード.
	 *
	 * Params:
	 *  val = 比較する値
	 * Resturn:
	 *  true/false (一致/不一致)
	 */
	bool opEquals(T)(T val)
	{
		static if (__traits(isScalar, T))
		{
			bigint biVal;
			biVal = val;
			return opEquals(biVal);
		}
		else static if (is(T == bigint))
		{	// bigint
			if (this.sign != val.sign)
			{	// 符号不一致
				return false;
			}
			if (this.values.length != val.values.length)
			{	// 桁数不一致
				return false;
			}
			for (int i = 0; i < this.values.length; i++)
			{
				if (this.values[i] != val.values[i])
				{	// 異なる
					return false;
				}
			}
			return true;
		}
		else
		{
			return false;
		}
	}


	/**
	 * <, <=, >, >= のオーバーロード.
	 *
	 * Params:
	 *  val = 比較する値
	 * Resturn:
	 *  負/0/正 (<0 / =0 / >0)
	 */
	int opCmp(T)(T val)
	{
		bigint cmpVal = bigintRef(val);

		// 符号が異なる場合, 符号にて比較
		if (this.sign != cmpVal.sign)
		{
			return (this.sign - cmpVal.sign);
		}

		// 絶対値の比較結果に符号を掛ける.
		return (this.sign * opCmpABS(cmpVal));
	}
	unittest
	{
		long[] val = [ 0L, 0x12345, 0xFEDCA, int.min, int.max,
			0x1122334455, 0xFFEEDDCCAA, long.min, long.max ];
		bigint res, tmp1, tmp2;
		for (int i = 0; i < val.length; i++)
		{
			tmp1 = val[i];
			for (int j = 0; j < val.length; j++)
			{
				tmp2 = val[j];
				if (val[i] == val[j])
				{
					assert(tmp1 == tmp2);
					assert(tmp1 >= tmp2);
					assert(tmp1 <= tmp2);
				}
				else if (val[i] > val[j])
				{
					assert(tmp1 != tmp2);
					assert(tmp1 >  tmp2);
				}
				else
				{
					assert(tmp1 != tmp2);
					assert(tmp1 <  tmp2);
				}
			}
		}
	}


	/**
	 * = オーバーロード.
	 *
	 * Params:
	 *  val = 値
	 * Return:
	 *  自インスタンス
	 */
	bigint opAssign(T)(in T val)
	{
		setValue!(T)(val);
		return this;
	}
	unittest
	{
		bigint val;
		val = 0;
		assert(0 == cast(long)(val));
	}


	/**
	 * 演算子 +=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opAddAssign(T)(T val)
	{
		if (val == 0)
		{	// += 0 なら値は変化しない.
			return this;
		}
		if (this.sign == 0)
		{	// 現在の値が 0 なら += val の val 代入と同じ
			this = val;
			return this;
		}

		bigint addVal = bigintRef(val);
		if (this.sign == addVal.sign)
		{	// + 同士 or - 同士の加算, ※符号は変化なし
			addABS(this.values, addVal.values);
		}
		else
		{	// 異なる符合同士の加算. ※符号は絶対値が大きいものになる
			// 絶対値の大きいものから小さいものを引く
			if (opCmpABS(addVal) > 0)
			{	// |this| > |addVal|
				subABS(this.values, addVal.values);
			}
			else
			{	// |this| < |addVal|
				subABS_r(this.values, addVal.values);
				this.sign = addVal.sign;
			}
		}
		return this;
	}


	/**
	 * 演算子 -=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opSubAssign(T)(T val)
	{	// -= val は, += -val と同じ
		return opAddAssign(-val);
	}


	/**
	 * 演算子 *=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opMulAssign(T)(T val)
	{
		if ((this == 0) || (val == 0))
		{	// どちらか 0 なら 0
			this = 0;
			return this;
		}

		// 初期化
		bigint mulVal;
		mulVal      = val;
		this.sign   = cast(byte) (this.sign * mulVal.sign);

		//           a   b   c   d  <- mulVal
		//       *       x   y   z  <- this
		// -------------------------
		//          az  bz  cz  dz  <- (1)
		//      ay  by  cy  dy      <- (2)
		//  ax  bx  cx  dx          <- (3)
		// -------------------------
		//  r5  r4  r3  r2  r1  r0
		
		// 結果格納バッファ初期化 [Dの場合 0 で初期化される]
		ulong[] res = new ulong[this.values.length + mulVal.values.length];

		// 掛け算実施
		for (int i = 0; i < this.values.length; i++)
		{
			for (int j = 0; j < mulVal.values.length; j++)
			{
				res[i + j] += cast(ulong) this.values[i]
					        * cast(ulong) mulVal.values[j];
			}
		}

		// 繰り上がりを考慮して this.values に格納
		this.values  = null;
		this.values ~= cast(uint) res[0];
		for (int i = 1; i < res.length; i++)
		{
			res[i]      += res[i - 1] >>> BLOCK_BIT;
			this.values ~= cast(uint) res[i];
		}

		return this;
	}


	/**
	 * 演算子 /=.
	 * TODO : 現状 long 型までの計算のみ
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opDivAssign(T)(T val)
	{
		long divVal = cast(long)(val);
		long myVal  = cast(long)(this);
		myVal /= divVal;
		this = myVal;
		return this;
	}


	/**
	 * 演算子 %=.
	 * TODO : 現状 long 型までの計算のみ
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opModAssign(T)(T val)
	{
		long modVal = cast(long)(val);
		long myVal  = cast(long)(this);
		myVal %= modVal;
		this = myVal;
		return this;
	}


	/**
	 * 演算子 &=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opAndAssign(T)(T val)
	{
		bigint andVal;
		andVal = val;

		// 桁追加用の定義 [負なら all F を追加する]
		uint thisAddFigure   = 0;
		uint andValAddFigure = 0;

		// 2の補数表現に変換
		if (this.sign < 0)
		{
			thisAddFigure   = -1;
			this            = toBinaryComplement(this);
		}
		if (andVal.sign < 0)
		{
			andValAddFigure = -1;
			andVal          = toBinaryComplement(andVal);
		}

		// 桁あわせ
		if (this.values.length > andVal.values.length)
		{
			for (int i = andVal.values.length; i < this.values.length; i++)
			{
				andVal.values ~= andValAddFigure;
			}
		}
		else
		{
			for (int i = this.values.length; i < andVal.values.length; i++)
			{
				this.values ~= thisAddFigure;
			}
		}

		// and 処理
		for (int i = 0; i < this.values.length; i++)
		{
			this.values[i] &= andVal.values[i];
		}

		// 先頭 bit が立っている場合, 負の値に変換
		if ((this.values[$ - 1] & int.min) != 0)
		{
			this      = toBinaryComplement(this);
			this.sign = -1;
		}

		// 余分な桁削除 (AND により桁が減る可能性があるため)
		adjust(this.values);
		if ((this.values.length == 1) && (this.values[0] == 0))
		{
			this.sign = 0;
		}
		return this;
	}


	/**
	 * 演算子 |=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opOrAssign(T)(T val)
	{
		bigint orVal;
		orVal = val;

		// 桁追加用の定義 [負なら all F を追加する]
		uint thisAddFigure   = 0;
		uint orValAddFigure  = 0;

		// 2の補数表現に変換
		if (this.sign < 0)
		{
			thisAddFigure   = -1;
			this            = toBinaryComplement(this);
		}
		if (orVal.sign < 0)
		{
			orValAddFigure = -1;
			orVal          = toBinaryComplement(orVal);
		}

		// 桁あわせ
		if (this.values.length > orVal.values.length)
		{
			for (int i = orVal.values.length; i < this.values.length; i++)
			{
				orVal.values ~= orValAddFigure;
			}
		}
		else
		{
			for (int i = this.values.length; i < orVal.values.length; i++)
			{
				this.values ~= thisAddFigure;
			}
		}

		// or 処理
		for (int i = 0; i < this.values.length; i++)
		{
			this.values[i] |= orVal.values[i];
		}

		// 先頭 bit が立っている場合, 負の値に変換
		if ((this.values[$ - 1] & int.min) != 0)
		{
			this      = toBinaryComplement(this);
			this.sign = -1;
		}

		// 余分な桁削除
		adjust(this.values);
		if ((this.values.length == 1) && (this.values[0] == 0))
		{
			this.sign = 0;
		}
		return this;
	}


	/**
	 * 演算子 ^=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opXorAssign(T)(T val)
	{
		bigint xorVal;
		xorVal = val;

		// 桁追加用の定義 [負なら all F を追加する]
		uint thisAddFigure   = 0;
		uint xorValAddFigure  = 0;

		// 2の補数表現に変換
		if (this.sign < 0)
		{
			thisAddFigure   = -1;
			this            = toBinaryComplement(this);
		}
		if (xorVal.sign < 0)
		{
			xorValAddFigure = -1;
			xorVal          = toBinaryComplement(xorVal);
		}

		// 桁あわせ
		if (this.values.length > xorVal.values.length)
		{
			for (int i = xorVal.values.length; i < this.values.length; i++)
			{
				xorVal.values ~= xorValAddFigure;
			}
		}
		else
		{
			for (int i = this.values.length; i < xorVal.values.length; i++)
			{
				this.values ~= thisAddFigure;
			}
		}

		// xor 処理
		for (int i = 0; i < this.values.length; i++)
		{
			this.values[i] ^= xorVal.values[i];
		}

		// 先頭 bit が立っている場合, 負の値に変換
		if ((this.values[$ - 1] & int.min) != 0)
		{
			this      = toBinaryComplement(this);
			this.sign = -1;
		}

		// 余分な桁削除
		adjust(this.values);
		if ((this.values.length == 1) && (this.values[0] == 0))
		{
			this.sign = 0;
		}
		return this;
	}


	/**
	 * 演算子 <<=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opShlAssign(T)(T val)
	{
		int shiftVal;
		static if (__traits(isScalar, T))
		{	// 整数, 浮動小数
			shiftVal = cast(int) val;
		}
		else static if (is(T == bigint))
		{	// bigint
			shiftVal = (cast(int) val.values[0]) * this.sign;
		}
		else
		{
			static assert(false);
		}

		if (shiftVal == 0)
		{	// 0 なら何もしない
			return this;
		}
		if (shiftVal < 0)
		{	// 右シフト
			return opShrAssign(-shiftVal);
		}

		// 2の補数表現に変換
		uint thisAddFigure   = 0;
		if (this.sign < 0)
		{
			thisAddFigure = -1;
			this          = toBinaryComplement(this);
		}
		// 左シフトなので this の桁を 1 つ増やしておく
		this.values ~= thisAddFigure;

		// uint.sizeof * 8 を超えている分は, byte 単位で移動
		int byteShift = shiftVal / BLOCK_BIT;
		int bitShift  = shiftVal & (BLOCK_BIT - 1);
		int bitShiftR = BLOCK_BIT - bitShift;

		// 結果格納
		uint[] res = new uint[this.values.length + 1 + byteShift];

		// bit 単位シフト
		res[byteShift] = (this.values[0] << bitShift);
		int i = 1;
		for (; i < this.values.length; i++)
		{
			res[byteShift + i] = (this.values[i]     << bitShift)
							   | (this.values[i - 1] >> bitShiftR);
		}

		this.values = res;
		/* res を 1 つ分余分にとっており,
		 * 先頭 bit が立つ事はない.
		if ((this.values[$ - 1] & int.min) != 0)
		{
			this      = toBinaryComplement(this);
			this.sign = -1;
		}
		*/

		// 調整
		adjust(this.values);
		return this;
	}


	/**
	 * 演算子 >>=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opShrAssign(T)(T val)
	{
		int shiftVal;
		static if (__traits(isScalar, T))
		{	// 整数, 浮動小数
			shiftVal = cast(int) val;
		}
		else static if (is(T == bigint))
		{	// bigint
			shiftVal = (cast(int) val.values[0]) * this.sign;
		}
		else
		{
			static assert(false);
		}

		if (shiftVal == 0)
		{	// 0 なら何もしない
			return this;
		}
		if (shiftVal < 0)
		{	// 左シフト
			return opShlAssign(-shiftVal);
		}

		// 2の補数表現に変換
		uint thisAddFigure   = 0;
		if (this.sign < 0)
		{
			thisAddFigure = -1;
			this          = toBinaryComplement(this);
		}

		// uint.sizeof * 8 を超えている分は, byte 単位で移動
		int byteShift = shiftVal / BLOCK_BIT;
		int bitShift  = shiftVal & (BLOCK_BIT - 1);
		int bitShiftL = BLOCK_BIT - bitShift;

		// byteShift が現在の配列サイズを超える場合は -1 or 0
		if (byteShift >= this.values.length)
		{
			if (thisAddFigure == -1)
			{
				this.sign   = -1;
				this.values = [ 1 ];
			}
			else
			{
				this.sign   = 0;
				this.values = [ 0 ];
			}
			return this;
		}

		// 結果格納
		uint[] res   = new uint[this.values.length - byteShift];

		// bitShift なし
		if (bitShift == 0)
		{
			res = this.values[byteShift .. $];
		}
		else
		{
			// bit 単位シフト
			int i = 0;
			for (; i < (this.values.length - byteShift - 1); i++)
			{
				res[i] = (this.values[i + byteShift]     >> bitShift)
					   | (this.values[i + byteShift + 1] << bitShiftL);
			}
			res[i] = (this.values[i + byteShift] >> bitShift)
				   | (thisAddFigure << bitShiftL);
		}

		// 先頭 bit が立っている場合, 負の値に変換
		this.values = res;
		if ((this.values[$ - 1] & int.min) != 0)
		{
			this      = toBinaryComplement(this);
			this.sign = -1;
		}

		adjust(this.values);
		return this;
	}


	/**
	 * 演算子 >>>=.
	 *
	 * Params:
	 *  val = 被演算値
	 * Return:
	 *  演算結果
	 */
	bigint opUShrAssign(T)(T val)
	{
		int shiftVal;
		static if (__traits(isScalar, T))
		{	// 整数, 浮動小数
			shiftVal = cast(int) val;
		}
		else static if (is(T == bigint))
		{	// bigint
			shiftVal = (cast(int) val.values[0]) * this.sign;
		}
		else
		{
			static assert(false);
		}

		if (shiftVal == 0)
		{	// 0 なら何もしない
			return this;
		}
		if (shiftVal < 0)
		{	// 左シフト
			return opShlAssign(-shiftVal);
		}

		// 2の補数表現に変換
		if (this.sign < 0)
		{
			this = toBinaryComplement(this);
		}

		// uint.sizeof * 8 を超えている分は, byte 単位で移動
		int byteShift = shiftVal / BLOCK_BIT; 
		int bitShift  = shiftVal & (BLOCK_BIT - 1);
		int bitShiftL = BLOCK_BIT - bitShift;

		// byteShift が現在の配列サイズを超える場合は -1 or 0
		if (byteShift >= this.values.length)
		{
			this.sign   = 0;
			this.values = [ 0 ];
			return this;
		}

		// 結果格納
		uint[] res   = new uint[this.values.length - byteShift];

		// bitShift なし
		if (bitShift == 0)
		{
			res = this.values[byteShift .. $];
		}
		else
		{
			// bit 単位シフト
			int i = 0;
			for (; i < (this.values.length - byteShift - 1); i++)
			{
				res[i] = (this.values[i + byteShift]     >>> bitShift)
					   | (this.values[i + byteShift + 1] << bitShiftL);
			}
			res[i] = (this.values[i + byteShift] >>> bitShift);
		}

		this.values = res;
		adjust(this.values);
		return this;
	}


	/**
	 * この数値の絶対値を返します.
	 *
	 * Return:
	 *  絶対値
	 */
	bigint abs()
	{
		if (this.sign >= 0)
		{	// 正の値なら参照を返す.
			return this;
		}
		bigint absVal;
		absVal.sign   = -this.sign;
		absVal.values = this.values.dup;
		return absVal;
	}
	unittest
	{
		long[] val = [ 0, int.min, int.max ];
		bigint res;
		for (int i = 0; i < val.length; i++)
		{
			res = val[i];
			if (val[i] >= 0)
			{
				assert(cast(long) res.abs() == val[i]);
			}
			else
			{
				assert(cast(long) res.abs() == -val[i]);
			}
		}
	}


	/**
	 * 絶対値の比較を行います.
	 *
	 * Params:
	 *  val = 比較する値
	 * Resturn:
	 *  負/0/正 (<0 / =0 / >0)
	 */
	int opCmpABS(T)(T val)
	{
		bigint cmpVal = bigintRef(val);
		if (this.values.length != cmpVal.values.length)
		{	// 桁数が異なる
			return (this.values.length - cmpVal.values.length);
		}
		for (int i = (this.values.length - 1); i >= 0; i--)
		{	// 上位桁から比較
			if (this.values[i] != cmpVal.values[i])
			{	// 異なる
				return (this.values[i] - cmpVal.values[i]);
			}
		}
		return 0;
	}


	/**
	 * 数値変換.
	 *
	 * Return:
	 *  数値変換
	 */
	T to(T)()
	{
		static if (__traits(isScalar, T))
		{
			// ulong, long に変換
			static if (is(T == long) || is(T == ulong))
			{
				T val = this.values[0];
				if (this.values.length >= 2)
				{
					val  |= cast(ulong) this.values[1] << cast(ulong) BLOCK_BIT;
				}
				static if (is(T == long))
				{
					if (this.sign < 0)
					{
						val = -val;
					}
				}
				return val;
			}
			else
			{
				return cast(T) to!(long)();
			}
		}
		else
		{	// 以外
			static assert(false);
		}
	}
	unittest
	{
		// bigint val = new bigint(0x12);
		bigint val;
		val = 0x12;
		assert(0x12 == val.to!(ubyte));
		assert(0x12 == val.to!(ushort));
		assert(0x12 == val.to!(uint));
		assert(0x12 == val.to!(ulong));
		assert(0x12 == val.to!(byte));
		assert(0x12 == val.to!(short));
		assert(0x12 == val.to!(int));
		assert(0x12 == val.to!(long));
		assert(0x12 == val.to!(float));
		assert(0x12 == val.to!(double));
	}


	// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
	//  以下 private
	// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
	private:

	/**
	 * 2の補数表現に変換します.
	 *
	 * Params:
	 *  val = 変換する値
	 * Return:
	 *  変換後の値
	 */
	static
	bigint toBinaryComplement(T)(T val)
	{
		bigint biVal = bigintRef(val);

		// 符号反転
		biVal.sign = -biVal.sign;

		// bit 反転
		long carry = 1;
		for (int i = 0; i < biVal.values.length; i++)
		{
			biVal.values[i]  ^= -1;
			carry            += biVal.values[i];
			biVal.values[i]   = cast(uint) carry;
			carry           >>= BLOCK_BIT;
		}

		return biVal;
	}


	/**
	 * 指定された値の bigint 型参照を返します.
	 *
	 * [注意]
	 * 指定された値が bigint 型の場合, 参照をそのまま返します.
	 *
	 * Params:
	 *  val = 変換する値
	 * Return:
	 *  変換後の値
	 */
	static
	bigint bigintRef(T)(T val)
	{
		static if (__traits(isScalar, T))
		{	// 整数, 浮動小数なら変換
			bigint bigintVal;
			bigintVal = val;
			return bigintVal;
		}
		else static if (is(T == bigint))
		{	// 既に bitint ならそのまま
			return val;
		}
		else
		{
			static assert(false);
		}
	}


	/**
	 * val1 と val2 を加算し, 結果を val1 に格納します.
	 *
	 * Params:
	 *  val1 = 被加算値 & 結果格納用
	 *  val2 = 加算値
	 */
	static
	void addABS(ref uint[] val1, in uint[] val2)
	{
		ulong carry  = 0;
		int   i      = 0;

		if (val1.length < val2.length)
		{
			for (; i < val1.length; i++)
			{
				carry    += cast(ulong) val1[i] + cast(ulong) val2[i];
				val1[i]   = cast(uint) carry;
				carry   >>= BLOCK_BIT;
			}
			for (; i < val2.length; i++)
			{
				carry    += cast(ulong) val2[i];
				val1     ~= cast(uint) carry;
				carry   >>= BLOCK_BIT;
			}
		}
		else
		{
			for (; i < val2.length; i++)
			{
				carry    += cast(ulong) val1[i] + cast(ulong) val2[i];
				val1[i]   = cast(uint) carry;
				carry   >>= BLOCK_BIT;
			}
		}
		// 桁拡張
		if (carry > 0)
		{
			if (i < val1.length)
			{
				val1[i] += cast(uint) carry;
			}
			else
			{
				val1    ~= cast(uint) carry;
			}
		}
	}


	/**
	 * val1 - val2 を演算し, 結果を val1 に格納します.
	 *
	 * Params:
	 *  val1 = 被減算値 & 結果格納用
	 *  val2 = 減算値
	 */
	static
	void subABS(ref uint[] val1, in uint[] val2)
	{
		long carry = 0;
		int  i     = 0;
		for (; i < val2.length; i++)
		{
			carry    += cast(ulong) val1[i] - cast(ulong) val2[i];
			val1[i]   = cast(uint) carry;
			carry   >>= BLOCK_BIT;
		}
		for (; i < val1.length; i++)
		{
			carry    += cast(ulong) val1[i];
			val1[i]   = cast(uint) carry;
			carry   >>= BLOCK_BIT;
		}
		adjust(val1);
	}


	/**
	 * val2 - val1 を演算し, 結果を val1 に格納します.
	 *
	 * Params:
	 *  val1 = 被減算値 & 結果格納用
	 *  val2 = 減算値
	 */
	static
	void subABS_r(ref uint[] val1, in uint[] val2)
	{
		long carry = 0;
		int  i     = 0;
		for (; i < val1.length; i++)
		{
			carry    += cast(ulong) val2[i] - cast(ulong) val1[i];
			val1[i]   = cast(uint) carry;
			carry   >>= BLOCK_BIT;
		}
		for (; i < val2.length; i++)
		{
			carry    += cast(ulong) val2[i];
			val1     ~= cast(uint) carry;
			carry   >>= BLOCK_BIT;
		}
		adjust(val1);
	}


	/**
	 * 指定された値の余分な上位配列(値が0)を削除します.
	 *
	 * Params:
	 *  val = 調整する値
	 */
	static
	void adjust(ref uint[] val)
	{
		int len = val.length - 1;
		while ((len > 0) && (val[len] == 0))
		{
			len--;
		}
		val.length = len + 1;
	}


	/**
	 * 指定された値を設定します.
	 *
	 * Params:
	 *  val = 設定する値
	 */
	void setValue(T)(in T val)
	{
		// ----- 整数型の場合 -----
		static if (__traits(isIntegral, T))
		{	// 符号設定
			T tmpVal = val;
			if (val == 0)
			{
				this.sign = 0;
			}
			else if (val < 0)
			{
				this.sign = -1;
				tmpVal    = -tmpVal;
			}
			else
			{
				this.sign = 1;
			}

			// 値設定
			this.values = null;
			for (int i = 0; i < (T.sizeof / uint.sizeof); i++)
			{
				this.values  ~= cast(uint) (tmpVal & uint.max);
				tmpVal      >>= BLOCK_BIT;
				if (tmpVal == 0) { break; }
			}
		}

		// ----- 浮動小数型の場合 -----
		else static if (__traits(isFloating, T))
		{
			setValue(cast(long) val);
		}

		// ----- bigint の場合 -----
		else static if (is(T == bigint))
		{
			this.sign   = val.sign;
			this.values = val.values.dup;
		}

		// ----- 上記以外 -----
		else
		{
			static assert(false);
		}
	}

	/** 符号. */
	byte   sign   = 0;

	/** 値. */
	uint[] values = [ 0 ];

	/** ブロックビット */
	static invariant int  BLOCK_BIT  = uint.sizeof * 8;
}


