Is using the most significant bit to tag a union considered a bad practice?

Question

Suppose I have the following tagged union:

// f32 is a float of 32 bits
// uint32 is an unsigned int of 32 bits
struct f32_or_uint32 {
    char tag;
    union {
        f32 f;
        uint32 u;
    }
}

If tag == 0, then it is a f32. If tag == 1, then it is a uint32. There is only one problem with that representation: it uses 64 bits, when only 33 should be necessary. That is almost a ´1/2´ waste, which can be considerably when you are dealing with huge buffers. I never use the 32 bits, so I thought in using one bit as the flag and doing this instead:

#define IS_UINT32(x) (!(x&0x80000000))
#define IS_F323(x) (x&0x80000000)
#define MAKE_F32(x) (x|0x80000000)
#define EXTRACT_F32(x) (x&0x7FFFFFF)
union f32_or_uint32 {
    f32 f;
    uint32 u;
}

This way, I am using 31 bits for the value and only 1 for the tag. My question is: could this practice be detrimental to performance, maintainability and portability?

Answer 1

No, you can't do that. At least, not in the general sense.

An unsigned integer takes on 2^32 different values. It uses all 32 bits. Likewise, a float takes on (nearly) 2^32 different values. It uses all 32 bits.

With some care it might well be possible to isolate a bit that will always be 1 in one type and 0 for the other, across the range of values that you actually want to use. The high bit of unsigned int would be available if you decided to use values only up to 2^31. The low bit of float could be available if you didn't mind a small rounding error.

There is a better strategy available if the range of unsigned ints is smaller (say only 23 bits). You could select a high order bit pattern of 1+8 bits that was illegal for your usage of float. Perhaps you can manage without +/- infinity? Try 0x1ff.

To answer your other questions, it's relatively easy to create a new type like this in C++, using a class and some inline functions, and get good performance. Doing it with macros in C would tend to be more invasive of the code and more prone to bugs, but with similar performance. The instruction overhead required to do these tests and perhaps do some mask operations is unlikely to be detectable in most normal usages. Obviously that would have to be reconsidered in the case of a computationally intensive usage, but you can just see this as a typical space/speed trade-off.

Answer 2

Using the high bit is going to be annoying on the most diffuse x86 platform because it's the sign bit and the most significant bit for unsigned ints.

A scheme that's IMO slightly better is to use the lowest bit instead but that requires decoding (i.e. storing a shifted integer):

#include <stdio.h>

typedef union tag_uifp {
    unsigned int ui32;
    float fp32;
} uifp;

#define FLOAT_VALUE 0x00
#define UINT_VALUE  0x01

int get_type(uifp x) {
    return x.ui32 & 1;
}

unsigned get_uiv(uifp x) {
    return x.ui32 >> 1;
}

float get_fpv(uifp x) {
    return x.fp32;
}

uifp make_uiv(unsigned x) {
    uifp result;
    result.ui32 = 1 + (x << 1);
    return result;
}

uifp make_fpv(float x) {
    uifp result;
    result.fp32 = x;
    result.ui32 &= ~1;
    return result;
}

uifp data[10];

void setNumbers() {
    int i;
    for (i=0; i<10; i++) {
        data[i] = (i & 1) ? make_fpv(i/10.0) : make_uiv(i);
    }
}

void printNumbers() {
    int i;
    for (i=0; i<10; i++) {
        if (get_type(data[i]) == FLOAT_VALUE) {
            printf("%0.3f\n", get_fpv(data[i]));
        } else {
            printf("%i\n", get_uiv(data[i]));
        }
        data[i] = (i & 1) ? make_fpv(i) : make_uiv(i);
    }
}

int main(int argc, const char *argv[]) {
    setNumbers();
    printNumbers();
    return 0;
}

With this approach what you are losing is the least significant bit of precision from the float number (i.e. storing a float value and re-reading it is going to lose some accuracy) and only 31 bits are available for the integer.

You could try instead to use only NaNs floating point values, but this means that only 22 bits are easily available for the integers because of the float format (23 if you're willing to lose also infinity).

The idea of using lowest bits for tagging is used often (e.g. Lisp implementations).

Answer 3

Let's talk first about whether this works conceptually. This trick more or less works if you're storing unsigned 32-bit numbers but you know they will never be greater than 231. It works because all numbers smaller than 231 will always have a "0" in the high bit. If you know it will always be 0, you don't actually have to store it.

The trick also more or less works if you are storing floating point numbers that are never negative. For single-precision floating point numbers, the high bit indicates sign, and is always 0 if the number is positive. (This property of floating-point numbers is not nearly as well-known among programmers, so you'd want to document this).

So assuming your use case fits in these parameters, the approach works conceptually. Now let's investigate whether it is possible to express in C.

You can't perform bitwise operations on floating-point values; for more info see [Why you can't] perform a bitwise operation on floating point numbers. So to get at the floating-point number's bit pattern, you need to treat it as a char* array:

typedef uint32_t tagged_t;

tagged_t float_to_tagged(float f) {
  uint32_t ret;
  memcpy(&ret, &f, sizeof(f));
  // Make sure the user didn't pass us a negative number.
  assert((ret & 0x80000000) == 0);
  return ret | 0x80000000
}

Don't worry about that memcpy() call -- any compiler worth it's salt will optimize it away. This is the best and fastest way to get at the float's underlying bit pattern.

And you'd likewise need to use memcpy to get the original float back.

float tagged_to_float(tagged_t val) {
  float ret;
  val &= 0x7FFFFFF;
  memcpy(&ret, &val, sizeof(val));
  return ret;
}

I have answered your question directly because I believe in giving people the facts. That said, I agree with other posters who say this is unlikely to be your best design choice. Reflect on your use case: if you have very large buffers of these values, is it really the case that every single one can be either a uint32 or a float, and there is no pattern to it? If you can move this type information to a higher level, where the type info applies to all values in some part of the buffer, it will most definitely be more efficient than making your loops test the type of every value individually.