1. 12-bit ints
An array of bytes (unsigned char) stores unsigned integers,
each represented using 12 bits (two integers fit in three bytes).
Bits are used least significant first, thus the low-order nibble
of the second char in a triple forms the high-order bit of the first number,
and the high-order nibble forms the low-order four bits of the second number.
(A nibble is 4 bits from a byte).
Write a function that takes an array and its byte length and prints
all numbers in hexadecimal.
(This encoding was used for the FAT-12 file allocation table in DOS).
2. Set encoding
Write a function, which given a string (char array terminated by '\0')
returns a 32-bit integer mask which has a 1 for every lowercase letter
found in the string (choose bit positions accordingly).
Use the created bit mask to filter text read from standard input until EOF,
printing only those characters which do not appear in the initial string.
3. Character compression.
A text is represented using only four bits (nibbles) for frequent characters,
as follows: 4-bit values from 1 to 15 represent characters from the
following string: char key[] = " etaoinsrhldcf\n";, a nibble with value zero is followed by two nibbles representing an 8-bit character not in that string. Nibbles are stored least significant first. The end of the text is marked by two null bytes '\0'.
a) Write a function which takes as parameter a char array representing an encoded (compressed) text and prints out the decompressed version
b) Write a function which takes as parameter a string (character array terminated by '\0') and prints out the compressed text
4. The Collatz
conjecture says that for any positive n, the following
sequence of operations will eventually reach 1: if n is even, divide it
by 2; else, if n is odd, compute n = 3n + 1.
a) Tabulate for n = 1 to 1 million the number of steps it takes to reach 1
(the "stopping time") starting from n. Avoid overflow.
Avoid repeating computations.
b) Compute and print from the tabulated values the sequence of numbers
whose stopping time is larger than that of any smaller number, i.e.:
1, 2, 3, 6, 7, 9, ...
5. Write a function that adds two numbers given as arrays of characters (digits), terminated by '\0'. The array for the result and its length are also given as parameters. Do not overflow the result.
6. Implement multiplication of arbitrarily large natural numbers, stored as arrays of digits. Write a function that takes as parameters two such numbers, computes and prints their product.
7. Given two natural numbers m < n, compute and print the digits
in the binary representation of fraction m / n . If the fraction
is periodic, determine its period and print it out between parantheses,
e.g. 1/10 = 0.0(0011) .
Hint: use an array to track remainders you have already seen, as shown in the course slides for base 10.
Extra credit: if n ≤ 64, use bit operations on a uint64_t both
for tracking remainders and constructing the result.
8. Write a function to determine whether a string is an anagram of another string (can be obtained by rearranging its characters). Hint: use a histogram of characters.
9. Write a function that takes as parameter a character array (ended by the null character '\0'), and reverses each word in the array. A word is a sequence of non-whitespace characters. Do not change the spacing between words.