Bit field

A bit field is a common idiom used in computer programming to compactly store a value as a short series of bits. A bit field is most commonly used to represent integral types of known, fixed bit-width. Perhaps the most well known usage of bit-fields is to represent single bit flags, with each flag stored in a separate bit.

A bit field is distinguished from a bit array in that the latter is used to store a large set of bits indexed by integers and is often wider than any integral type supported by the language. Bit fields, on the other hand, typically fit within a machine word, and the denotation of bits is independent of their numerical index.

Examples

Example implementation in C:

#define PREFERENCE_LIKES_ICE_CREAM (1 << 0) /* 0x01 */
#define PREFERENCE_PLAYS_GOLF      (1 << 1) /* 0x02 */
#define PREFERENCE_WATCHES_TV      (1 << 2) /* 0x04 */
#define PREFERENCE_READS_BOOKS     (1 << 3) /* 0x08 */

unsigned char preference;

void set_preference(unsigned char flag) {
    preference |= flag;
}

void reset_preference(unsigned char flag) {
    preference &= ~flag;
}

unsigned char get_preference(unsigned char flag) {
    return (preference & flag) != 0;
}

Instead of using hardcoded numerical representations for the powers of two (0x08), the use of the bit shift operator (1 << 3) with an incrementing shift operand is recommended for easier readability.

Kernighan and Ritchie's book, The C Programming Language, describes a method for defining and accessing fields directly. Using this method, bitwise operators are not needed as bit members can be accessed the same as struct members. An example using a struct follows:

struct preferences {
    unsigned int likes_ice_cream : 1;
    unsigned int plays_golf : 1;
    unsigned int watches_tv : 1;
    unsigned int reads_books : 1;
}; 

struct preferences fred;

fred.likes_ice_cream = 1;
fred.plays_golf = 1;
fred.watches_tv = 1;
fred.reads_books = 0;

if (fred.likes_ice_cream == 1)
    /* ... */

However, bit members in structs have potential practical drawbacks. First, the ordering of bits in memory is cpu dependent and memory padding rules can vary between compilers. In addition, less well optimized compilers sometimes generate poor quality code for reading and writing bit members and there are potentially thread safety issues relating to bit fields because most machines cannot manipulate arbitrary sets of bits in memory, but must instead load and store whole words . e.g. the following would not be thread-safe, in spite of the use of a mutex for each member:

struct foo {
    int flag : 1;
    int counter : 15;
};

struct foo my_foo;

/* ... */

/* in thread 1 */

pthread_mutex_lock(&my_mutex_for_flag);
my_foo.flag = !my_foo.flag;
pthread_mutex_unlock(&my_mutex_for_flag);

/* in thread 2 */

pthread_mutex_lock(&my_mutex_for_counter);
++my_foo.counter;
pthread_mutex_unlock(&my_mutex_for_counter);

The root of the problem is that on most machines it is impossible to load and store flag and counter separately, when both are stored in the same word. In order for this to be thread-safe you should use a single mutex to protect both flag and counter, instead of two.

Homogeneity and mathematical structure

In the examples above, the individual power-of-two values are declared as macros (ending up being the machine word). Since bitfields are by essence destined to be combined with the bitwise OR operator, such code

enum preference {
        preference_likes_ice_cream = 1<<0,
        preference_plays_golf = 1<<1,
        preference_likes_watching_tv = 1<<2,
        preference_reads_books = 1<<3,
};

fails the type-safety principle when combining preference_plays_golf|preference_likes_ice_cream, that does not belong to the enumeration.

Quantities defined as the combination of bits are actually elements of the elementary abelian group (Z/2Z)ⁿ; and the relation defined as a<=b when a&b=a only creates a partial order (1011b is greater than 1010b but 1011b and 1101b are not comparable).

This remark is of interest when designing variable importance debug channels (from `informative' to `fatal'); the regular integer comparison cannot be used to filter out part of the messages.

Nevertheless, a bit field can be safely and elegantly implemented using a bit array where the bit indices for each flag are values of an enumerated type (like the EnumSet class in Java); this avoids the dangers of direct bitwise manipulations.

See also

• Bitboard, used in chess and similar games.
• Bit array
• Flag word

External links

• Explanation from a book
• Description from another wiki
• Use case in a C++ guide
• bit library

References