# longlong.h – support functions for multi-word arithmetic

## Bit manipulation

flint_clz(x)

  Returns the number of zero-bits from the msb to the first non-zero bit in the limb \(x\). This is the number of steps \(x\) needs to be shifted left to set the most significant bit in \(x\). If \(x\) is zero then the return value is undefined.

flint_ctz(x)

  As for `flint_clz()`, but counts from the least significant end. If \(x\) is zero then the return value is undefined.

flint_bitcnt_t FLINT_BIT_COUNT(ulong x)

  Returns the number of binary bits required to represent x. If x is zero it returns 0. This is an inline-function only.

FLINT_FLOG2(x)
FLINT_CLOG2(x)

  For \(x \ge 1\), it returns \(\lfloor \log_2 x \rfloor\) and \(\lceil \log_2 x \rceil\), respectively.

## Addition and subtraction

Note

When aliasing inputs with outputs in these addition and subtraction macros, make sure to have \(s_{i}\) aliased with \(a_{i}\) for addition macros, and \(d_{i}\) aliased with \(m_{i}\) for optimal performance. Moreover, keep immediates (in other words, constants known to the compiler) in the \(b_{i}\) variables for addition and \(s_{i}\) for subtraction.

add_ssaaaa(s1, s0, a1, a0, b1, b0)

  Sets \(s_1\) and \(s_0\) according to \(c B^2 + s_1 B + s_0 = (a_1 B + a_0) + (b_1 B + b_0)\), where \(B = 2^{\mathtt{FLINT\_BITS}}\) is the base, and \(c\) is the carry from the addition which is not stored anywhere.

add_sssaaaaaa(s2, s1, s0, a2, a1, a0, b2, b1, b0)

  Works like `add_ssaaaa`, but for two three-limbed integers. Carry is lost.

sub_ddmmss(d1, d0, m1, m0, s1, s0)

  Sets \(d_1\) and \(d_0\) to the difference between the two-limbed integers \(m_1 B + m_0\) and \(s_1 B + s_0\), where \(B = 2^{\mathtt{FLINT\_BITS}}\). Borrow from the subtraction is not stored anywhere.

sub_dddmmmsss(d2, d1, d0, m2, m1, m0, s2, s1, s0)

  Works like `sub_dddmmmsss`, but for two three-limbed integers. Borrow is lost.

## Multiplication

umul_ppmm(p1, p0, u, v)

  Computes \(p_1 B + p0 = u v\), where \(B = 2^{\mathtt{FLINT\_BITS}}\).

smul_ppmm(p1, p0, u, v)

  Works like `umul_ppmm` but for signed numbers.

## Division

udiv_qrnnd(q, r, n1, n0, d)

  Computes the non-negative integers \(q\) and \(r\) in \(d q + r = n_1 B + n_0\), where \(B = 2^{\mathtt{FLINT\_BITS}}\). Assumes that \(n_1 < d\).

sdiv_qrnnd(quotient, remainder, high_numerator, low_numerator, denominator)

  Works like `udiv_qrnnd`, but for signed numbers.

udiv_qrnnd_preinv(q, r, n1, n0, d, di)

  Works like `udiv_qrnnd`, but takes a precomputed inverse `di` as computed by `n_preinvert_limb_prenorm()`. This function assumes `d` is normalised, i.e. with most significant bit set.