# Unsigned 64-bit integer operations

Module `std::math::u64`

contains a set of procedures which can be used to perform unsigned 64-bit integer operations. These operations fall into the following categories:

**Arithmetic operations**- addition, multiplication, division etc.**Comparison operations**- equality, less than, greater than etc.**Bitwise operations**- binary AND, OR, XOR, bit shifts etc.

All procedures assume that an unsigned 64-bit integer (u64) is encoded using two elements, each containing an unsigned 32-bit integer (u32). When placed on the stack, the least-significant limb is assumed to be deeper in the stack. For example, a u64 value `a`

consisting of limbs `a_hi`

and `a_lo`

would be position on the stack like so:

```
[a_hi, a_lo, ... ]
```

Many of the procedures listed below (e.g., `overflowing_add`

, `wrapping_add`

, `lt`

) do not check whether the inputs are encoded using valid `u32`

values. These procedures do not fail when the inputs are encoded incorrectly, but rather produce undefined results. Thus, it is important to be certain that limbs of input values are valid `u32`

values prior to calling such procedures.

## Arithmetic operations

Procedure | Description |
---|---|

overflowing_add | Performs addition of two unsigned 64-bit integers preserving the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [overflow_flag, c_hi, c_lo, ...], where c = (a + b) % 2^64 This takes 6 cycles. |

wrapping_add | Performs addition of two unsigned 64-bit integers discarding the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a + b) % 2^64 This takes 7 cycles. |

overflowing_sub | Performs subtraction of two unsigned 64-bit integers preserving the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [underflow_flag, c_hi, c_lo, ...], where c = (a - b) % 2^64 This takes 11 cycles. |

wrapping_sub | Performs subtraction of two unsigned 64-bit integers discarding the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a - b) % 2^64 This takes 10 cycles. |

overflowing_mul | Performs multiplication of two unsigned 64-bit integers preserving the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi_hi, c_hi_lo, c_lo_hi, c_lo_lo, ...], where c = (a * b) % 2^64 This takes 18 cycles. |

wrapping_mul | Performs multiplication of two unsigned 64-bit integers discarding the overflow. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = (a * b) % 2^64 This takes 11 cycles. |

div | Performs division of two unsigned 64-bit integers discarding the remainder. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a // b This takes 54 cycles. |

mod | Performs modulo operation of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a % b This takes 54 cycles. |

divmod | Performs divmod operation of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [r_hi, r_lo, q_hi, q_lo ...], where r = a % b, q = a // b This takes 54 cycles. |

## Comparison operations

Procedure | Description |
---|---|

lt | Performs less-than comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a < b, and 0 otherwise. This takes 11 cycles. |

gt | Performs greater-than comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a > b, and 0 otherwise. This takes 11 cycles. |

lte | Performs less-than-or-equal comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a <= b, and 0 otherwise. This takes 12 cycles. |

gte | Performs greater-than-or-equal comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a >= b, and 0 otherwise. This takes 12 cycles. |

eq | Performs equality comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a == b, and 0 otherwise. This takes 6 cycles. |

neq | Performs inequality comparison of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c, ...], where c = 1 when a != b, and 0 otherwise. This takes 6 cycles. |

eqz | Performs comparison to zero of an unsigned 64-bit integer. The input value is assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [a_hi, a_lo, ...] -> [c, ...], where c = 1 when a == 0, and 0 otherwise. This takes 4 cycles. |

min | Compares two unsigned 64-bit integers and drop the larger one from the stack. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a when a < b, and b otherwise. This takes 23 cycles. |

max | Compares two unsigned 64-bit integers and drop the smaller one from the stack. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a when a > b, and b otherwise. This takes 23 cycles. |

## Bitwise operations

Procedure | Description |
---|---|

and | Performs bitwise AND of two unsigned 64-bit integers. The input values are assumed to be represented using 32-bit limbs, but this is not checked. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a AND b. This takes 6 cycles. |

or | Performs bitwise OR of two unsigned 64-bit integers. The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a OR b. This takes 16 cycles. |

xor | Performs bitwise XOR of two unsigned 64-bit integers. The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not. The stack transition looks as follows: [b_hi, b_lo, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a XOR b. This takes 6 cycles. |

shl | Performs left shift of one unsigned 64-bit integer using the pow2 operation. The input value to be shifted is assumed to be represented using 32-bit limbs. The shift value should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a << b mod 2^64. This takes 28 cycles. |

shr | Performs right shift of one unsigned 64-bit integer using the pow2 operation. The input value to be shifted is assumed to be represented using 32-bit limbs. The shift value should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a >> b. This takes 44 cycles. |

rotl | Performs left rotation of one unsigned 64-bit integer using the pow2 operation. The input value to be shifted is assumed to be represented using 32-bit limbs. The shift value should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a << b mod 2^64. This takes 35 cycles. |

rotr | Performs right rotation of one unsigned 64-bit integer using the pow2 operation. The input value to be shifted is assumed to be represented using 32-bit limbs. The shift value should be in the range [0, 64), otherwise it will result in an error. The stack transition looks as follows: [b, a_hi, a_lo, ...] -> [c_hi, c_lo, ...], where c = a << b mod 2^64. This takes 40 cycles. |

clz | Counts the number of leading zeros of one unsigned 64-bit integer. The input value is assumed to be represented using 32 bit limbs, but this is not checked. The stack transition looks as follows: `[n_hi, n_lo, ...] -> [clz, ...]` , where `clz` is a number of leading zeros of value `n` .This takes 43 cycles. |

ctz | Counts the number of trailing zeros of one unsigned 64-bit integer. The input value is assumed to be represented using 32 bit limbs, but this is not checked. The stack transition looks as follows: `[n_hi, n_lo, ...] -> [ctz, ...]` , where `ctz` is a number of trailing zeros of value `n` .This takes 41 cycles. |

clo | Counts the number of leading ones of one unsigned 64-bit integer. The input value is assumed to be represented using 32 bit limbs, but this is not checked. The stack transition looks as follows: `[n_hi, n_lo, ...] -> [clo, ...]` , where `clo` is a number of leading ones of value `n` .This takes 42 cycles. |

cto | Counts the number of trailing ones of one unsigned 64-bit integer. The input value is assumed to be represented using 32 bit limbs, but this is not checked. The stack transition looks as follows: `[n_hi, n_lo, ...] -> [cto, ...]` , where `cto` is a number of trailing ones of value `n` .This takes 40 cycles. |