BitLength¶

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description¶

BitLength[n]

gives the number of binary bits needed to represent the integer n.

Notes

For n \> 0, BitLength\[n\] is Floor\[Log\[2, n\]\] + 1; BitLength\[0\] is 0. For n \< 0, BitLength\[n\] is equivalent to BitLength\[BitNot\[n\]\].

Examples (12)¶

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (6)¶

In[1]:= BitLength[255]
Out[1]= 8

In[2]:= BitLength[256]
Out[2]= 9

In[3]:= BitLength[2^100]
Out[3]= 101

In[4]:= BitLength[100!]
Out[4]= 525

In[5]:= BitLength[{0, 1, 2, 7, 8, 255, 256}]
Out[5]= {0, 1, 2, 3, 4, 8, 9}

In[6]:= BitLength[{-1, -2, -8, -256}]
Out[6]= {0, 1, 3, 8}

Scope (1)¶

In[7]:= BitLength[1, 2] BitLength::argx: BitLength called with 2 arguments; 1 argument is expected.

Applications (5)¶

255 is 11111111 in binary, eight bits

In[8]:= BitLength[255]
Out[8]= 8

One more bit than 255

In[9]:= BitLength[256]
Out[9]= 9

Exact for arbitrarily large integers, with no floating point

In[10]:= BitLength[2^100]
Out[10]= 101

A negative n uses two's complement: BitLength[BitNot[n]]

In[11]:= BitLength[-256]
Out[11]= 8

Listable: it threads over a list

In[12]:= BitLength[{0, 1, 2, 7, 8, 255, 256}]
Out[12]= {0, 1, 2, 3, 4, 8, 9}

Options & behaviour¶

Diagnostics. A non-integer argument emits BitLength::int and echoes the call back unevaluated; a wrong-arity call emits BitLength::argx. A symbolic argument is left unevaluated silently.

Algorithm¶

bitlength.c

BitLength[n] -- the number of binary bits needed to represent the integer n.

  n > 0 : Floor[Log[2, n]] + 1   (= mpz_sizeinbase(n, 2)).
  n = 0 : 0.
  n < 0 : BitLength[BitNot[n]], and BitNot[n] = -n - 1 in two's complement,
          so BitLength[-1] = 0, BitLength[-2] = 1, BitLength[-2^k] = k.

BitLength is Listable (threads over lists automatically). The packed / NDArray fast path is the int64 kernel ndk_BitLength_ii in src/ndinteger.c and the Compile[] lowering is OP_BLEN_I in src/compile/. All arithmetic here is done in GMP, so machine integers and arbitrary-precision bignums are handled uniformly.

Implementation notes¶

Algorithm. builtin_bitlength gives the number of binary bits needed to represent an integer n. All arithmetic is done in GMP, so machine integers (EXPR_INTEGER) and bignums (EXPR_BIGINT) are handled uniformly. The magnitude whose base-2 size is wanted is n itself for n >= 0 and BitNot[n] = -n - 1 for n < 0 (computed as -(n + 1), which is >= 0 there); its bit length is mpz_sizeinbase(m, 2) — exact, because base 2 is a power of two — and 0 is special-cased to 0. So BitLength[n] = Floor[Log2[n]] + 1 for n > 0 without ever going through floating point, BitLength[0] = 0, BitLength[-1] = 0, BitLength[-2] = 1, and BitLength[-2^k] = k.

A concrete non-integer numeric argument (Real, Rational, Complex, …) emits BitLength::int and leaves the call unevaluated; a symbolic argument flows through silently (returns NULL); a wrong arity emits BitLength::argx. Both diagnostics route through the mth_message funnel, so they honour Quiet[]/Check[].

Data structures. Two short-lived GMP mpz_t values (n and the magnitude m); the result is a machine Integer, since a bit length is bounded by the operand's own size and always lands within EXPR_INTEGER range.

Complexity / limits. O(1) on a machine integer, O(size of n) on a bignum (the cost of mpz_sizeinbase). BitLength is Protected and Listable, so it threads element-wise over a list. The packed/NDArray fast path is the int64 kernel ndk_BitLength_ii (src/ndinteger.c) and the Compile[] lowering is OP_BLEN_I; both cover the full int64 range including INT64_MIN (BitLength[-2^63] is 63), which the complement-based magnitude computes without overflow.

Protected, Listable. Threads element-wise over a list of integers, e.g. BitLength[{0, 1, 2, 7, 8, 255, 256}].
For n > 0, BitLength[n] is an efficient exact version of Floor[Log[2, n]] + 1 -- it never converts through floating-point and is exact for arbitrarily large n (via GMP's mpz_sizeinbase in base 2).
BitLength[0] is 0.
For n < 0, BitLength[n] is equivalent to BitLength[BitNot[n]]. In two's complement BitNot[n] = -n - 1, so BitLength[-1] is 0, BitLength[-2] is 1, and BitLength[-2^k] is k.
Works for both machine integers and bignums. The packed / NDArray fast path (src/ndinteger.c) and the Compile[] lowering (OP_BLEN_I) both handle the full int64 range, including INT64_MIN (BitLength[-2^63] is 63), which the complement-based kernel computes without overflow.

Attributes: Listable, Protected.

References¶

See also: NDArray

Source: src/bitwise/bitlength.c
Specification: docs/spec/builtins/bitwise.md
Tests: tests/test_bitwise.c

Notes & additional examples¶

Notes¶

BitLength[n] is the number of binary bits needed to represent the integer n. For n > 0 it is an exact Floor[Log[2, n]] + 1 that never converts through floating point (it uses GMP's base-2 mpz_sizeinbase), so it is exact for arbitrarily large n. BitLength[0] is 0.

For n < 0 it equals BitLength[BitNot[n]], and in two's complement BitNot[n] = -n - 1, so BitLength[-1] is 0, BitLength[-2] is 1, and BitLength[-2^k] is k.

BitLength is Protected and Listable, so it threads element-wise over a list. It has a packed/NDArray int64 fast path and a Compile[] lowering, both covering the full int64 range including INT64_MIN (BitLength[-2^63] is 63). A non-integer argument emits BitLength::int and stays unevaluated; a symbolic argument is left unevaluated silently.