Bit manipulation · about 50 min

Masks, flags and bit fields

Why this matters

A Unix file's permissions, the options you pass to open(), the status register of a device, the header of a TCP packet, the pixel format of an image: all of them pack several small pieces of information into the bits of one integer. To read and write them you need four basic operations (set, clear, toggle, test) and two techniques (extracting a field and inserting one). After this lesson, code like flags & ~O_NONBLOCK or (hdr >> 4) & 0xF will read as plainly as arithmetic.

Masks

A mask is a value whose 1 bits select the positions you care about. A mask for bit n is 1u << n; a mask for the low w bits is (1u << w) - 1 (for example (1u << 4) - 1 is 0b1111 = 0xF).

The four operations, for a single bit n:

  set     x |=  (1u << n)      OR with 1 forces the bit on, OR with 0 leaves it
  clear   x &= ~(1u << n)      AND with 0 forces it off, AND with 1 leaves it
  toggle  x ^=  (1u << n)      XOR with 1 flips it, XOR with 0 leaves it
  test    (x >> n) & 1u        1 if the bit is on, 0 if off
          or  (x & (1u << n)) != 0

The same operations work with masks of many bits at once: x |= 0xF0 sets bits 4 to 7.

Flags

A flag set gives each yes/no option its own bit, so one integer can hold many options. You define the flags as powers of two, often with an enum:

#include <stdio.h>

enum {
    PERM_READ  = 1u << 0,   /* 001 */
    PERM_WRITE = 1u << 1,   /* 010 */
    PERM_EXEC  = 1u << 2,   /* 100 */
};

void show(unsigned perms)
{
    printf("%c%c%c\n",
           (perms & PERM_READ)  ? 'r' : '-',
           (perms & PERM_WRITE) ? 'w' : '-',
           (perms & PERM_EXEC)  ? 'x' : '-');
}

int main(void)
{
    unsigned p = PERM_READ | PERM_WRITE;  /* combine with | */
    show(p);
    p |= PERM_EXEC;                       /* add one */
    show(p);
    p &= ~PERM_WRITE;                     /* remove one */
    show(p);
    p ^= PERM_READ;                       /* flip one */
    show(p);
    return 0;
}

rw-
rwx
r-x
--x

This is exactly how the operating system works. Unix file modes like 0755 are octal because each octal digit is three bits, rwx, for owner, group and others. And the POSIX open call takes flags combined with |: open(path, O_WRONLY | O_CREAT | O_TRUNC, 0644), which you will use in the systems module.

Testing with & gives the masked value, not 0 or 1: p & PERM_EXEC is 4 when set. That is fine in an if, but if you need an actual 1 (to store or compare), write (p & PERM_EXEC) != 0 or !!(p & PERM_EXEC).

Fields: several bits as one number

A field is a group of adjacent bits that together hold a small number. A 24-bit color 0xRRGGBB has three 8-bit fields:

  bit:  23 ........ 16  15 ......... 8  7 .......... 0
        +--------------+---------------+--------------+
        |   red (8)    |   green (8)   |   blue (8)   |
        +--------------+---------------+--------------+
  0x3366CC:   0x33           0x66           0xCC

Extracting a field is "shift down, then mask": (color >> 8) & 0xFF is green. Inserting fields is "mask, shift up, then OR":

uint32_t color = 0x3366CC;
unsigned r = (color >> 16) & 0xFF;
unsigned g = (color >> 8) & 0xFF;
unsigned b = color & 0xFF;
printf("%u %u %u\n", r, g, b);                   /* 51 102 204 */
uint32_t back = (r << 16) | (g << 8) | b;
printf("%06X\n", back);                          /* 3366CC */

Replacing one field inside a word, without disturbing the others, combines everything: clear the field with an inverted mask, then OR in the new value. To put 0x7 into the 4-bit field at bits 8 to 11:

uint32_t reg = 0xABCD1234;
reg = (reg & ~(0xFu << 8)) | (0x7u << 8);
printf("%08X\n", reg);                           /* ABCD1734 */

  reg              1010 1011 1100 1101 0001 0010 0011 0100   ABCD1234
  ~(0xF << 8)      1111 1111 1111 1111 1111 0000 1111 1111
  AND              1010 1011 1100 1101 0001 0000 0011 0100   ABCD1034
  0x7 << 8         0000 0000 0000 0000 0000 0111 0000 0000
  OR               1010 1011 1100 1101 0001 0111 0011 0100   ABCD1734

Struct bit fields

C can also do the shifting and masking for you. In a struct, a member followed by : width is a bit field that occupies exactly that many bits:

struct pixel {
    unsigned red   : 5;
    unsigned green : 6;
    unsigned blue  : 5;
};

struct pixel px = {31, 63, 0};
printf("%zu %u %u %u\n", sizeof px, px.red, px.green, px.blue);   /* 4 31 63 0 */

The 16 bits of fields fit in one 4-byte unsigned. Assigning a value too big for the field silently keeps only the low bits; gcc warns when it can see it:

warning: unsigned conversion from 'int' to 'unsigned char:6' changes value from '64' to '0' [-Woverflow]

Bit fields are convenient for flags inside your own program's data. But the order of bit fields within a word, and the padding between them, are implementation-defined, so do not use them to match an external format (a file header, a network packet, a hardware register): the explicit shifts and masks above say exactly where every bit goes on every compiler. You also cannot take the address of a bit field.

Common mistakes

flags & !MASK instead of flags & ~MASK. ! is logical NOT and gives 0, wiping every bit.
Forgetting to clear before inserting. word | (value << shift) only adds 1 bits; the old field's 1 bits stay. Clear with & ~mask first.
Not masking the inserted value. If value has more bits than the field, the extra bits spill into the neighbouring field. (value << shift) & mask prevents it.
Signed masks. ~(1 << n) is fine for small n, but 1 << 31 is UB. Use 1u.
(1u << 32) - 1 for a full 32-bit mask. Shifting by the full width is UB. Use 0xFFFFFFFFu or UINT32_MAX, and keep field widths below 32 in general code.

Recap

Set with |=, clear with &= ~, toggle with ^=, test with & (or shift and & 1).
Flags are powers of two combined with |; that is how the OS passes options.
Extract a field with (x >> shift) & mask; replace one with (x & ~(mask << shift)) | ((v & mask) << shift).
Struct bit fields are handy for internal data but their layout is implementation-defined; use explicit masks for external formats.

Going further: run stat -c '%a %A' /etc/passwd in the sandbox terminal to see a mode as octal and as letters, and look at man 2 open for the flag names. Then read /usr/include/x86_64-linux-gnu/bits/fcntl-linux.h to see that O_CREAT and friends are just numbers with single bits set.

Exercises

Exercise 1 · quiz

Match the operation

flags is an unsigned and MASK has a single bit set. Which expression turns that bit off and leaves every other bit unchanged?

Answer

flags & ~MASK

~MASK has every bit set except the one you want to clear; ANDing keeps all other bits as they are and forces that one to 0. | MASK sets it, ^ MASK toggles it, & MASK tests it (keeps only that bit). !MASK is logical NOT, which is just 0 for any nonzero mask, so flags & !MASK clears everything: a common typo.

Exercise 2 · write code

The four basic operations

Implement four functions on bit number n (0 is the least significant bit, n is 0 to 31) of a 32-bit unsigned value:

uint32_t bit_set(uint32_t x, int n);     /* x with bit n turned on        */
uint32_t bit_clear(uint32_t x, int n);   /* x with bit n turned off       */
uint32_t bit_toggle(uint32_t x, int n);  /* x with bit n flipped          */
int      bit_test(uint32_t x, int n);    /* 1 if bit n of x is on, else 0 */

Note that bit_test must return exactly 0 or 1, not the masked value. Use 1u << n (or UINT32_C(1) << n) for the mask, never 1 << n, because 1 << 31 overflows a signed int. main is a small demo that prints:

File: main.c

Starting point

#include <stdio.h>
#include <stdint.h>

uint32_t bit_set(uint32_t x, int n)    { return x; }
uint32_t bit_clear(uint32_t x, int n)  { return x; }
uint32_t bit_toggle(uint32_t x, int n) { return x; }
int      bit_test(uint32_t x, int n)   { return 0; }

int main(void)
{
    uint32_t x = 0x21;              /* 0010 0001 */
    x = bit_set(x, 2);
    printf("%08X\n", (unsigned)x);
    x = bit_clear(x, 2);
    printf("%08X\n", (unsigned)x);
    x = bit_toggle(x, 31);
    printf("%08X\n", (unsigned)x);
    printf("%d %d\n", bit_test(x, 5), bit_test(x, 4));
    return 0;
}

Example

expected output

Hint 1

Set: OR with the mask. Clear: AND with the complement of the mask. Toggle: XOR with the mask.

Hint 2

For test, shift the bit down to position 0 and AND with 1, or write (x & (1u << n)) != 0.

Reference solution

#include <stdio.h>
#include <stdint.h>

uint32_t bit_set(uint32_t x, int n)    { return x | (1u << n); }
uint32_t bit_clear(uint32_t x, int n)  { return x & ~(1u << n); }
uint32_t bit_toggle(uint32_t x, int n) { return x ^ (1u << n); }
int      bit_test(uint32_t x, int n)   { return (x >> n) & 1u; }

int main(void)
{
    uint32_t x = 0x21;              /* 0010 0001 */
    x = bit_set(x, 2);
    printf("%08X\n", (unsigned)x);
    x = bit_clear(x, 2);
    printf("%08X\n", (unsigned)x);
    x = bit_toggle(x, 31);
    printf("%08X\n", (unsigned)x);
    printf("%d %d\n", bit_test(x, 5), bit_test(x, 4));
    return 0;
}

Exercise 3 · write code

Unpack and repack a color

Web colors pack red, green and blue into one number written in hex as RRGGBB. Read colors in hex (with scanf("%x", ...)) until end of input. For each, print the three components in decimal, then the color with red and blue swapped, as six uppercase hex digits. Format, one line per color:

r=51 g=102 b=204 swapped=CC6633

That line is for input 3366CC. Use shifts and masks, not division.

File: main.c

Starting point

#include <stdio.h>

int main(void)
{
    unsigned color;
    while (scanf("%x", &color) == 1) {
        unsigned r = 0, g = 0, b = 0;   /* extract these */
        unsigned swapped = 0;           /* build this */
        printf("r=%u g=%u b=%u swapped=%06X\n", r, g, b, swapped);
    }
    return 0;
}

Example

input

3366CC

expected output

r=51 g=102 b=204 swapped=CC6633

Example

input

FF0000 00ff00 0000FF 000000 FFFFFF 123456

expected output

r=255 g=0 b=0 swapped=0000FF
r=0 g=255 b=0 swapped=00FF00
r=0 g=0 b=255 swapped=FF0000
r=0 g=0 b=0 swapped=000000
r=255 g=255 b=255 swapped=FFFFFF
r=18 g=52 b=86 swapped=563412

Hint 1

Red is the top byte of the three: shift right by 16, then mask with 0xFF.

Hint 2

Build the result by shifting each component into place and ORing: (b << 16) | (g << 8) | r.

Reference solution

#include <stdio.h>

int main(void)
{
    unsigned color;
    while (scanf("%x", &color) == 1) {
        unsigned r = (color >> 16) & 0xFFu;
        unsigned g = (color >> 8) & 0xFFu;
        unsigned b = color & 0xFFu;
        unsigned swapped = (b << 16) | (g << 8) | r;
        printf("r=%u g=%u b=%u swapped=%06X\n", r, g, b, swapped);
    }
    return 0;
}

Exercise 4 · write code

Replace a field

Hardware registers and file formats often pack several small fields into one word. Write

uint32_t set_field(uint32_t word, int shift, int width, uint32_t value);

which returns word with the width bits starting at bit shift replaced by the low width bits of value, leaving all other bits unchanged. width is 1 to 31 and shift + width <= 32. Extra high bits in value must be ignored, not allowed to leak into neighbouring fields.

For example set_field(0xABCD1234, 8, 4, 0x7) returns 0xABCD1734. main reads lines of word shift width value (word and value in hex) and prints the result as 8 uppercase hex digits:

$ echo "ABCD1234 8 4 7" | ./prog
ABCD1734

File: main.c

Starting point

#include <stdio.h>
#include <stdint.h>

uint32_t set_field(uint32_t word, int shift, int width, uint32_t value)
{
    return word | (value << shift);
}

int main(void)
{
    unsigned word, value;
    int shift, width;
    while (scanf("%x %d %d %x", &word, &shift, &width, &value) == 4)
        printf("%08X\n", (unsigned)set_field(word, shift, width, value));
    return 0;
}

Example

input

ABCD1234 8 4 7

expected output

ABCD1734

Example

input

FFFFFFFF 4 8 0
00000000 0 4 FF
FFFFFFFF 28 4 0
12345678 31 1 1
00000000 1 31 7FFFFFFF

expected output

FFFFF00F
0000000F
0FFFFFFF
92345678
FFFFFFFE

Hint 1

A mask of width ones at the bottom is (1u << width) - 1. Shift it up into position.

Hint 2

First clear the field in word with & ~mask, then OR in the new value, itself masked so stray bits cannot escape.

Hint 3

return (word & ~mask) | ((value << shift) & mask);

Reference solution

#include <stdio.h>
#include <stdint.h>

uint32_t set_field(uint32_t word, int shift, int width, uint32_t value)
{
    uint32_t mask = ((UINT32_C(1) << width) - 1) << shift;
    return (word & ~mask) | ((value << shift) & mask);
}

int main(void)
{
    unsigned word, value;
    int shift, width;
    while (scanf("%x %d %d %x", &word, &shift, &width, &value) == 4)
        printf("%08X\n", (unsigned)set_field(word, shift, width, value));
    return 0;
}