07. Bitwise Operations

Bitwise Operations#

The operators in this note allow us to inspect and manipulate the individual bits of an integer. They are used extensively for packed data, permissions, instruction encodings, device registers, networking and file flags. Before continuing, it is worth being comfortable with binary and hexadecimal notation from Integers.

There are six bitwise operators in C. The worked patterns and conventions here follow the official COMP1521 bitwise-operations notes:

These operators work on the individual columns of a bit pattern. They are not the same as the logical operators &&, || and !, which treat each complete value as either false (0) or true (non-zero).

5 && 6   // 1: both complete values are non-zero
5 & 6    // 4: 0101 & 0110 = 0100

Thinking One Bit at a Time#

Every multi-bit operation is built by applying a one-bit truth table independently to corresponding positions.

Bitwise AND#

AND produces 1 only when both input bits are 1:

For a single bit, the useful identities are:

x & 0 = 0
x & 1 = x

A 0 in a mask clears the corresponding result bit, whilst a 1 allows the original bit to pass through. This makes AND useful for selecting bits:

  00010011    x = 0x13
& 00000111    mask = 0x07
----------
  00000011    result = 0x03

Bitwise OR#

OR produces 1 when at least one input bit is 1:

Its useful identities are:

x | 0 = x
x | 1 = 1

A 1 in the mask forces the result bit on, whilst a 0 preserves the original bit. OR is therefore useful for setting bits:

  00010011    x = 0x13
| 00000111    mask = 0x07
----------
  00010111    result = 0x17

Bitwise XOR#

Exclusive OR produces 1 when the two input bits differ:

Its useful identities are:

x ^ 0 = x
x ^ 1 = the opposite of x
x ^ x = 0

A 1 in the mask flips the corresponding bit, whilst a 0 preserves it:

  00010011    x = 0x13
^ 00000111    mask = 0x07
----------
  00010100    result = 0x14

Applying the same XOR mask twice returns the original value because every selected bit is flipped twice:

$$(x\mathbin{\char94}m)\mathbin{\char94}m=x.$$

Bitwise NOT#

NOT is unary: it flips every bit in its operand.

~00010011 = 11101100

This does not mean “make the number negative”. In two's complement, -x is equivalent to ~x + 1, not merely ~x.

There is also a width-related trap in C. Small integer operands undergo integer promotion before most arithmetic and bitwise operations:

uint8_t x = 0x13;
printf("%x\n", ~x);       // commonly ffffffec, not ec

uint8_t y = (uint8_t)~x;  // truncates back to 8 bits: ec

When reasoning about ~, be explicit about the width of the result you intend to keep.

Bit Masks#

A mask is a bit pattern designed to select particular positions. For one bit at position n, where the LSB is position 0, the mask is:

uint32_t mask = 1u << n;

The unsigned 1u is deliberate. Shifts are easier to reason about when their left operand is unsigned.

Checking a bit#

AND the value with the mask:

bool is_set = (value & (1u << n)) != 0;

The expression before != 0 is either zero or a value whose bit n is set. It is not necessarily exactly 1.

Setting a bit#

OR the value with the mask:

value |= 1u << n;

Clearing a bit#

Invert the mask so that every position is 1 except the bit to clear, then AND:

value &= ~(1u << n);

Toggling a bit#

XOR the value with the mask:

value ^= 1u << n;

The four operations can be remembered by what their masks do:

Constructing Masks#

The difficult part of many questions is not applying the operator; it is constructing the right mask.

The lowest n bits#

For 0 < n < width, the lowest n bits can be set using:

uint32_t mask = (1u << n) - 1;

Why does this work? 1u << n has a single 1 at position n. Subtracting one borrows through every lower position:

1 << 5       00100000
(1 << 5)-1   00011111

A range of bits#

Suppose we want bits low through high, inclusive, with 0 <= low <= high < 32. The number of bits is:

unsigned length = high - low + 1;

First construct length low 1 bits, then move them into position. Using UINT32_MAX also handles the full-width case without ever evaluating the invalid expression 1u << 32:

uint32_t low_mask = UINT32_MAX >> (32 - length);
uint32_t mask = low_mask << low;

For bits 8 through 15:

low 8 ones:     00000000 00000000 00000000 11111111
shift left 8:   00000000 00000000 11111111 00000000

Extracting a range#

Mask away the unwanted bits, then shift the field down to bit 0:

uint32_t extract_range(uint32_t value, unsigned low, unsigned high) {
    // Precondition: 0 <= low <= high < 32.
    unsigned length = high - low + 1;
    uint32_t mask = UINT32_MAX >> (32 - length);
    return (value >> low) & mask;
}

Shifting first is often simpler: the desired low bit becomes bit 0, after which a low-bit mask selects the desired width.

Replacing a range#

Replacing a packed field requires two stages: clear the destination field, then OR in the shifted replacement.

uint32_t replace_range(
    uint32_t value,
    unsigned low,
    unsigned high,
    uint32_t replacement
) {
    // Precondition: 0 <= low <= high < 32.
    unsigned length = high - low + 1;
    uint32_t low_mask = UINT32_MAX >> (32 - length);
    uint32_t field_mask = low_mask << low;

    value &= ~field_mask;
    value |= (replacement & low_mask) << low;
    return value;
}

The replacement & low_mask prevents high bits from leaking outside the destination field.

These examples use UINT32_MAX from <stdint.h>. The stated precondition is still necessary: without it, subtracting the indices can underflow and a shift count can fall outside the range 0 through 31.

Bit Flags#

When several independent yes/no properties must be stored, one bit can represent each property. Each named flag is a power of two:

#define CAN_READ     (1u << 0)
#define CAN_WRITE    (1u << 1)
#define CAN_EXECUTE  (1u << 2)
#define IS_HIDDEN    (1u << 3)

Flags can then be combined using OR:

uint32_t permissions = CAN_READ | CAN_WRITE;

if (permissions & CAN_WRITE) {
    // writing is permitted
}

permissions |= CAN_EXECUTE;   // add a flag
permissions &= ~CAN_WRITE;    // remove a flag

This is precisely why functions such as open in File Systems accept flags combined with |: every constant occupies a distinct subset of bits.

A set represented by bits#

A bitset uses bit n to represent whether integer n belongs to a set. A uint64_t can represent a subset of the values 0 through 63:

uint64_t set = 0;
set |= 1ULL << 4;                 // insert 4
set |= 1ULL << 19;                // insert 19

bool contains_4 = set & (1ULL << 4);
set &= ~(1ULL << 4);              // remove 4

Set operations become bitwise operations:

Shift Operators#

Shifts move a bit pattern whilst keeping the result at a fixed width. Bits which fall off an end are discarded.

Left shift#

value << n moves every bit n positions towards the MSB and inserts zeroes on the right:

00000101 << 2 = 00010100
       5          20

When no significant bit is discarded, shifting an unsigned value left by n multiplies it by $2^n$. It is safer to think of the operation as moving bits, however, because fixed-width overflow may discard high bits:

11000000 << 2 = 00000000    in eight bits

In C, left-shifting an unsigned value is defined modulo one more than the maximum value. Left-shifting a negative signed value is undefined, and even a positive signed shift can be undefined if its mathematical result is not representable. Use unsigned operands for bit manipulation.

Logical right shift#

For an unsigned value, value >> n shifts bits towards the LSB and inserts zeroes on the left:

00010111 >> 2 = 00000101
      23           5

This corresponds to unsigned integer division by $2^n$, with any remainder discarded.

Arithmetic right shift#

An arithmetic right shift copies the sign bit into the newly opened upper positions:

11110000 >> 2 = 11111100

This preserves the sign of a two's-complement value. In C, the result of right-shifting a negative signed integer is implementation-defined. On the MIPS environment used by COMP1521, sra explicitly requests this sign-propagating behaviour.

Bitwise Operations in MIPS#

MIPS provides register and immediate forms of the common bitwise operations:

The immediate forms are convenient for small masks, but their mask field is only 16 bits. li can be used when a full 32-bit mask is needed.

Shifts in MIPS#

The v means that the shift amount is variable, supplied in a register.

Mipsy also accepts rol and ror pseudo-instructions which rotate bits. A rotate returns bits which fall from one end at the other end, rather than discarding them as a shift does. Some later MIPS versions have real rotate instructions, but classic MIPS and C do not provide one universal direct equivalent.

Checking whether an integer is odd#

An integer is odd exactly when its least significant bit is 1:

# $a0 contains n
andi $v0, $a0, 1       # 1 if odd, 0 if even
jr   $ra

In handwritten MIPS this bit test is direct and appropriate. In ordinary C, prefer the readable expression n % 2 != 0 unless the bit itself is genuinely what the program is modelling. A competent compiler can select an efficient bit test without requiring the source to obscure its intent.

Checking an arbitrary bit#

# $a0 = value, $a1 = bit position n
li   $t0, 1
sllv $t0, $t0, $a1     # mask = 1 << n
and  $v0, $a0, $t0     # result is zero or the mask
sne  $v0, $v0, $zero   # normalise to exactly 0 or 1
jr   $ra

Extracting a byte#

To extract byte n from a 32-bit word, shift it down and retain the lowest eight bits:

# $a0 = word, $a1 = byte index 0..3
sll  $t0, $a1, 3       # multiply the byte index by 8 bits
srlv $v0, $a0, $t0
andi $v0, $v0, 0x00FF
jr   $ra

Worked Example: Packed Colour#

Suppose a 32-bit colour is arranged as 0xRRGGBBAA: eight bits each for red, green, blue and alpha.

To extract each component in C:

uint8_t red   = (colour >> 24) & 0xFF;
uint8_t green = (colour >> 16) & 0xFF;
uint8_t blue  = (colour >> 8)  & 0xFF;
uint8_t alpha = colour         & 0xFF;

To replace the green component:

colour &= ~(0xFFu << 16);                 // clear old green
colour |= ((uint32_t)new_green) << 16;    // insert new green

Notice the cast before shifting. If new_green is an 8-bit type, converting it to uint32_t first makes the intended 32-bit shift explicit.

Common Mistakes#

• Confusing & with &&, or | with ||.
• Checking value & mask == 0 without parentheses. Equality binds more tightly than bitwise AND, so write (value & mask) == 0.
• Expecting value & (1u << n) to return exactly 1. It returns either zero or the mask.
• Writing ~mask without considering integer promotion and result width.
• Shifting a signed or negative value when the task is about raw bits.
• Shifting by a count equal to or greater than the width of the promoted left operand.
• Building ((1u << length) - 1) when length may be 32.
• Forgetting to clear a field before ORing in its replacement.
• Using sra when logical zero-fill is required, or srl when a signed value must retain its sign.

Practice#

Given:

uint8_t x = 0x55;   // 01010101
uint8_t y = 0xAA;   // 10101010

Evaluate:

1. x & y
2. x ^ y
3. x | y
4. (uint8_t)~x
5. x >> 1
6. (uint8_t)(y << 2)
7. An expression which extracts bits 3 through 6 of value.

Bit masks reappear in File Systems, where open combines access and creation flags, whilst the consequences of finite bit patterns continue in Floating Point.