1. Nibbles
A nibble is a group of 4 bits. Write a function that given an unsigned n
a) returns the value with the nibbles placed in reverse order
b) returns the value with the bits in each nibble reversed
2. Consecutive bits Write a function that given an unsigned n returns the number of segments of consecutive equal bits in the binary representation of n. Example: 000100 has three segments: 000, 1, 00.
3. Every other bit
a) Write a function that takes a 32-bit unsigned and returns the 16-bit
number formed by the bits in even positions. I.e., if we label the bits
...ba9876543210, return the number formed by bits ...a86420 .
b) The same problem, but place the bits in reverse order.
4. Base 32 We can write a number in base 32, continuing to use letters after 'F'. Write a function that takes an unsigned and prints it in base 32.
5. Bitwise addition Write a function that adds two unsigned numbers, bit by bit, using the elementary school algorithm with carry (from LSB to MSB).
6.Convert between float and double
A double has 64 bits, of which 52 for mantissa and 11 for the exponent, represented with a bias of 1023.
a) Write a function that converts a float to a double, processing the bit representation.
b) Write a function that converts a double to a float. If the value is too large to be represented, return ± INFINITY (from math.h).
7. Fractional part
Write a function that takes as parameter a float, and returns its fractional part (the difference to the number truncated towards zero). Use bitwise operators.
Hint: examine the code for truncating a number written in class.
8. Round float
Write a function that rounds of a float to the next int, using
its bit representation. If the fractional part is 0.5,
round away from zero.
Hint: examine the code for truncating a number written in class.
9. Rational to float
Write a function that takes two unsigned numbers m and n
and returns m/n as a float.
Hint: Obtain the integer part first. Then follow the grade-school division algorithm, but in base 2 (doubling the dividend every time instead of multiplying by 10), and accumulate the quotient bits (1 or 0). You need a total of 24 bits for integer and fractional part (starting from the most significant 1 bit, which will become the implicit 1 in front of the mantissa).
10. Bitwise multiplication Write a function that multiplies two unsigned 32-bit integers, returning a 64-bit unsigned. Iterate over each bit of one number, adding the other one shifted by the appropriate number of bits. (You may use regular addition).
11. Floating-point multiplication Write a function that multiplies two floats, returning a) a float; b) a double. Add exponents. Multiply mantissas as integers (after or-ing with the implicit 1), then shift the result, round and adjust the exponent if needed. Cast one operand to 64 bits before multiplying.
12. Floating-point addition
Write a function that adds two positive float numbers by processing
their bit representation.
Hint: Find the larger of the two exponents and shift the other mantissa (after adding the implicit 1) right by the exponent difference (so it the bits of both correspond to the same powers of 2). Add the mantissas,
and do any rounding or exponent correction.
13. Floating-point inverse Write a function that given a nonzero float x returns 1/x manipulating its bit representation. Use step-by-step division with the mantissa.
14. Polynomial division in Z2
A polynomial with with coefficients 0 or 1 can be represented as an integer
(each bit is the coefficient for the corresponding power).
a) Write a function that divides two polynomials and returns the result
(all represented as above).
b) The bits in a sequence of bytes read from input can be viewed as a
polynomial, with most significant coefficient first. Write a function that
divides this polynomial (read until end of input) by a given 32-bit polynomial, and returns the remainder. This is used in various CRC computations.