What is the most efficient way to store flag values?
A flag is a value used to make a decision between two or more options in the execution of a program. For
instance, the /w flag on the MS-DOS dir command causes the command to display filenames in several
columns across the screen instead of displaying them one per line. Another example of a flag can be seen in
the answer to FAQ III.5, in which a flag is used to indicate which of two possible types is held in a union.
Because a flag has a small number of values (often only two), it is tempting to save memory space by not
storing each flag in its own int or char.
instance, the /w flag on the MS-DOS dir command causes the command to display filenames in several
columns across the screen instead of displaying them one per line. Another example of a flag can be seen in
the answer to FAQ III.5, in which a flag is used to indicate which of two possible types is held in a union.
Because a flag has a small number of values (often only two), it is tempting to save memory space by not
storing each flag in its own int or char.
Efficiency in this case is a tradeoff between size and speed. The most memory-space efficient way to store
a flag value is as single bits or groups of bits just large enough to hold all the possible values. This is because
most computers cannot address individual bits in memory, so the bit or bits of interest must be extracted from
the bytes that contain it.
The most time-efficient way to store flag values is to keep each in its own integer variable. Unfortunately,
this method can waste up to 31 bits of a 32-bit variable, which can lead to very inefficient use of memory.
If there are only a few flags, it doesn’t matter how they are stored. If there are many flags, it might be
advantageous to store them packed in an array of characters or integers. They must then be extracted by a
process called bit masking, in which unwanted bits are removed from the ones of interest.
Sometimes it is possible to combine a flag with another value to save space. It might be possible to use highorder
bits of integers that have values smaller than what an integer can hold. Another possibility is that some
data is always a multiple of 2 or 4, so the low-order bits can be used to store a flag. For instance, in FAQ III.5,
the low-order bit of a pointer is used to hold a flag that identifies which of two possible types the pointer
points to.
advantageous to store them packed in an array of characters or integers. They must then be extracted by a
process called bit masking, in which unwanted bits are removed from the ones of interest.
Sometimes it is possible to combine a flag with another value to save space. It might be possible to use highorder
bits of integers that have values smaller than what an integer can hold. Another possibility is that some
data is always a multiple of 2 or 4, so the low-order bits can be used to store a flag. For instance, in FAQ III.5,
the low-order bit of a pointer is used to hold a flag that identifies which of two possible types the pointer
points to.
Cross Reference:
X.2: What is meant by “bit masking”?
X.3: Are bit fields portable?
X.4: Is it better to bitshift a value than to multiply by 2?
No comments:
Post a Comment