C Programming: Basic Exercises

This repository collects a set of programming exercise questions suitable for a first-course in C programming. The exercises are categorized according to language features needed to solve the programs.

Questions

1. Compute the absolute value of a given integer.
2. Swap two half-bytes (nibbles) of a uint8_t.
3. Write a single expression function to check whether a uint32_t is a power of two.
4. Write a function to compute the ceiling of the base-2 logarithm of an unsigned integer.
5. Write a function to compute $e^x$ approximately.
6. Write a function to compute the length of the collatz sequence of a given unsigned integer.
7. Define a struct point and a function to compute the square of the distance from origin.
8. Rot-k encode a given string. Only rotate the letters. Preserve letter-case.
9. Reverse a string in-place.
10. Given an array of integers and a target, check whether there are two elements in the array that sum to the target.
11. Given an array and a value, move all elements with that value to the end of the array and return the length of sub-array not containing that value.
12. From a sorted array, remove all duplicates.
13. Partition an array.
14. Compute the prime factorization of an int.
15. Crypto square.
16. Generate all k-permutations of an n-element array.
17. Generate all k-combinations of an n-element array.

Solutions

Absolute value

This can be done using an if.

#include <stdio.h>

int abs(int x)
{
        if (x >= 0) return x;
        return -x;
}

int main()
{
        printf("|%d| = %d.\n", 5, abs(5));
        printf("|%d| = %d.\n", -5, abs(-5));
        return 0;
}

|5| = 5.
|-5| = 5.

The body of the if always returns. It is considered good practice in such cases to avoid writing an explicit else.

Swap nibbles

We use bitwise shift and or.

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

uint8_t swap_nibble(uint8_t x)
{
        return (x << 4) | (x >> 4);
}

int main()
{
        printf("swap_nibble(%02x) = %02x.\n", 0xad, swap_nibble(0xad));
        return 0;
}

swap_nibble(ad) = da.

For an unsigned integer, all shifts shift in zeroes. For signed integers, right shift shifts in the most significant bit’s value. So this code will not work if we replace unsigned with signed integers.

Check power of two

#include <stdio.h>
#include <stdbool.h>

bool is_pow_2(unsigned int x)
{
        return x * !(x & (x - 1));
}

int main()
{
        printf("is_pow_2(%3u) = %s.\n",  24,  is_pow_2(24) ? "true" : "false");
        printf("is_pow_2(%3u) = %s.\n", 256, is_pow_2(256) ? "true" : "false");
        printf("is_pow_2(%3u) = %s.\n", 255, is_pow_2(255) ? "true" : "false");
        return 0;
}

is_pow_2( 24) = false.
is_pow_2(256) = true.
is_pow_2(255) = false.

Base-two log

We double a number repeatedly until it is not less than x. The number of repetitions is the answer.

#include <stdio.h>
#include <assert.h>

unsigned int log2ceil(unsigned int x)
{
        assert(x > 0);

        unsigned int p = 1;
        unsigned int r = 0;
        while (p < x) {
                p *= 2;
                ++r;
        }

        return r;
}

int main()
{
        printf("log2ceil(%u) = %u.\n", 19340, log2ceil(19340));
        printf("log2ceil(%u) = %u.\n", 16384, log2ceil(16384));
        return 0;
}

log2ceil(19340) = 15.
log2ceil(16384) = 14.

The variables p and r satisfy the property: $2^r = p$, at the beginning and at the end of each iteration of the loop. Such properties are called loop invariants. When the loop is terminated, we have either:

• $p = x$: We know $2^r = p$, so r must be the answer. or,
• $p &gt; x$: We know $p/2 &lt; x$, so we know $2^r-1 < x$ and $2^r &gt; x$. Again, r must be the answer.

Approximate exponential function

We use the Maclaurin series of the exponential function. Here we take a fixed number of terms. A better approach is to detect and stop the loop when the terms become insignificant.

#include <stdio.h>

double e(double x)
{
        const size_t N = 20;

        double r = 1.0;

        for (size_t i = N; i >= 1; --i) {
                r = 1 + x/i * r;
        }

        return r;
}

int main()
{
        printf("e(%.2lf) = %.2lf.\n", 3.0, e(3.0));
        return 0;
}

e(3.00) = 20.09.

Collatz sequence length

A number is odd if and only if its least significant bit is one. We keep a variable len each time we find a new element in the sequence. An assert ensures that n > 0. The program exits immediately otherwise.

#include <stdio.h>
#include <assert.h>

size_t collatz_length(unsigned int n)
{
        assert(n > 0);

        size_t len = 1;

        while (n != 1) {
                if (n & 1) n = 3*n + 1;
                else       n = n/2;
                ++len;
        }

        return len;
}

int main()
{
        printf("collatz_length(%u) = %zu.\n", 2345, collatz_length(2345));
        return 0;
}

collatz_length(2345) = 152.

Sometimes, it helps the reader when the code is aligned as the if and else branches above. But don’t overdo it.

Point

#include <stdio.h>

struct point {
        double x, y;
};

double l2_sq(struct point p)
{
        return p.x*p.x + p.y*p.y;
}

int main()
{
        printf("%.2lf\n", l2_sq((struct point) { .x = 2.0, .y = 3.0 }));
        return 0;
}

13.0

Rot-k encoding

#include <stdio.h>

char *rotk(char *s, size_t k)
{
        char *p = s;
        while (*p) {
                switch(*p) {
                case 'a' ... 'z': *p = 'a' + (*p-'a'+k)%26; break;
                case 'A' ... 'Z': *p = 'A' + (*p-'A'+k)%26; break;
                }
                ++p;
        }
        return s;
}

int main()
{
        char buf[] = "The quick brown fox jumped over the lazy dog.";
        printf("%s\n", rotk(buf, 13));
        return 0;
}

Gur dhvpx oebja sbk whzcrq bire gur ynml qbt.

Reverse string

#include <stdio.h>

char *rev(char *s)
{
        size_t i = 0;
        size_t j = 0;

        while (s[j]) ++j;
        --j;

        while (i < j) {
                char t = s[i];
                s[i] = s[j];
                s[j] = t;
                ++i;
                --j;
        }

        return s;
}

int main()
{
        char buf[] = "abcdefghijklmnopqrstuvwxyz";
        printf("%s\n", rev(buf));
        return 0;
}

Target sum

#include <stdio.h>

struct pair {
        ssize_t i, j;
};

struct pair sum2(int xs[], size_t n, int t)
{
        for (size_t i = 0; i < n; ++i)
                for (size_t j = i+1; j < n; ++j)
                        if (xs[i] + xs[j] == t)
                                return (struct pair) { i, j };
        return (struct pair) { -1, -1 };
}

int main()
{
        int xs[] = { 2, 9, 1, -5, 3, 10, 13 };
        struct pair p = sum2(xs, 7, 8);

        if (p.i >= 0 && p.j >= 0)
                printf("8 = %d + %d.\n", xs[p.i], xs[p.j]);

        return 0;
}

8 = -5 + 13.

Remove element from array

#include <stdio.h>

size_t rem(int xs[], size_t n, int v)
{
        size_t i = 0, j = n-1;

        while (1) {
                while (i < n  && xs[i] != v) ++i;
                while (j >= 0 && xs[j] == v) --j;
                if (i >= j) return i;
                int t = xs[i];
                xs[i] = xs[j];
                xs[j] = t;
        }
}

int main()
{
        int xs[] = { 2, 1, 5, 4, 3, 4, 9, 1, 4, 3, 4, 4 };
        size_t r = rem(xs, sizeof(xs)/sizeof(xs[0]), 4);
        printf("(");
        for (size_t i = 0; i < r; ++i)
                printf("%d, ", xs[i]);
        printf(")\n");
        return 0;
      
}

(2, 1, 5, 3, 3, 1, 9, )

Remove duplicates from sorted array

We do this in-place. We keep two indices into the array:

• i is the next position in the array to be filled.
• j is used to look for the next distinct element.

#include <stdio.h>

size_t uniq(int xs[], size_t n)
{
        if (n == 0) return 0;

        size_t i = 1, j = 1;
        while (j < n) {
                while (j < n && xs[j] == xs[j-1]) ++j;
                if (j < n) xs[i++] = xs[j++];
        }
        return i;
}

int main()
{
        int xs[] = { 1, 1, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6 };
        size_t r = uniq(xs, sizeof(xs)/sizeof(xs[0]));
        printf("(");
        for (size_t i = 0; i < r; ++i) {
                printf("%d, ", xs[i]);
        }
        printf(")\n");

        return 0;
}

(1, 2, 3, 4, 5, 6, )

Partition an array

#include <stdio.h>
#include <stdbool.h>

size_t partition(int xs[], size_t n, bool (*f)(int x))
{
        if (n == 0) return 0;

        size_t i = 0, j = n-1;

        while (1) {
                while (i < n  && !f(xs[i])) ++i;
                while (j >= 0 &&  f(xs[j])) --j;
                if (i >= j) break;
                int t = xs[i];
                xs[i] = xs[j];
                xs[j] = t;
        }

        return i;
}

bool is_even(int x)
{
        return x % 2 == 0;
}

void print_array(int xs[], size_t n)
{
        printf("(");
        for (size_t i = 0; i < n; ++i) printf("%d, ", xs[i]);
        printf(")\n");
}

int main()
{
        int xs[] = { 4, 0, 3, 9, 1, 6, 4, 8 };
        size_t n = sizeof(xs)/sizeof(xs[0]);
        size_t p = partition(xs, n, is_even);
        print_array(xs, p);
        print_array(xs+p, n-p);
        return 0;
}

(1, 9, 3, )
(0, 4, 6, 4, 8, )

Prime factorization

#include <stdio.h>
#include <stdlib.h>

int *prime_factorization(int n)
{
        if (n <= 0) return NULL;

        int *fs = malloc(8 * sizeof(int) * sizeof(int));
        size_t i = 0;
        size_t d = 2;
        while (n > 1) {
                while (n%d == 0) {
                        fs[i++] = d;
                        n /= d;
                }
                ++d;
        }
        fs[i] = 0;
        return fs;
}

void print_pf(int *fs)
{
        if (*fs) printf("%d", *fs++);
        while (*fs)
                printf(" * %d", *fs++);
}

int main()
{
        int *p840 = prime_factorization(840);
        print_pf(p840);
        free(p840);
        return 0;
}

2 * 2 * 2 * 3 * 5 * 7

Crypto square

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

char *normalize(const char *message)
{
        size_t n = strlen(message);
        char *s = malloc(n * sizeof(char));
        size_t j = 0;

        for (size_t i = 0; i < n; ++i)
                switch (message[i]) {
                case 'a' ... 'z':
                case 'A' ... 'Z': s[j++] = tolower(message[i]);
                }
        s[j] = '\0';

        return s;
}

char *encrypt(const char *message)
{
        message = normalize(message);
        size_t n = strlen(message);
        size_t r = 0, c = 1;

        while (r * c < n) {
                if ((c-1) * c >= n)
                        r = c-1;
                else if (c * c >= n)
                        r = c;
                else
                        ++c;
        }

        char *secret = malloc(1 + r * c * sizeof(char));
        size_t i = 0;
        for (size_t x = 0; x < c; ++x) {
                for (size_t y = 0; y < r; ++y)
                        if (y*c + x < n)
                                secret[i++] = message[y*c + x];
                secret[i++] = ' ';
        }
        secret[i] = '\0';

        return secret;
}

int main()
{
        printf("%s\n", encrypt("A man and a dog."));
        return 0;
}

aad mno adg na 

Generate permutations

#include <stdio.h>

void swap(int *a, int *b)
{
        int t = *a;
        *a = *b;
        *b = t;
}

void do_permutations (
        int xs[], size_t n,
        int perm[], size_t k, size_t k1,
        void (*process)(int perm[], int k))
{
        if (n < k1) return;

        if (k1 == 0) {
                process(perm, k);
                return;
        }

        for (size_t i = 0; i < n; ++i) {
                swap(&xs[0], &xs[i]);
                perm[k-k1] = xs[0];
                do_permutations(xs+1, n-1, perm, k, k1-1, process);
                swap(&xs[0], &xs[i]);
        }
}

void permutations (
        int xs[], size_t n,
        int perm[], size_t k,
        void (*process)(int perm[], int k))
{
        do_permutations(xs, n, perm, k, k, process);
}

void print_array(int xs[], size_t n)
{
        printf("(");
        for (size_t i = 0; i < n; ++i)
                printf("%d, ", xs[i]);
        printf(")\n");
}

int main()
{
        int xs[] = { 1, 2, 3, 4 };
        int buf[2];
        permutations(xs, 4, buf, 2, print_array);
        return 0;
}

(1, 2, )
(1, 3, )
(1, 4, )
(2, 1, )
(2, 3, )
(2, 4, )
(3, 2, )
(3, 1, )
(3, 4, )
(4, 2, )
(4, 3, )
(4, 1, )

Generate combinations

#include <stdio.h>

void do_combinations (
        int xs[], size_t n,
        int comb[], size_t k, size_t k1,
        void (*process)(int comb[], size_t k))
{
        if (n < k1) return;

        if (k1 == 0) {
                process(comb, k);
                return;
        }

        comb[k-k1] = xs[0];
        do_combinations(xs+1, n-1, comb, k, k1-1, process);
        do_combinations(xs+1, n-1, comb, k,   k1, process);
}

void combinations (
        int xs[], size_t n,
        int comb[], size_t k,
        void (*process)(int comb[], size_t k))
{
        do_combinations(xs, n, comb, k, k, process);
}

void print_array(int xs[], size_t n)
{
        printf("(");
        for (size_t i = 0; i < n; ++i)
                printf("%d, ", xs[i]);
        printf(")\n");
}

int main()
{
        int xs[] = { 1, 2, 3, 4, 5 };
        int buf[3];
        combinations(xs, 5, buf, 3, print_array);
        return 0;
}

(1, 2, 3, )
(1, 2, 4, )
(1, 2, 5, )
(1, 3, 4, )
(1, 3, 5, )
(1, 4, 5, )
(2, 3, 4, )
(2, 3, 5, )
(2, 4, 5, )
(3, 4, 5, )