Encodings

An encoding is a rule that maps values to bit patterns. A fixed-width encoding has a finite number of patterns, so it cannot represent every mathematical value. When a value does not fit, the language or library must define what happens: wrap around, report an error, round, or refuse the conversion.

Do not confuse a value with its encoding. The number 65 and the character A are different concepts even though ASCII assigns the same code point to them. Likewise, the bytes of a signed integer and the bytes of an unsigned integer can be identical while their interpreted values differ.

Integer

An unsigned w-bit integer uses the bits as a binary positional number. For example, 00000101 is \(2^2 + 2^0 = 5\). With w bits, unsigned values range from \(0\) to \(2^w - 1\). Arithmetic is performed modulo \(2^w\): after \(255\) comes \(0\) in an 8-bit unsigned type. (11111111 + 00000001 = 00000000)

Signed integers on the machines used in this course use two’s complement. For a w-bit signed value, the range is \(-2^{w-1}\) through \(2^{w-1}-1\). The highest bit contributes a negative weight, so the pattern for -1 is all ones. Two’s complement makes addition and subtraction use the same circuitry for signed and unsigned values.

The C17 standard permits more than one signed representation, although two’s complement is used by modern desktop systems. Rust specifies two’s-complement signed integers. When exchanging binary data, choose an explicit width such as uint32_t or u32; plain int is not a portable file format.

Here the bit pattern is preserved while the interpretation changes:

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

int main(void) {
    uint32_t u = UINT32_MAX;
    printf("u + 1 = %" PRIu32 "\n", u + 1);

    int32_t n = -1;
    printf("same bits as unsigned = %" PRIu32 "\n", (uint32_t)n);
}

fn main() {
    let u = u32::MAX;
    println!("u + 1 = {}", u.wrapping_add(1));

    let n: i32 = -1;
    println!("same bits as unsigned = {}", n as u32);
}

Unsigned overflow is defined modulo the width in both examples. In C, signed overflow is undefined behavior; the compiler may assume it never happens and optimize based on that assumption. In Rust, a + b checks for overflow in debug builds and can panic, while a release profile may use wrapping behavior. Rust makes the desired policy explicit with checked_add, saturating_add, and wrapping_add.

Bitwise operations work directly on bits: & keeps bits set in both operands, | keeps bits set in either operand, ^ keeps bits that differ, and ~ flips every bit. A left shift usually multiplies an unsigned value by a power of two when no significant bit is lost. Right shift of an unsigned value fills with zeroes; right shift of a signed negative value is language- and implementation-specific in C, while Rust defines an arithmetic right shift for signed integers.

Note

SAR vs. SHR

SAR, Shift Arithmetic Right, fills with the value of the sign bit. SHR, SHift logical Right, fills with zeroes. For signed negative integers, most C compilers do SAR for them.

Mixed signed and unsigned arithmetic is a common C surprise. The usual arithmetic conversions may convert a negative int to a very large unsigned value. Rust refuses to compare different integer types until the programmer writes an explicit conversion. Prefer one integer type for an expression and use checked conversions at boundaries.

For the exact rules, see C17 integer representations and conversions, sections 6.2.6.2 and 6.3.1.3, the Rust Reference: Numeric types, and the Rust book’s integer chapter.

Real Number

Computers cannot store most real numbers exactly with a finite number of bits. A floating-point value is similar to scientific notation, but its base is usually 2:

\(value = (-1)^{sign} * {significand} * 2^{exponent - bias}\)

Tip

By contrast, 10 base scientific notation could be written as:

\(value = (-1)^{sign} * {significand} * 10^{exponent}\)

IEEE 754 binary32 (float in common C implementations and f32 in Rust) has 1 sign bit, 8 exponent bits, and 23 fraction bits. Binary64 (double and f64) has 1 sign bit, 11 exponent bits, and 52 fraction bits. The exponent is stored with a bias so that ordinary positive and negative exponents can be compared as unsigned fields. There are also encodings for positive and negative zero, subnormal numbers close to zero, positive and negative infinity, and NaN (not a number).

Tip

According to IEEE 754, the bias of a k-bits exponent floating-point value is \(2^{k-1} - 1\).

The decimal value 0.1 has no finite binary expansion, so converting it to binary64 rounds it to the nearest representable value. Repeated operations accumulate rounding error, and floating-point addition is not generally associative: (a + b) + c can differ from a + (b + c).

Note

Floating-point precision issues are one of the main problems currently facing deep learning frameworks and deep learning optimization. The main reason is the non-associativeness of floating-point operations.

For comparisons, use a tolerance chosen for the scale and meaning of the calculation, or compare an exact invariant instead. There is no single epsilon that is correct for every program. NaN is especially unusual: it is not equal to itself, so use isnan in C or is_nan in Rust when testing for it.

The authoritative specification is the IEEE 754-2019 standard. For language-specific behavior, consult the C floating-point clauses in N1570 and the Rust primitive f64 documentation.

Character

Text is encoded too. A character set assigns abstract characters to numbers called code points. An encoding turns code points into bytes. ASCII assigns values to 128 basic characters. Unicode assigns code points to characters from many writing systems, and UTF-8 encodes a Unicode code point using one to four bytes while preserving ASCII as a prefix-compatible subset.

Tip

UTF-8 is currently the most widely used character encoding.

#include <stdio.h>
#include <string.h>

int main(void) {
    const char ascii[] = "A";
    const unsigned char utf8[] = "\xC3\xA9"; /* UTF-8 for U+00E9 */

    printf("ASCII: sizeof = %zu, strlen = %zu\n",
           sizeof ascii, strlen(ascii));
    printf("UTF-8: bytes = %zu, strlen = %zu\n",
           sizeof utf8 - 1, strlen((const char *)utf8));
}

fn main() {
    let ascii = "A";
    let letter = "\u{00E9}"; // U+00E9, encoded as two UTF-8 bytes

    println!("ASCII: bytes = {}, chars = {}", ascii.len(), ascii.chars().count());
    println!("UTF-8: bytes = {}, chars = {}", letter.len(), letter.chars().count());
}

For the standards behind these choices, read the Unicode Core Specification, Chapter 3, RFC 3629: UTF-8, the C17 string library clauses in N1570, and the Rust documentation for str.