Integer logarithm in O(1) (especially for the C preprocessor)

lognint.py

#!/usr/bin/env python3

# SPDX-FileCopyrightText: 2026 Ilya Egorov <0x42005e1f@gmail.com>
# SPDX-License-Identifier: ISC

from __future__ import annotations

import sys

from math import ceil, log
from typing import TYPE_CHECKING, Literal

if TYPE_CHECKING:
    ModeType = Literal["floor", "ceil"]

COEF_TABLE: tuple[tuple[tuple[int, int], ...], ...] = (
    (( 6,  2), ( 12,   3), (22,  4), (44, 7), (86, 12)),
    ((11,  3), ( 33,   7), (98, 18)),
    ((21,  6), ( 81,  18)),
    ((33,  9), (161,  37)),
    ((47, 12), (281,  66)),
    ((65, 17), (449, 107)),
    ((85, 22), (673, 162)),
)


def calc_coef(base: int, stop: int) -> tuple[int, int, int]:
    """a - b//(c + x); x = base**(0..a) - 1"""

    if base < 2:
        msg = "`base` must be >= 2"
        raise ValueError(msg)

    if stop <= 0:
        a = 0
        b = 0
        c = 1
    elif stop <= 1:
        a = 1
        b = 1
        c = 1
    elif stop <= 2:
        a = 2
        b = 1 + 3*(base - 1)//2
        c = 1 + 3*(base - 1)//2 - base + 1
    elif base >= 9:
        a = 3
        b = 1 + 3*(base*base - base)//2
        c = 1 + 3*(base*base - base)//2 - base*base + 1
    else:  # stop >= 3
        a = min(stop, 2 + len(values := COEF_TABLE[base - 2]))
        b = values[a - 3][0]
        c = values[a - 3][1]

    return (a, b, c)


def find_maxsize(base: int, stop: int, mode: ModeType) -> int:
    """Lambert W function in integers (floor/ceil)"""

    if base < 2:
        msg = "`base` must be >= 2"
        raise ValueError(msg)

    if stop < 2:
        msg = "`stop` must be >= 2"
        raise ValueError(msg)

    term = log(stop + 1, base)
    size = ceil(term - log(term, base))

    if mode == "floor":
        if size*(base**size - 1) - 1 > stop:
            size -= 1
    elif mode == "ceil":
        if size*(base**size - 1) - 1 < stop:
            size += 1
    else:
        msg = "`mode` must be 'floor' or 'ceil'"
        raise ValueError(msg)

    return size


def gen_blocks(base: int, stop: int, mode: ModeType) -> list[tuple[int, int]]:
    maxsize = find_maxsize(base, stop, mode=mode)

    if maxsize < 2:
        return []

    if base < 6:
        sizes = range(2, len(COEF_TABLE[base - 2]) + 4)
    else:
        sizes = range(2, base)

    if sizes.stop - 2 >= stop:
        return []

    items = [[(base**size - 1, size)] for size in sizes]
    result = None

    while items:
        next_items: list[list[tuple[int, int]]] = []

        for blocks in items:
            block, blocksize = blocks[-1]

            if mode == "floor":
                limit = min(block, maxsize//blocksize) + 1
            elif mode == "ceil":
                limit = min(block, (maxsize + blocksize - 1)//blocksize) + 1
            else:
                msg = "`mode` must be 'floor' or 'ceil'"
                raise ValueError(msg)

            if next_sizes := range(2, limit):
                next_items.extend(
                    [*blocks, ((block + 1)**size - 1, blocksize*size)]
                    for size in next_sizes
                )
            elif mode == "floor":
                if blocksize <= maxsize:
                    if result is None:
                        result = blocks
                    elif blocksize > result[-1][-1]:
                        result = blocks
                    elif blocksize == result[-1][-1]:
                        if len(blocks) < len(result):
                            result = blocks
                        elif len(blocks) == len(result):
                            if blocks < result:
                                result = blocks
            elif mode == "ceil":
                if blocksize >= maxsize:
                    if result is None:
                        result = blocks
                    elif blocksize < result[-1][-1]:
                        result = blocks
                    elif blocksize == result[-1][-1]:
                        if len(blocks) < len(result):
                            result = blocks
                        elif len(blocks) == len(result):
                            if blocks < result:
                                result = blocks
            else:
                msg = "`mode` must be 'floor' or 'ceil'"
                raise ValueError(msg)

        items = next_items

    assert result is not None

    if result[-1][0]*result[-1][1] < sizes.stop:
        result = []

    return result


def gen_expr(base: int, stop: int, mode: ModeType) -> tuple[int, str]:
    if base < 2:
        msg = "`base` must be >= 2"
        raise ValueError(msg)

    if stop <= 0:
        return (0, "(0)")

    if stop <= 1:
        return (1, "(1-1//(1+(x)))")

    blocks = gen_blocks(base, stop, mode=mode)

    if blocks:
        start = blocks[0][-1] - 1
    else:
        start = stop

    if base >= min(start + 2, 6):
        parts = [f"(x)//{base - 1}%{base - 1}"]
        power = base - 2
    else:
        a, b, c = calc_coef(base, start)
        parts = [f"{a}-{b}//({c}+(x))"]
        power = a

    for block, blocksize in blocks:
        parts[-1] = parts[-1].replace("(x)", f"(x)%{block}", 1)
        parts.append(f"(x)//((x)%{block}+1)//{block}%{block}*{blocksize}")
        power = block*blocksize - 1

    return (power, f"({'+'.join(reversed(parts))})")


def main() -> None:
    base, stop = map(eval, sys.argv[1:])

    left_exp, left_expr = gen_expr(base, stop, mode="floor")
    left_limits = f"x = {base}^n - 1, where 0 <= n <= {left_exp}"
    right_exp, right_expr = gen_expr(base, stop, mode="ceil")
    right_limits = f"x = {base}^n - 1, where 0 <= n <= {right_exp}"

    print(f"The nearest expression on the left  ({left_limits}):")
    print(f"    {left_expr}")
    print(f"The nearest expression on the right ({right_limits}):")
    print(f"    {right_expr}")


if __name__ == "__main__":
    main()

Warning

This comment is a work-in-progress description. The content is expected to grow significantly over time, and the existing sections will also be modified or completely rewritten (largely to address the AI's biases; I apologize for spending time on this nonsense instead of writing something that might be more interesting to you). I hope you will like the final version, so please be patient.

This is the first known generalization and justification of the method published by Hallvard B. Furuseth as a function-like macro in 2003. Unlike the original, this gist contains an expression generator for any base (not just 2) and any maximum exponent (not just a hard-coded one). I reinvented and extended the method from scratch because I was skeptical of "magic numbers", and so I especially want to explain how it works so that my solution is not just a hack for you either.

How to use

lognint.py is a script for Python ≥3.8. It takes two integer arguments:

1. base — the base of the number system.
2. stop — the maximum supported exponent.

The script generates expressions that allow the exponent $n$ to be calculated for numbers of the form $m^n - 1$ ($2 ≤ m = \text{base}$, $0 ≤ n ≤ \text{stop}$), that is, to compute the logarithm to the given base. To handle the form $m^n$, it is sufficient to simply subtract one from the input value. Like Hallvard B. Furuseth's original work, it does not support intermediate values that do not correspond to the form: for example, for $m = 2$, $2^6 - 1 = 63$ is valid but $64$ is not (for the latter, the result is undefined).

All expressions use the Python syntax for consistency and ease of verification, but functionally they are defined solely by integer arithmetic, so they are easily portable to other languages. In particular, for C, it is sufficient to replace all // with /, and the expression can then be used as is (for example, as the IMAX_BITS macro when the base is 2).

---

$ ./lognint.py 2 100
The nearest expression on the left  (x = 2^n - 1, where 0 <= n <= 59):
    ((x)//((x)%15+1)//15%15*4+3-6//(2+(x)%15))
The nearest expression on the right (x = 2^n - 1, where 0 <= n <= 154):
    ((x)//((x)%31+1)//31%31*5+4-12//(3+(x)%31))
$ ./lognint.py 3 100
The nearest expression on the left  (x = 3^n - 1, where 0 <= n <= 77):
    ((x)//((x)%26+1)//26%26*3+2-4//(2+(x)%26))
The nearest expression on the right (x = 3^n - 1, where 0 <= n <= 319):
    ((x)//((x)%80+1)//80%80*4+3-11//(3+(x)%80))
$ ./lognint.py 5 100
The nearest expression on the left  (x = 5^n - 1, where 0 <= n <= 47):
    ((x)//((x)%24+1)//24%24*2+(x)%24//4%4)
The nearest expression on the right (x = 5^n - 1, where 0 <= n <= 371):
    ((x)//((x)%124+1)//124%124*3+(x)%124//4%4)
$ ./lognint.py 7 100
The nearest expression on the left  (x = 7^n - 1, where 0 <= n <= 95):
    ((x)//((x)%48+1)//48%48*2+(x)%48//6%6)
The nearest expression on the right (x = 7^n - 1, where 0 <= n <= 1025):
    ((x)//((x)%342+1)//342%342*3+(x)%342//6%6)

>>> x = 2**12 - 1
>>> ((x)//((x)%31+1)//31%31*5+4-12//(3+(x)%31))
12
>>> x = 3**34 - 1
>>> ((x)//((x)%80+1)//80%80*4+3-11//(3+(x)%80))
34
>>> x = 5**56 - 1
>>> ((x)//((x)%124+1)//124%124*3+(x)%124//4%4)
56
>>> x = 7**78 - 1
>>> ((x)//((x)%342+1)//342%342*3+(x)%342//6%6)
78

How it works

Unsigned integers with a k-multiple width

Suppose we have the maximum value of some unsigned integer, of the form $2^n - 1$ — a non-negative integer ($≥ 0$), where $n$ is a natural integer ($≥ 1$ ⇒ more strictly, $2^n - 1 ≥ 1$, since $2^1 - 1 = 2 - 1 = 1$, and as $n$ increases, the value also increases). And we want to find its width, that is, $n$ — the number of bits or, in other words, the number of digits in the base-2 numeral system. But under very specific conditions: no real numbers, no loops, no branches — only integer arithmetic (the C preprocessor).

An example of such a value is $2^{16} - 1 = 65535$, sometimes called a Mersenne number or a base-2 repunit. It can be represented as a repdigit in at least the binary, quaternary, and hexadecimal numeral systems:

• $\text{1111111111111111}_{2} \quad\text{(16 digits)}$
• $\text{33333333}_{4} \quad\text{(8 digits)}$
• $\text{FFFF}_{16} \quad\text{(4 digits)}$

And algebraically they take the following forms:

• $1⋅2^{15} + 1⋅2^{14} + 1⋅2^{13} + 1⋅2^{12} + 1⋅2^{11} + 1⋅2^{10} + 1⋅2^{9} + 1⋅2^{8} + 1⋅2^{7} + 1⋅2^{6} + 1⋅2^{5} + 1⋅2^{4} + 1⋅2^{3} + 1⋅2^{2} + 1⋅2^{1} + 1⋅2^{0}$
• $3⋅4^{7} + 3⋅4^{6} + 3⋅4^{5} + 3⋅4^{4} + 3⋅4^{3} + 3⋅4^{2} + 3⋅4^{1} + 3⋅4^{0}$
• $15⋅16^{3} + 15⋅16^{2} + 15⋅16^{1} + 15⋅16^{0}$

These numeral systems are not chosen at random. The number of bits $n$ is usually a multiple of a byte, which is also usually a multiple of an octet (8 bits; a byte is wider but a multiple of that (16-/24-/32-bit), for example, on some DSPs). The binary, quaternary, and hexadecimal numeral systems have, respectively, $2 = 2^1$, $4 = 2^2$, $16 = 2^4$ values per digit, therefore, $1 = 2^0$, $2 = 2^1$, $4 = 2^2$ bits per digit. And these are exactly the divisors of 8 bits, except for the last one — the 8 bits itself!

The final divisor corresponds to the base-256 numeral system ($256 = 2^8$ values per digit; $8 = 2^3$ bits per digit), and in this system, the value takes the following form:

$$ 255⋅256^1 + 255⋅256^0 $$

The first sum (base-2) has 16 terms, each 1 bit long, and that is the value we want to find ($n$). The last sum (base-256) has only 2 terms, but each is 8 bits long — the sum with the fewest terms if we want to cover all $n$ that are multiples of 8 bits. What if we count in 8-bit bytes instead of bits (which is valid in most cases), and then simply multiply the result by eight? First, let us convert the expression into a sum of powers:

$$ \frac{255⋅256^1 + 255⋅256^0}{255} = 256^1 + 256^0 $$

Now, the value can be represented as follows in the previous numeral systems:

• $\text{0000000100000001}_{2} \quad\text{(16 digits)}$
• $\text{00010001}_{4} \quad\text{(8 digits)}$
• $\text{0101}_{16} \quad\text{(4 digits)}$

Or, algebraically:

• $1⋅2^{8} + 1⋅2^{0}$
• $1⋅4^{4} + 1⋅4^{0}$
• $1⋅16^{2} + 1⋅16^{0}$

We have, in a sense, replaced each sequence of 8 ones (in bits) with a single one, padded with zeros on the left. Now we just have to calculate their sum. There is a useful mathematical property for this:

$$ 2^8 = 4^4 = 16^2 = 256^1 ≡ 1 \pmod{255} $$

Which means:

$$ (256^1 + 256^0) \bmod 255 = (1^1 + 1^0) \bmod 255 = 2 $$

So, all that remains is to combine all the operations in hexadecimal form (for clarity) and multiply by the byte width. Let us do that, and at the same time check for some other powers:

>>> (2**8-1)//0xFF%0xFF*8
8
>>> (2**16-1)//0xFF%0xFF*8
16
>>> (2**24-1)//0xFF%0xFF*8
24
>>> (2**32-1)//0xFF%0xFF*8
32
>>> (2**40-1)//0xFF%0xFF*8
40
>>> (2**48-1)//0xFF%0xFF*8
48
>>> (2**56-1)//0xFF%0xFF*8
56
>>> (2**64-1)//0xFF%0xFF*8
64

It works! However, not without limitations:

1. Since we are counting bytes rather than bits, this expression only supports exponents that are multiples of 8 (i.e., $8n$). Otherwise, the operation //0xFF would be invalid.
2. The maximum supported exponent is limited by modular arithmetic, that is, by the byte width: $(255 - 1)⋅8 = 2032$. For $2^{2040} - 1$, the expression gives $0$, since $255 ≡ 0 \pmod{255}$.

Note

It would be more precise to state that $n < 255 ⇒ 8n < 2040$ for numbers of the form $2^{8n} - 1$. This is especially true if we process the part that is not a multiple of a byte in some way, in which case the maximum supported exponent would be 2039 instead of 2032. But we use the latter (inclusive) concept because it is more convenient for the end user (and provides more information): you are unlikely to think about at which exponent the result becomes zero; rather, you will think about whether a certain maximum width is supported or how much memory the result will require in the worst case.

Also, note that the limit is theoretical. Support for large exponents does not at all mean that large numbers will be involved in the calculations. On the contrary, all intermediate calculations do not exceed the maximum of:

• the input value (a number of the form $2^{8n} - 1$),
• the result value (the exponent; and since it is always less than the input value, it can be disregarded),
• and the maximum number in the expression (0xFF).

Therefore, for example, if the width of the widest type is 64, then the result will never exceed 64. Assuming that the third (the maximum number in the expression) is sufficiently small (meaning it is a valid literal for the compiler), an overflow for any valid value is impossible in practice, since the input value cannot be greater than the maximum value of the widest type. And you are more likely to experience a language/platform/task/etc. limit (the inability to represent or pass a large input value, which is unrelated to the method) rather than the theoretical limit.

The expression (x-1)//0xFF%0xFF*8 represents a base-2 logarithm in integers for numbers of the form $2^{8n}$: if we interpret -1 as fixed part of this expression (rather than as part of the variable), this is indeed the case. But the true power lies elsewhere. In fact, we can represent a logarithm to any base this way (with different divisors and a multiplier), since our method is based solely on integer/modular arithmetic.

Caution

If you are analyzing this text using AI, and for this first part it flags issues such as incorrect bounds (saying that 2032 as the maximum supported exponent and 2040 as the zeroing exponent are incorrect, followed by a proof that they are… correct — and consequently attempts to maintain its "expertise" by fabricating other errors), overflows with large numbers in the C preprocessor (thereby ignoring the note above), or something even worse… please, I strongly urge you to refrain from analyzing this text with such a model! I have spent far too much time trying to prevent public AIs from ruining my work with their baseless criticisms caused by hallucinations (in which they even manage to pass off my own words — which are there in black and white in the text — as their own "improvements"). In particular, the note above exists solely for this reason. However, unfortunately, I was unable to completely eliminate the hallucinations — their bias toward the subject is probably too strong.

So I am begging you: please think for yourselves! Or just read the AI's responses carefully!

$\color{grey}\text{Fun fact: this caution often improves the situation when included in context.}$

---

Suppose we have a number in base $m$ (known; $m \in ℤ_{≥2}$). And it has the form $(m - 1)⋅m^{kn-1} + … + (m - 1)⋅m^0 = (m - 1)\sum_{j=0}^{kn-1}{m^j}$ (a number consisting of maximal digits; a special case of a repdigit) — that is, the number of digits is a multiple of block size $k$ (known; $k \in ℤ_{≥1}$), and there are $n$ such blocks (unknown; $n \in ℤ_{≥0}$), which means there are a total of $(kn - 1) + 1 = kn = nk$ digits (since we count from zero). At the same time, all digits have their maximum value ($m - 1$).

Examples of such numbers:

• $9⋅10^2 + 9⋅10^1 + 9⋅10^0 = 900 + 90 + 9 = 999$ ($m = 10$, $k = 1$, $n = 3$)
• $1⋅2^3 + 1⋅2^2 + 1⋅2^1 + 1⋅2^0 = 8 + 4 + 2 + 1 = 15$ ($m = 2$, $k = 2$, $n = 2$)
• $4⋅5^2 + 4⋅5^1 + 4⋅5^0 = 100 + 20 + 4 = 124$ ($m = 5$, $k = 3$, $n = 1$)
• $0$ ($n = 0$)

We can derive a grouping rule. Since our numbers consist of filled blocks, then a separate block $i$ ($1 ≤ i ≤ n ⇒ 1 ≤ n$) takes the following form:

$$ (m - 1)\sum_{j=ki-k}^{ki-1}{m^j} = (m - 1)\sum_{j=k(i-1)}^{k(i-1)+(k-1)}{m^j} = (m - 1)\sum_{j=0}^{k-1}{m^{k(i-1)+j}} $$

Interpreting the latter as the sum of a finite geometric series (where the initial term is $m^{k(i-1)+0}=m^{k(i-1)}$, the common ratio is $m$, and the number of terms is $(k - 1) + 1 = k$):

$$ (m - 1)\sum_{j=0}^{k-1}{m^{k(i-1)+j}} = (m - 1)\frac{m^{k(i-1)}⋅(m^k - 1)}{m - 1} = m^{k(i-1)}⋅(m^k - 1) = (m^k - 1)⋅m^{k(i-1)} = (m^k - 1)⋅(m^k)^{i-1} $$

When $n = 0$, no block $i$ exists, since there is simply nothing to numerate. In this case, we will treat the grouping as producing zero (since summing a sequence of zeros results in zero, regardless of $m$ and $k$). Finally, if we apply the transformation to the entire number, then for any $n ≥ 0$:

$$ (m - 1)\sum_{j=0}^{kn-1}{m^j} = (m - 1)\sum_{i=1}^{n}{\sum_{j=ki-k}^{ki-1}{m^j}} = (m^k - 1)\sum_{i=1}^{n}{(m^k)^{i-1}} = (m^k - 1)\sum_{j=0}^{n-1}{(m^k)^j} $$

In fact, we have performed a conversion from one number system to another: from $m$ to $m^k$. And in the special case where $n = 1$, that is, a single block covers the entire number ($k$ is exactly the number of digits):

$$ (m - 1)\sum_{j=0}^{kn-1}{m^j} \xrightarrow{n=1} (m - 1)\sum_{j=0}^{k-1}{m^j} $$

$$ (m^k - 1)\sum_{j=0}^{n-1}{(m^k)^j} \xrightarrow{n=1} (m^k - 1)\sum_{j=0}^{0}{(m^k)^j} = (m^k - 1)⋅(m^k)^0 = m^k - 1 $$

$$ (m - 1)\sum_{j=0}^{k-1}{m^j} = m^k - 1 $$

Thus, these numbers represent powers in the given number system minus one:

$$ (m - 1)\sum_{j=0}^{kn-1}{m^j} = m^{kn} - 1 = (m^k)^n - 1 = (m^k - 1)\sum_{j=0}^{n-1}{(m^k)^j} $$

And this is clearly seen in the examples above:

• $999 = 1000 - 1 = 10^3 - 1$
• $15 = 16 - 1 = 2^4 - 1$ ($= 4^2 - 1 = 3⋅4^1 + 3⋅4^0 = 12 + 3 = 15$)
• $124 = 125 - 1 = 5^3 - 1$
• $0 = 1 - 1 = m^0 - 1$ ($\forall m$)

Now let us calculate the number of blocks $n$ (to make it known). It corresponds to the number of digits in the base $m^k$, so we will work in that base. First, we will eliminate the constant factor using the standard division operation, which in this case yields no remainder:

$$ \frac{(m^k)^n - 1}{m^k - 1} = \frac{(m^k - 1)\sum_{j=0}^{n-1}{(m^k)^j}}{m^k - 1} = \sum_{j=0}^{n-1}{(m^k)^j} $$

Second, note that according to modular arithmetic:

$$ m^k = (m^k - 1) + 1 ≡ 1 ⇒ (m^k)^j ≡ 1^j = 1 \pmod{m^k - 1} $$

And thus:

$$ \sum_{j=0}^{n-1}{(m^k)^j} ≡ \sum_{j=0}^{n-1}{1} = (n - 1) + 1 = n \pmod{m^k - 1} $$

As a consequence, for the base $m^k$, the following holds:

$$ \frac{(m^k)^n - 1}{m^k - 1} \bmod (m^k - 1) = n \bmod (m^k - 1) $$

From this, we can find the number of digits in base $m$. One digit in base $m^k$ corresponds to $k$ digits in base $m$. And thus we obtain:

$$ \left(\frac{m^{kn} - 1}{m^k - 1} \bmod (m^k - 1)\right)k = \left(n \bmod (m^k - 1)\right)k $$

The modulo operation imposes an upper bound on $n$ for our problem: $0 ≤ n < m^k - 1$, since $m^k - 1 ≡ 0 \pmod{m^k - 1}$. If we exceed the upper bound, the values will begin to cycle and thus will no longer be considered valid numbers of digits. But for $n$ that satisfies the constraint, the method works as intended. Moreover, the larger the base $m$ and the higher the block size $k$, the better the method works.

Note the limitations again:

• a number of the form $(m^k)^n - 1$
• $2 ≤ m$
• $1 ≤ k$
• $0 ≤ n < m^k - 1$

Some properties:

1. The maximum supported exponent is $(m^k - 2)k$.
2. The maximum supported number is $(m^k)^{m^k-2} - 1$.

Remember that by adding one, the number represents a power in the given number system. And so, the operation of counting the number of digits — if we consider the original value to be that without one subtracted — is essentially a logarithm to base $m$ for numbers of the form $m^{kn} = (m^k)^n$. Or, to put it another way, — if we consider the original value to be that with one subtracted, and interpret it as the maximum value of a certain data type, — it is the width of the number in the given number system.

For example, a base-10 logarithm with block size 2 (maximum exponent 196):

>>> (10**0-1)//99%99*2
0
>>> (10**2-1)//99%99*2
2
>>> (10**4-1)//99%99*2
4
>>> (10**8-1)//99%99*2
8
>>> (10**16-1)//99%99*2
16
>>> (10**32-1)//99%99*2
32
>>> (10**64-1)//99%99*2
64
>>> (10**128-1)//99%99*2
128

Note

By the way, it is interesting to note that this:

$$ \frac{m^{kn} - 1}{m^k - 1} = \frac{(m^k)^n - 1}{m^k - 1} $$

is exactly a repunit in base $m^k$. This means that counting digits using the modulo operation is valid for any repunit (and thus for any repdigit).

---

Signed integers with a k-multiple width

At the beginning, we focused on unsigned integers, but now it is time to move on to signed ones. In the C23 standard (and most implementations of previous standards), their maximum value is $2^{n-1} - 1$ (where $n$ is the width of the corresponding unsigned type), and in this section, to simplify the explanation, we will stick to this version.

Signed types have the same width as their corresponding unsigned types, since the width of signed types includes both value bits and the sign bit (C99), and the number of value bits is exactly one less than that of the corresponding unsigned type (C23). The standard specifies the two's-complement representation of the sign, whereas earlier standards allowed two other alternative representations (sign and magnitude, one's complement); however, this affects only the representation of negative values and the minimum value, and has no effect on the representation of non-negative values and the maximum value.

Important

Do not confuse a type's width with its size in bits (sizeof(<type>)*CHAR_BIT). The size in bits may include padding bits used for memory alignment (C99). These bits do not carry value information, meaning width is always less than or equal to size. Think of width as the minimum amount of information required to represent any value of the type without loss, while size is the actual memory occupied.

Also note that the correspondence between signed and unsigned types is determined by: the same amount of storage, the same alignment requirements, and the one-to-one correspondence between value bits. This, the division of the representation bits into three groups (value bits, padding bits, and the sign bit), and the very concept of width (as value bits plus the sign bit) has been valid since C99. However, prior to C23, the number of value bits for signed types was only required to be less than or equal to the number of value bits for unsigned types, which formally allowed for:

• the maximum values of the signed and corresponding unsigned types to be equal;
• the difference between the maximum values to be more than one bit.

So, in the general case, the form given above might be incorrect, and we will return to this later.

To calculate the width of a signed type using modular arithmetic in base $2^k$, the number of digits (or value bits, whichever term you prefer) must be a multiple of the block size $k$. Moreover, if we consider a set of width values that we need to support, then $k$ must be a common divisor of those values. If we take, for example, 8-bit and 16-bit maximums, they will have $8 - 1 = 7$ and $16 - 1 = 15$ digits — there is no common integer divisor other than $1$, but the latter is meaningless since the maximum supported exponent will be $(m^k - 2)k = (2^1 - 2)1 = 0 < 15$. This means we need to transform the number in some way, that is, make it take the form $2^n - 1$.

There are two approaches: rounding up or rounding down. The first seems the most obvious and directly gives the desired value ($(2^{n-1} - 1)⋅2 + 1 = (2^n - 2) + 1 = 2^n - 1$), but it is unreliable because it may actually exceed the range of the data type (in particular, if we try to transform the maximum value of the widest type supported by the C preprocessor, this will lead to an integer overflow and give an incorrect result). Instead, we will take the opposite approach: to achieve a multiple of the block size, let us simply remove the minimum number of bits necessary to achieve that multiple — if $k = 8$, then that is 7 bits ($7 - 7 = 0$, $15 - 7 = 8$).

Our examples have the following forms:

• $127⋅256^0$, 0x7F, and 0b01111111 (8-bit)
• $127⋅256^1 + 255⋅256^0$, 0x7FFF, and 0b0111111111111111 (16-bit)

Since this is the binary number system, the operation can be easily expressed as a logical right shift by 7:

• 0b01111111>>7 → 0b00000000, and 0x7F>>7 → 0x00 (8-bit)
• 0b0111111111111111>>7 → 0b0000000011111111, and 0x7FFF>>7 → 0x00FF (16-bit)

But it is also equivalent to integer division by $2^7 = 128$:

• $\left\lfloor\frac{127⋅256^0}{128}\right\rfloor = \left\lfloor\frac{127}{128}\right\rfloor = 0$ (8-bit)
• $\left\lfloor\frac{127⋅256^1 + 255⋅256^0}{128}\right\rfloor = \left\lfloor\frac{127⋅256 + 255}{128}\right\rfloor = 127⋅2 + \left\lfloor\frac{255}{128}\right\rfloor = 254 + \left\lfloor\frac{128 + 127}{128}\right\rfloor = 255 + \left\lfloor\frac{127}{128}\right\rfloor = 255$ (16-bit)

Subsequent operations correspond to those we described earlier for bytes, with the only difference being that at the end, we will have to add +1 byte to the result to compensate for the removed 7 bits and to correct for the sign bit. Also, we can combine division by $2^7$ with division by $2^8 - 1$ (the maximum digit in base $2^8$): $128⋅255 = 32640$, which can be represented in hexadecimal as 0x7F80. In summary:

>>> (2**7-1)//0x7F80%0xFF*8+8
8
>>> (2**15-1)//0x7F80%0xFF*8+8
16
>>> (2**23-1)//0x7F80%0xFF*8+8
24
>>> (2**31-1)//0x7F80%0xFF*8+8
32
>>> (2**39-1)//0x7F80%0xFF*8+8
40
>>> (2**47-1)//0x7F80%0xFF*8+8
48
>>> (2**55-1)//0x7F80%0xFF*8+8
56
>>> (2**63-1)//0x7F80%0xFF*8+8
64

Actually, we can make the number of digits a multiple of the block size without knowing the exact difference. But before that, let us move on to a generalization, just as we did before.

…to be continued…

---

Integers with an arbitrary width

…to be continued…

How it relates

The first version of the macro, published in 2003, specified a limit of up to 3e+10 for the exponent:

/* Number of bits in inttype_MAX, or in any (1<<b)-1 where 0 <= b < 3E+10 */
#define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

It is a special case (see the last one; 0x3fffffff == 1073741823):

$ ./lognint.py 2 3e+10
The nearest expression on the left  (x = 2^n - 1, where 0 <= n <= 7516192739):
    ((x)//((x)%268435455+1)//268435455%268435455*28+(x)%268435455//((x)%15+1)//15%15*4+3-6//(2+(x)%15))
The nearest expression on the right (x = 2^n - 1, where 0 <= n <= 32212254689):
    ((x)//((x)%1073741823+1)//1073741823%1073741823*30+(x)%1073741823//((x)%31+1)//31%31*5+4-12//(3+(x)%31))

The second version of the macro, published in 2006, specified a limit of up to 2040 for the exponent:

/* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))

It is also a special case (see the first one):

$ ./lognint.py 2 2040
The nearest expression on the left  (x = 2^n - 1, where 0 <= n <= 2039):
    ((x)//((x)%255+1)//255%255*8+7-86//(12+(x)%255))
The nearest expression on the right (x = 2^n - 1, where 0 <= n <= 4598):
    ((x)//((x)%511+1)//511%511*9+(x)%511//((x)%7+1)//7%7*3+2-2//(1+(x)%7))

Therefore, as a consequence, all of Hallvard B. Furuseth's work can be explained by the very same theory on which this generator is based.