C Foundations Lesson 6 of 7

Binary and integer overflow in C

25 min, 4 exercises

Builds on lessons 1 to 5. Start at lesson 1

Learn

Bits and unsigned wrap

A byte is 8 bits, and each bit is 0 or 1. Read as a plain binary number, 8 bits can hold 2 to the power 8 = 256 different patterns, so an unsigned char stores 0 to 255.

00000000 = 0
00000101 = 5     (4 + 1)
11111111 = 255   (128+64+32+16+8+4+2+1)

So what happens if you add 1 to 255? There is no ninth bit to carry into. For unsigned types, C defines the answer: the value wraps around modulo 256, so you get 0. Like a car odometer rolling over.

unsigned char u = 255;
u = u + 1;   // u is now 0

Strictly, u + 1 is worked out as an int, giving 256, and storing 256 back into the 1-byte u keeps only the low 8 bits. Same result, fully defined. Bigger types work the same way: an int here is 4 bytes, 32 bits, so an unsigned int wraps after 4294967295.

Learn

Signed overflow and hex

Signed types are different. Overflowing a signed int is undefined behaviour: the standard makes no promise at all, and optimising compilers really do assume it never happens. Many machines will happen to wrap to a negative number, but you must not rely on it. Use unsigned types when you want wrap-around.

Binary gets long fast, so programmers write bytes in hexadecimal: base 16, digits 0-9 then a-f. One hex digit is exactly 4 bits, so one byte is always two hex digits. 255 is ff, 16 is 10. Print hex with %x, and an unsigned value with %u.

Learn

Reading single bits

Two operators let you look at one bit at a time. x >> i shifts every bit of x right by i places, so the bit you want lands in the lowest position. & 1 then keeps only that lowest bit and clears the rest.

x            = 00000101   (5)
x >> 2       = 00000001
(x >> 2) & 1 = 1          bit 2 of 5 is on

Bits are numbered from 0 on the right. That is how the CPU sees a byte: eight switches, each worth a power of two. The bit printer project prints them all.

Try

Run it: a byte wrapping round

The example is already in the editor. Run it, change one thing, and run it again.

example.c to run
#include <stdio.h>

int main(void) {
    unsigned char u = 250;
    for (int i = 0; i < 8; i++) {
        printf("%u (hex %x)\n", u, u);
        u = u + 1;
    }
    printf("255 in hex is %x, 4096 in hex is %x\n", 255, 4096);
    return 0;
}

Practice

Overflow an unsigned char

Start an unsigned char called fuel at 250. Add 10 to it, then print it with %u. Work out the number on paper first, then see whether the computer agrees.

exercise_1.c to run
#include <stdio.h>

int main(void) {
    unsigned char fuel = 250;
    // add 10, then print
    printf("%u\n", fuel);
    return 0;
}

Practice

Print numbers in hex

Print the numbers 10, 15, 16 and 255, each on its own line, as decimal = hex, like this:

  • 10 = a
  • 15 = f
  • 16 = 10
  • 255 = ff

Use a format code for the hex part rather than typing it.

exercise_2.c to run
#include <stdio.h>

int main(void) {
    printf("%d = %d\n", 10, 10);
    return 0;
}

Practice

Count the 1 bits

Finish int count_ones(unsigned char x) so it returns how many of the 8 bits of x are 1. Use >> and & 1 in a loop over bits 0 to 7. The program should print:

  • 0 has 0 one bits
  • 5 has 2 one bits
  • 170 has 4 one bits
  • 255 has 8 one bits
exercise_3.c to run
#include <stdio.h>

int count_ones(unsigned char x) {
    int count = 0;
    return count;
}

int main(void) {
    printf("0 has %d one bits\n", count_ones(0));
    printf("5 has %d one bits\n", count_ones(5));
    printf("170 has %d one bits\n", count_ones(170));
    printf("255 has %d one bits\n", count_ones(255));
    return 0;
}

Your turn

Highest badge earned

A game save keeps 8 badges in one unsigned char: bit 0 is the easiest badge, bit 7 the hardest, and a 1 means earned. Write int best_badge(unsigned char badges), which returns the number of the highest bit that is 1, or -1 if no badge is earned yet.

On your own. Hints open after your first check.

exercise_4.c to run

  
  

  

  





    
    

    
  

  

    
C, 32-bit: int and pointers are 4 bytes