Bit twiddling a lot of bits in C

Question

I would like to use binary flags to represent a mathematical set in C, where "Bit i is set" means "item i is in the Set". This is convenient because operations like "union" and "intersection" are trivial to implement ("|" and "&"). However, I want my set to be able to contain more than 32 items. Furthermore, I want my code to work on both 32 and 64 bit machines.

Is there any simple way to manipulate more than one word worth of bits in C? Is there a better way to approach this task?

Answer 1

Yes, you simply define an array of your 32-bit integers. Then you manipulate a specific element of the array.

Given a bit ID from 0 through 255 inclusive (for example), that would be an array:

unsigned int bits[8];

In order to find which element to operate on:

unsigned int index = bitId >> 5; // turns 0..255 into 0..31

To get the masks for a given bit ID:

unsigned int masks[] = {
    0x0001, 0x0002, 0x0004, 0x0008,
    0x0001, 0x0020, 0x0040, 0x0080,
    0x0100, 0x0200, 0x0400, 0x0800,
    0x1000, 0x2000, 0x4000, 0x8000
};
unsigned int mask = masks[bitId & 0x1f];

If you have the uint32_t type available in your implementation, that's probably the safest way to go. Otherwise, there are known methods for using unsigned int using CHAR_BIT and sizeof to actually figure out at runtime how big to make the masks array and what values you should use for discovering the array index and bitmask index.

For example, this snippet from my code library shows how I did it for a character-based bitmask:

static unsigned char bitmask[CHAR_BIT];
void bitsetInit (void) {
        unsigned char mask = 1;
        int i = 0;
        while (i < CHAR_BIT) {
                bitmask[i++] = mask;
                mask <<= 1;
        }
}

and using:

bsp->bits[bitnum/CHAR_BIT] &= ~bitmask[bitnum%CHAR_BIT];
bsp->bits[bitnum/CHAR_BIT] |= bitmask[bitnum%CHAR_BIT];

for clearing and setting bits respectively.

If you wanted to use unsigned int instead of unsigned char you would simply calculate the number of bits for that:

unsigned int UINT_BIT = CHAR_BIT * sizeof (unsigned int);

and use it where I've used CHAR_BIT above (the mask array can be dynamically allocated at runtime if need be).

Answer 2

Gnu multi-precision library provides integer implementation, with very good optimization for integers of arbitrary precision, and also has most useful bit twiddling functionality. (link)

Depending on the specific operations you actually need to perform, there may be some fancy data structures that might do the job a little better. For instance, there's the very clever Disjoint Sets structure, for modeling a set of disjoint sets, which has truly astounding asymptotic performance over the 3 operations it supports.

Answer 3

You could use uint64_t from <stdint.h>. Beyond that, I am afraid you are out of luck as far as & and | are concerned, and should look for a different design (e.g. structs with appropriate functions to handle them, or third-party libraries.).

Answer 4

paxdiablo seems to have given you the correct approach to solve this problem the way you've said you want to solve it.

Is there a better way to approach this task?

Unless you have a specific performance or hardware reason to do your work at a bit-wise level, there might be better ways to represent a set. For example, a linked list or binary tree, who's values are members of the set. Both of these structures can have (effectively) infinite size, and are easy to iterate through.

Just because some set operations are easy to implement with boolean logic does not mean all are. The additional code that depends on your set operations will likely be more clear if you have a set-type interface, rather than a boolean logic (only) interface.

No matter what solution you come up with, I recommend you hide it behind an interface, so you can change your storage solution in the future. You can do this by defining functions which you pass your structure to, and only operating on the structure through those functions.

Answer 5

If you really are satisfied with 32 and 64 bit types, in modern C (aka C99) the typedefs uint_least32_t and uint_least64_t are guaranteed to exist in "stdint.h". In contrast to the exact-width types uint32_t and uint64_t (which are optional) they may correspond to a base type that has width that is wider than the number indicates.

If speed is important you may also use uint_fast32_t and uint_fast64_t which must also exist. They trade speed for size and are supposed to use the corresponding base type that has the "fastest" support on the target machine. The blow up for data may be substantial though. E.g. on my 64 bit ubuntu all these "fast" types are 64 bit types.

If you use gcc you'd also have __uint128_t on 64 bit machines as an extra service.