{{Short description|Data structure that maps one or more adjacent bits}} A '''bit field''' is a data structure that maps to one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected.<ref name="BrummBrumm1988">{{cite book|author1=Penn Brumm|author2=Don Brumm|title=80386 Assembly Language: A Complete Tutorial and Subroutine Library|url=https://books.google.com/books?id=qjkiAQAAIAAJ|date=August 1988|publisher=McGraw-Hill School Education Group|isbn=978-0-8306-9047-3|page=606}}</ref><ref name="Oualline1997">{{cite book|author=Steve Oualline|title=Practical C Programming|url=https://archive.org/details/practicalcprogra00oual_0|url-access=registration|year=1997|publisher=O'Reilly Media, Inc.|isbn=978-1-56592-306-5|pages=[https://archive.org/details/practicalcprogra00oual_0/page/403 403]–}}</ref> A bit field is most commonly used to represent integral types of known, fixed bit-width, such as single-bit Booleans.
The meaning of the individual bits within the field is determined by the programmer; for example, the first bit in a bit field (located at the field's base address) is sometimes used to determine the state of a particular attribute associated with the bit field.<ref name="Miller1992">{{cite book|author=Michael A. Miller|title=The 68000 Microprocessor Family: Architecture, Programming, and Applications|url=https://books.google.com/books?id=6qAkAQAAIAAJ|date=January 1992|publisher=Merrill|isbn=978-0-02-381560-7|page=323}}</ref>
Within CPUs and other logic devices, collections of bit fields called '''flags''' are commonly used to control or to indicate the outcome of particular operations.<ref name="GriffithsAdams2010">{{cite book|author1=Ian Griffiths|author2=Matthew Adams|author3=Jesse Liberty|title=Programming C# 4.0: Building Windows, Web, and RIA Applications for the .NET 4.0 Framework|url=https://books.google.com/books?id=8graYKZ7rhIC&pg=PA81|date=30 July 2010|publisher=O'Reilly Media, Inc.|isbn=978-1-4493-9972-6|pages=81–}}</ref> Processors have a status register that is composed of flags. For example, if the result of an addition cannot be represented in the destination an arithmetic overflow is set. The flags can be used to decide subsequent operations, such as conditional jump instructions. For example, a <syntaxhighlight lang="asm" inline>JE ...</syntaxhighlight> (Jump if Equal) instruction in the x86 assembly language will result in a jump if the Z (zero) flag was set by some previous operation.
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.{{citation needed|date=January 2019}} Bit fields, on the other hand, typically fit within a machine word,<ref name="Miller1992" /> and the denotation of bits is independent of their numerical index.<ref name="Oualline1997" />
==Implementation== Bit fields can be used to reduce memory consumption when a program requires a number of integer variables which always will have low values. For example, in many systems, storing an integer value requires two bytes (16-bits) of memory; sometimes the values to be stored actually need only one or two bits. Having a number of these tiny variables share a bit field allows efficient packaging of data in the memory.<ref name="Mimar1991">{{cite book|author=Tibet Mimar|title=Programming and Designing with the 68000 Family: Including 68000, 68010/12, 68020, and the 68030|url=https://books.google.com/books?id=arFQAAAAMAAJ|year=1991|publisher=Prentice Hall|isbn=978-0-13-731498-0|page=275}}</ref>
In C, native implementation-defined bit fields can be created using <code>int</code>,{{efn|In C, it is implementation-defined whether a bit-field of type int is signed or unsigned. In C++, it is always signed to match the underlying type.}} <code>unsigned int</code>, <code>signed int</code>, <code>_Bool</code> (in C99), <code>_BitInt(N)</code>, <code>unsigned _BitInt(N)</code> (in C23) or other implementation-defined types. In C++, they can be created using any integral or enumeration type; most C compilers also allow this. In this case, the programmer can declare a structure for a bit field which labels and determines the width of several subfields.<ref name="Prata 2007">{{cite book|last=Prata|first=Stephen|title=C primer plus|year=2007|publisher=Sams|location=Indianapolis, Ind|isbn=978-0-672-32696-7|edition=5th}}</ref> Adjacently declared bit fields of the same type can then be packed by the compiler into a reduced number of words, compared with the memory used if each 'field' were to be declared separately.
For languages lacking native bit fields, or where the programmer wants control over the resulting bit representation, it is possible to manually manipulate bits within a larger word type. In this case, the programmer can set, test, and change the bits in the field using combinations of masking and bitwise operations.<ref name="Daggett2013">{{cite book|author=Mark E. Daggett|title=Expert JavaScript|url=https://books.google.com/books?id=MPBZAgAAQBAJ&pg=PA68|date=13 November 2013|publisher=Apress|isbn=978-1-4302-6097-4|pages=68–}}</ref>
==Examples== ===C=== Bit fields can be used inside structs in C and C++.<ref name="Prata 2007"/> <syntaxhighlight lang="c"> #include <stdint.h>
// opaque and show enum Visibility : uint8_t { NO = 0, YES = 1 };
// line styles enum LineStyle : uint8_t { SOLID = 1, DOTTED = 2, DASHED = 3 };
// Colors enum Color : uint8_t { BLACK = 0, RED = 0b001, GREEN = 0b010, BLUE = 0b100, YELLOW = RED | GREEN, // 011 MAGENTA = RED | BLUE, // 101 CYAN = GREEN | BLUE, // 110 WHITE = RED | GREEN | BLUE // 111 };
const char* colors[8] = {"Black", "Red", "Green", "Yellow", "Blue", "Magenta", "Cyan", "White"};
// bit field box properties struct BoxProps { uint32_t opaque : 1; uint32_t fill_color : 3; maybe_unused uint32_t filler_a : 4; // fill to 8 bits
uint32_t show_border : 1; uint32_t border_color : 3; uint32_t border_style : 2;
maybe_unused uint8_t filler_b : 0; // fill to nearest byte (16 bits)
uint8_t width : 4; // Split a byte into 2 fields of 4 bits uint8_t height : 4; };
int main() { BoxProps my_box = { .opaque = YES, .fill_color = RED, .show_border = YES, .border_color = BLUE, .border_style = SOLID, .width = 5, .height = 10 }; } </syntaxhighlight>
The layout of bit fields in a C <code>struct</code> is implementation-defined. For behavior that remains predictable across compilers, it may be preferable to emulate bit fields with a primitive and bit operators: <syntaxhighlight lang="c"> #include <stdint.h>
/** * Each of these preprocessor directives defines a single bit, * corresponding to one button on the controller. * Button order matches that of the Nintendo Entertainment System. */ enum Key : uint8_t { KEY_RIGHT = 0b00000001, KEY_LEFT = 0b00000010, KEY_DOWN = 0b00000100, KEY_UP = 0b00001000, KEY_START = 0b00010000, KEY_SELECT = 0b00100000, KEY_B = 0b01000000, KEY_A = 0b10000000 };
// global state uint8_t gameControllerStatus = 0;
// Sets the gameControllerStatus using OR void onKeyPressed(uint8_t key) { gameControllerStatus |= key; }
// Clears the gameControllerStatus using AND and ~ (binary NOT) void onKeyReleased(uint8_t key) { gameControllerStatus &= ~key; }
// Tests whether a bit is set using AND uint8_t isPressed(uint8_t key) { return gameControllerStatus & key; } </syntaxhighlight>
{{cleanup|reason=moved from Flag field|date=May 2016}}
===Rust=== While Rust lacks native C-style bit fields, this is instead achieved using masks. <syntaxhighlight lang="rust"> impl BoxProps { // Byte 0 const OPAQUE: u8 = 0b0000_0001; const FILL_COLOR_MASK: u8 = 0b0000_1110;
// Byte 1 const SHOW_BORDER: u8 = 0b0000_0001; const BORDER_COLOR_MASK: u8 = 0b0000_1110; const BORDER_STYLE_MASK: u8 = 0b0011_0000;
// Byte 2 const WIDTH_MASK: u8 = 0b0000_1111; const HEIGHT_MASK: u8 = 0b1111_0000; }
impl BoxProps { fn opaque(&self) -> bool { self.raw[0] & Self::OPAQUE != 0 }
fn set_opaque(&mut self, v: bool) { self.raw[0] = (self.raw[0] & !Self::OPAQUE) | (v as u8); }
fn fill_color(&self) -> u8 { (self.raw[0] & Self::FILL_COLOR_MASK) >> 1 }
fn set_fill_color(&mut self, v: u8) { self.raw[0] = (self.raw[0] & !Self::FILL_COLOR_MASK) | ((v & 0b111) << 1); }
fn width(&self) -> u8 { self.raw[2] & Self::WIDTH_MASK }
fn height(&self) -> u8 { (self.raw[2] & Self::HEIGHT_MASK) >> 4 } } </syntaxhighlight>
===Processor status register=== The status register of a processor is a bit field consisting of several flag bits. Each flag bit describes information about the processor's current state.<ref>{{cite book|title=InCider|url=https://books.google.com/books?id=AFpRAAAAYAAJ|date=January 1986|publisher=W. Green|page=108}}</ref> As an example, the status register of the 6502 processor is shown below:
{| class="wikitable" |+ 6502 status register |- ! Bit 7 !! Bit 6 !! Bit 5 !! Bit 4 !! Bit 3 !! Bit 2 !! Bit 1 !! Bit 0 |- | '''N'''egative flag || o'''V'''erflow flag || - || '''B'''reak flag || '''D'''ecimal flag || '''I'''nterrupt-disable flag || '''Z'''ero flag || '''C'''arry flag |}
These bits are set by the processor following the result of an operation. Certain bits (such as the Carry, Interrupt-disable, and Decimal flags) may be explicitly controlled using set and clear instructions. Additionally, branching instructions are also defined to alter execution based on the current state of a flag.
For an instance, after an <code>ADC</code> (Add with Carry) instruction, the <code>BVS</code> (Branch on oVerflow Set) instruction may be used to jump based on whether the overflow flag was set by the processor following the result of the addition instruction.
===Extracting bits from flag words=== A subset of flags in a flag field may be extracted by ANDing with a mask. A large number of languages support the shift operator (<<) where <code>1 << n</code> aligns a single bit to the nth position. Most also support the use of the AND operator (&) to isolate the value of one or more bits.
If the status-byte from a device is 0x67 and the 5th flag bit indicates data-ready. The mask-byte is <code>2^5 = 0x20</code>. ANDing the status-byte 0x67 (<code>0110 0111</code> in binary) with the mask-byte 0x20(<code>0010 0000</code> in binary) evaluates to 0x20. This means the flag bit is set i.e., the device has data ready. If the flag-bit had not been set, this would have evaluated to 0 i.e., there is no data available from the device.
To check the '''n'''th bit from a variable '''v''', perform either of the following: (both are equivalent) <syntaxhighlight lang="c"> bool nth_is_set = (v & (1 << n)) != 0; bool nth_is_set = (v >> n) & 1; </syntaxhighlight>
===Changing bits in flag words=== Writing, reading or toggling bits in flags can be done only using the OR, AND and NOT operations – operations which can be performed quickly in the processor. To set a bit, OR the status byte with a mask byte. Any bits set in the mask byte or the status byte will be set in the result.
To toggle a bit, XOR the status byte and the mask byte. This will set a bit if it is cleared or clear a bit if it is set.
==See also== * {{Annotated link|Binary code}} * {{Annotated link|Bit-band}} * {{Annotated link|Bitboard}} * {{Annotated link|Bit array}} * {{Annotated link|Flag (programming)}} * {{Annotated link|Word (computer architecture)}} * {{Annotated link|Mask (computing)}} * {{Annotated link|Program status word}} * {{Annotated link|Status register}} * {{Annotated link|FLAGS register (computing)}} * {{Annotated link|Control register}}
==Notes== {{noteslist}}
==References== <references/>
==External links== * [http://publications.gbdirect.co.uk/c_book/chapter6/bitfields.html Explanation from a book] * [http://c2.com/cgi/wiki?BitField Description from another wiki] * [https://web.archive.org/web/20080203070726/http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=131 Use case in a C++ guide] * [https://web.archive.org/web/20070428213243/http://libbit.sourceforge.net/ C++ libbit bit library] ([https://sourceforge.net/projects/libbit/ alternative URL]) * [https://graphics.stanford.edu/~seander/bithacks.html Bit Twiddling Hacks]: Several snippets of C code manipulating bit fields
Category:Bit data structures Category:Articles with example C code