Defining smallest possible sized macro in C

Question

I want to define a boolean macro in C that uses less than 4 bytes. I have looked into this, and maybe it is possible to define an asm macro, with gcc, that could be less. It is important that the definition will be small because I will have tens of thousands of matrices which hold these boolean values, and it is important that they can be as memory efficient as possible. Ideally, I want to define a 4-bit, or 8-bit macro that represents true and false, and will evaluate as such in an if-statement.

Edit:

When I define a macro

#define True 0
#define False !True

and then print the size, it returns a size of 4 bytes, which is very inefficient.

Edit2:

I just read up on bitpacking, and however little bits I could have for a boolean would be best. I'm just not too sure how to bitpack a struck that has the size of a few bits.

Edit3:

#include <stdio.h>
#include <string.h>

#define false (unsigned char(0))
#define true (!false)

int main() {
    if (true) {
        printf("The size of true is %d\n", sizeof(true));
    }
}

gives the following output

test.c: In function ‘main’:
test.c:8:9: error: expected ‘)’ before numeric constant
test.c:9:51: error: expected ‘)’ before numeric constant

Answer 1

Try this instead for your macros:

#define false ((unsigned char) 0)
#define true (!false)

This won't fix your space needs though. For more efficient storage, you need to use bits:

void SetBoolValue(int bitOffset, unsigned char *array, bool value)
{
    int index = bitOffset >> 3;
    int mask = 1 << (bitOffset & 0x07);

    if (value)
        array[index] |= mask;
    else
        array[index] &= ~mask;
}

bool GetBoolValue(int bitOffset, unsigned char *array)
{
    int index = bitOffset >> 3;
    int mask = 1 << (bitOffset & 0x07);

    return array[index] & mask;
}

Where each value of "array" can hold 8 bools. On modern systems, it can be faster to use a U32 or U64 as the array, but it can take up more space for smaller amounts of data.

To pack larger amounts of data:

void SetMultipleBoolValues(int bitOffset, unsigned char *array, int value, int numBitsInValue)
{
    for(int i=0; i<numBitsInValue; i++)
    {
        SetBoolValue(bitOffset + i, array, (value & (1 << i)));
    }
}

And here would be a driver:

int main(void)
{
    static char array[32];  // Static so it starts 0'd.
    int value = 1234;  // An 11-bit value to pack

    for(int i=0; i<4; i++)
        SetMultipleBoolValues(i * 11, array, value, 11);  // 11 = 11-bits of data - do it 4 times

    for(int i=0; i<32; i++)
       printf("%c", array[i]);

    return 0;
}

Answer 2

If you are using this in a structure, then you will want to use a bit field.

struct {
    unsigned flag : 1;
    /* other fields */
};

If you are wanting an array of boolean values, you should implement a bit vector (I was about to implement one, but Michael Dorgan's already done it).

Answer 3

First of all, there's no storage associated with your macros; they expand to the integer constants 0 and 1. The sizeof evaluates to 4 because the expressions have integer type. You can certainly assign those values to objects of smaller type (short or char).

For me, life got a lot simpler when I stopped using TRUE and FALSE macros¹. Remember that in C, a zero-valued integral expression evaluates to false, and all non-zero-valued integral expressions evaluate to true.

If you want to store values into something smaller than 8 bits, then you're going to have to do your own bit packing, something like

#define TEST(x,bit) ((x) & (1 << (bit)))
#define SET(x,bit) ((x) |= (1 << (bit)))
#define CLEAR(x,bit) ((x) &= ~(1 << (bit)))  

The smallest useful type for this is unsigned char. So if you need to store N single-bit values, you need an array of N/CHAR_BIT+1 elements. For example, to store 10 single-bit boolean values, you need 2 eight-bit array elements. Bits 0 through 7 will be stored in element 0, and bits 8 through 10 will be stored in element 1.

So, something like

#define MAX_BITS 24
unsigned char bits[MAX_BITS / CHAR_BIT + 1];

int bit = ...;

SET(bits[bit/CHAR_BIT], bit % CHAR_BIT);

if ( TEST(bits[bit/CHAR_BIT], bit % CHAR_BIT) )
{
  // do something if bit is set
}

CLEAR(bits[bit/CHAR_BIT], bit % CHAR_BIT);

No warranties express or implied; I don't do a lot of bit twiddling. But hopefully this at least points you in the right direction.

---

^{1. The precipitating event was someone dropping a header where TRUE == FALSE. Not the most productive afternoon.}

Answer 4

You should probably just use an unsigned char, it will be the smallest individually addressable type:

typedef unsigned char smallBool;

smallBool boolMatrix[M][N];

The above will use M * N bytes for the matrix.

Of course, wasting CHAR_BIT - 1 bits to store a single bit is ... wasteful. Consider bit-packing the boolean values.