title: 128-bit integer documentation_of: atcoder/extra/numeric/int128

128-bit integer

128-bitの符号なし整数 UInt128 と符号付き整数 Int128 を提供する。実装はC/C++のネイティブ __int128 に依存しないpure Nim実装であり、 C backendとC++ backendの両方で利用できる。

内部表現は2個の uint64 limbだが、fieldは公開されていない。値の生成・変換・演算には公開APIを使用する。

旧module

import atcoder/extra/math/int128

は互換shimとして残されている。新しいコードでは次を使用する。

import atcoder/extra/numeric/int128

Nimのidentifierはstyle-insensitiveであるため、従来の Uint128、 parseUint128、to_Uint128 という表記も引き続き利用できる。文書上の標準表記は UInt128、parseUInt128、toUInt128 とする。

型

UInt128
Int128

どちらも16 byteの固定長整数である。

UInt128 の範囲は 0 以上 2^128 - 1 以下。
Int128 は128-bit two's-complement表現を用い、範囲は -2^127 以上 2^127 - 1 以下。

生成と変換

toUInt128(x)
toInt128(x)

fromUInt64Words(highWord, lowWord)
fromInt128Bits(highWord, lowWord)

low64(x)
high64(x)

fromUInt64Words と fromInt128Bits は、上位64 bitと下位64 bitから値を構築する。内部fieldそのものは公開されない。

整数型からのconverterも提供されるため、文脈によっては通常の整数を直接代入できる。

let a: UInt128 = 123
let b: Int128 = -456

基本演算

次の演算を提供する。

+
-
*
div
mod
shl
shr
and
or
xor
not

==
<
<=
>
>=
cmp

UInt128 の +、-、* は 2^128 を法とするwrap演算である。 Int128 の +、-、* もtwo's-complement bit列上でwrapする。

Int128 の div と mod は0方向へ丸める。

parseInt128("-7") div parseInt128("3") == parseInt128("-2")
parseInt128("-7") mod parseInt128("3") == parseInt128("-1")

数学的なfloor divisionが必要な場合は次を使用する。

floorDiv(x, y)
floorMod(x, y)

floorDiv(parseInt128("-7"), parseInt128("3")) == parseInt128("-3")
floorMod(parseInt128("-7"), parseInt128("3")) == parseInt128("2")

0除算は DivByZeroDefect を送出する。

wrap・overflow・saturating演算

wrapping

wrappingAdd(a, b)
wrappingSub(a, b)
wrappingMul(a, b)

通常の +、-、* と同じwrap結果を明示的に得る。

overflowing

overflowingAdd(a, b)
overflowingSub(a, b)
overflowingMul(a, b)

返り値は次のnamed tupleである。

tuple[value: UInt128, overflow: bool]
tuple[value: Int128, overflow: bool]

value はwrap後の値、overflow は数学的な結果が型の範囲外かを表す。

let maximum =
  parseUInt128("340282366920938463463374607431768211455")

let result =
  overflowingAdd(maximum, parseUInt128("1"))

doAssert result.overflow
doAssert result.value == parseUInt128("0")

saturating

saturatingAdd(a, b)
saturatingSub(a, b)
saturatingMul(a, b)

overflowした場合、結果をその型の最小値または最大値へ固定する。

bit演算

countLeadingZeroBits(x)
countTrailingZeroBits(x)
popcount(x)

rotateLeft(x, distance)
rotateRight(x, distance)

0に対するleading zero countとtrailing zero countは128である。

rotationの距離は128を法として正規化される。負の距離も利用できる。

let one = parseUInt128("1")

doAssert rotateLeft(one, 127) ==
  parseUInt128("170141183460469231731687303715884105728")

doAssert rotateLeft(one, -1) ==
  rotateRight(one, 1)

Int128 のbit countとrotationは、その128-bit two's-complement bit列に対して行われる。

文字列変換

parseUInt128(s)
parseInt128(s)
$ value

10進文字列との相互変換を提供する。

let x =
  parseUInt128("18446744073709551616")

doAssert $x == "18446744073709551616"

let y =
  parseInt128("-170141183460469231731687303715884105728")

doAssert $y ==
  "-170141183460469231731687303715884105728"

空文字列、数字を含まない符号だけの文字列、10進数字以外を含む文字列は ValueError となる。

その他

abs(x)
hash(x)

pow(base, exponent, modulus)
base ^ exponent

inc(x)
dec(x)

+=
-=
*=

Int128 の負の指数は ValueError となる。 modular powerで法が0の場合は DivByZeroDefect となる。

使用例

import atcoder/extra/numeric/int128let a =  parseUInt128("123456789012345678901234567890")let b =  parseUInt128("9876543210987654321")echo a + becho a * becho a div becho a mod blet overflow =  overflowingMul(a, b)echo overflow.valueecho overflow.overflow

互換性

従来の次のimportは引き続き利用できる。

import atcoder/extra/math/int128

この旧pathはcanonical implementationをre-exportする互換shimである。新規コードでは atcoder/extra/numeric/int128 を推奨する。