7
\$\begingroup\$

Background

The newest version of the C standard, C23, adds preprocessor macros like INT_WIDTH, ULONG_WIDTH, and SIZE_WIDTH that tell you the bit width of various integer types (here, int, unsigned long, and size_t, respectively). However, while the majority of us are stuck with pre-C23 compilers/standard libraries, it would still be nice to have these values available to us.

What we do have easy access to is the numerical limits of the integer types, e.g. INT_MAX, ULONG_MAX, and SIZE_MAX. For unsigned types, these values are guaranteed to be of the form \$2^n - 1\$. If we could extract the \$n\$ from numbers like this, that would give us the width of every (unsigned) integer type.

Objective

Your goal is to write a C preprocessor macro MAX_TO_WIDTH(m) which converts unsigned _MAX values to the corresponding _WIDTH value. More precisely, \$\texttt{MAX_TO_WIDTH}(2^n - 1) = n\$ for all \$n\$ in a "reasonable" range (see below). For example, we need MAX_TO_WIDTH(255) == 8, MAX_TO_WIDTH(4294967295) == 32, etc. Your macro will not be called with other values, so MAX_TO_WIDTH(10) can return a garbage value, or even invalid code.

Because macro substitution works by pasting token sequences without evaluating them, fairly succinct macros can have very large expansions. Therefore, instead of golfing the macro itself, we will be golfing its output.

Rules

  1. Your submission should be a C macro definition like

    #define MAX_TO_WIDTH(m) ...
    

    You may also define and use any helper macros you want to.

  2. MAX_TO_WIDTH(m) must give the correct result for all \$m = 2^n - 1\$, \$n \in [1, 128]\$. Most C preprocessors that I know of only handle up to 64-bit integers, but new architectures like CHERI will have 128-bit pointers (and thus MAX_TO_WIDTH(UINTPTR_MAX) == 128. You should verify that your implementation works up to at least 128 bits, for example by translating it to Python.

  3. For valid inputs, your macro should produce an integer constant expression suitable for use in a preprocessor condition. That means things like this must work:

    #if MAx_TO_WIDTH(255) == 8
    switch (8) {
        case MAX_TO_WIDTH(255):
            break;
        default:
            assert(0);
    }
    #endif
    

    The C preprocessor has slightly different rules than C itself for evaluating expressions (particularly around overflow). The result should be correct in either context. The test cases attempt to validate this for you.

  4. Your macro must properly parenthesize its input and output. If you're unfamiliar with C, this means that macros like

    #define FOO(x) 2 * x + 1
    

    Are bad practice because 2 * FOO(1 + 1) expands to 2 * 2 * 1 + 1 + 1 (a.k.a. 6, not the desired 10). The macro should instead be written

    #define FOO(x) (2 * (x) + 1)
    

    The test cases attempt to validate this for you.

Testing

Add the following code after your macro definition to test it:

/* Check validity in preprocessor conditions */
#if 2 * MAX_TO_WIDTH(1 + 1 + 1) != 4
#error "Expected MAX_TO_WIDTH(3) == 2"
#endif

/* Calculate (1 << n) - 1, without overflow */
#define WIDTH_TO_MAX(n) ((((1ULL << ((n) - 1)) - 1) << 1) + 1)

/* Check that MAX_TO_WIDTH() inverts WIDTH_TO_MAX() */
#define ASSERT_WIDTH(n) _Static_assert(MAX_TO_WIDTH(WIDTH_TO_MAX(n)) == (n), "")

/* Expands to ASSERT_WIDTH(1); ASSERT_WIDTH(2); ...; ASSERT_WIDTH(64); */
#define ASSERT_WIDTH_2(n)  ASSERT_WIDTH(2 * (n) - 1); ASSERT_WIDTH(2 * (n))
#define ASSERT_WIDTH_4(n)  ASSERT_WIDTH_2(2 * (n) - 1); ASSERT_WIDTH_2(2 * (n))
#define ASSERT_WIDTH_8(n)  ASSERT_WIDTH_4(2 * (n) - 1); ASSERT_WIDTH_4(2 * (n))
#define ASSERT_WIDTH_16(n) ASSERT_WIDTH_8(2 * (n) - 1); ASSERT_WIDTH_8(2 * (n))
#define ASSERT_WIDTH_32(n) ASSERT_WIDTH_16(2 * (n) - 1); ASSERT_WIDTH_16(2 * (n))
#define ASSERT_WIDTH_64()  ASSERT_WIDTH_32(1); ASSERT_WIDTH_32(2)
ASSERT_WIDTH_64();

int main(void) {
    int ret[] = {1, 1, 0};
    switch (2) {
        /* Check validity as a constant expression */
        case MAX_TO_WIDTH(3):
            /* Check parenthesization */
            return MAX_TO_WIDTH(3)[ret];
        default:
            return 1;
    }
}

The code should compile without errors (warnings are okay), and run successfully (returning 0), without invoking any undefined behaviour. If you save this code as golf.c, you can check it like this:

user@host$ clang -fsanitize=undefined golf.c -o golf && ./golf || echo FAIL

Scoring

Your score is the number of preprocessing tokens that the test code expands to using your MAX_TO_WIDTH() definition. Lower scores are better. You can use clang's -dump-tokens flag to determine this:

user@host$ clang -fsyntax-only -Xclang -dump-tokens golf.c 2>&1 | wc -l
13877

This score is insensitive to whitespace, comments, and name length, so there's no incentive to golf the implementation in a way that obfuscates it.

Extra credit

If you want, you can calculate the largest \$n\$ for which your \$\texttt{MAX_TO_WIDTH}(2^n - 1)\$ would behave correctly (assuming a hypothetical C implementation with \$n\$-bit integers). Remember, \$n\$ must be at least 128, but it may be (significantly) higher. Each \$n\$ defines a "weight class" (so to speak) which includes all submissions with equal or greater \$n\$ values. For example, with these submissions:

Submitter Score \$n\$
A 12000 128
B 11000 256
C 13000 512

We'd have a leaderboard like this:

Weight class Winner
\$n \ge 128\$ B
\$n \ge 256\$ B
\$n \ge 512\$ C
\$\endgroup\$
8
  • \$\begingroup\$ Unsigned overflow isn't undefined, so you should just be able to use #define WIDTH_TO_MAX(n) ((1ULL << (n)) - 1). \$\endgroup\$
    – Neil
    Mar 12 at 22:34
  • \$\begingroup\$ Shifting by the width of the type (or more) is still undefined though \$\endgroup\$ Mar 12 at 22:36
  • 1
    \$\begingroup\$ Fair enough, you'd have to use #define WIDTH_TO_MAX(n) ((2ULL << (n) - 1) - 1). \$\endgroup\$
    – Neil
    Mar 12 at 22:41
  • \$\begingroup\$ Right, that should work. Do you think it's worth updating the question? It would change the scores a bit but the only answer so far is mine \$\endgroup\$ Mar 12 at 22:56
  • \$\begingroup\$ No, I was just commenting because I noticed it while trying (and failing) to answer the question. \$\endgroup\$
    – Neil
    Mar 12 at 23:33

2 Answers 2

3
\$\begingroup\$

n < 160, score 11925 11661

#define MAX_TO_WIDTH(x) (~0ull / 31 * ((x) >> 4 & ~0ull / 31 / (~0ull / 31 & 31)) / (~0ull / 32) * 5 + 4 - 12 / (3 + (x) % 31))

Try it online! Verify the score!

Explanation: The first part masks out the bits corresponding to 2⁴, 2⁹, 2¹⁴ etc., then counts just those bits by multiplying by a shifted mask and shifting. This value is multiplied by 5. Any remaining bits are extracted via % 31 and these are counted in a similar way to @TavianBarnes' answer by adding 3 and dividing into 12. In fact this can be done for any number of bits up to 8 using the Fibonacci numbers:

2 - 2 / (1 + (x) % 7)
3 - 6 / (2 + (x) % 15)
4 - 12 / (3 + (x) % 31)
5 - 25 / (5 + (x) % 63)
6 - 48 / (8 + (x) % 127)
7 - 91 / (13 + (x) % 255)

For specific values of n the score can be reduced by folding the constants.

n = 128, score 10622 10362

#define MAX_TO_WIDTH(x) (0x8421084210842108421084210842108ull * ((x) >> 4 & 0x1084210842108421084210842108421ull) / 0x8000000000000000000000000000000ull * 5 + 4 - 12 / (3 + (x) % 31))

Can't try it online but Verify the score!

n = 64, score 10473 10209

#define MAX_TO_WIDTH(x) (0x1084210842108421ull * ((x) & 0x842108421084210ull) / 0x800000000000000 * 5 + 4 - 12 / (3 + (x) % 31))

Try it online! Verify the score!

Edit: Saved a bunch from all the scores by removing a two sets of unnecessary parentheses (in some cases I had to switch a right shift to a divide by a power of 2).

\$\endgroup\$
2
\$\begingroup\$

Score: 13877 13613, \$n = 2040\$.

-264 thanks to l4m2

#define CHUNK(m, mask) (m) / ((m) % mask + 1) / mask % mask
#define INTERP(m) 7 - 86 / ((m) % 255 + 12)
#define MAX_TO_WIDTH(m) (CHUNK(m, 255) * 8 + INTERP(m))

This idea is due to Hallvard B. Furuseth on a comp.lang.c post in 2003. It uses this helper function

#define CHUNK(m, mask) (m) / ((m) % mask + 1) / mask % mask

Which is used to make a repeating sequence like this:

$$ \begin{aligned} a_{i,j} & = \texttt{CHUNK}(2^i - 1, 2^j - 1) \\ a_{0,j}, a_{1,j}, a_{2,j}, \ldots & = \underbrace{0, \ldots, 0}_{\text{$j$ times}}, \underbrace{1, \ldots, 1}_{\text{$j$ times}}, \cdots, \underbrace{2^j-2, \ldots, 2^j - 2}_{\text{$j$ times}}, 0, \ldots \end{aligned} $$

You can play around with it in Python to see:

>>> def CHUNK(m, mask):
...     return (m) // ((m) % mask + 1) // mask % mask
... 
>>> def a(i, j):
...     return CHUNK(2**i - 1, 2**j - 1)
... 
>>> [a(i, 2) for n in range(10)]
[0, 0, 1, 1, 2, 2, 0, 0, 1, 1]
>>> [a(i, 3) for n in range(10)]
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3]
>>> [a(i, 4) for n in range(10)]
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2]
>>> [a(n, 5) for n in range(5 * (2**5 - 1))] == \
... [i for i in range(2**5 - 1) for j in range(5)]
True

This sequence has \$j \, (2^j - 1)\$ values before it wraps, meaning

$$ \texttt{CHUNK}(2^i - 1, 2^j - 1) = \lfloor i/j \rfloor \quad \text{for all $i < j \, (2^j - 1)$.} $$

This is almost enough—what we want is \$j \, \lfloor i/j \rfloor + (i \bmod j) = i\$. We can get \$(i \bmod j)\$ in various ways. For now, let's fix \$j = 8\$. We know that \$2^i \pmod {2^8 - 1}\$ will have period 8:

>>> [(2**i - 1) % 255 for i in range(16)]
[0, 1, 3, 7, 15, 31, 63, 127, 0, 1, 3, 7, 15, 31, 63, 127]

And we can brute force a linear interpolation of these that maps them to [0, 1, 2, ...]:

>>> [(7 - 86 // ((2**i - 1) % 255 + 12)) for i in range(16)]
[0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7]

The original post is more like this:

#define CHUNK(m, mask) (m) / ((m) % mask + 1) / mask % mask
#define INTERP(m) 4 - 12 / ((m) % 31 + 3)
#define MAX_TO_WIDTH(m) \
    (CHUNK(m, 0x3fffffffL) * 30 + CHUNK((m) % 0x3fffffff, 31) * 5 + INTERP(m))

Which would have score: 21477, \$n = 30 \cdot (2^{30} - 1) = 32212254690\$.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Brackets besides INTERP(m) is unnecessary \$\endgroup\$
    – l4m2
    Mar 13 at 6:21
  • 1
    \$\begingroup\$ So is the CHUNK one \$\endgroup\$
    – l4m2
    Mar 13 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.