Computer programming - Lab 5

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. Create bit pattern Write a function that reads a string of digits c₀c₁c₂c₃... until EOF or whitespace and returns the unsigned number that has, starting with the least significant bit, c₀ bits 0, then c₁ bits of 1, then c₂ bits of 0, etc. Stop when there are no more bits to fill, or fill any remaining bits with the opposite of the last bit specified.

5. 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.

6. 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.

7. Convert between float and double 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).

8. 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).

9. Bitwise addition Write a function that adds two unsigned numbers, bit by bit, using the elementary school algorithm with carry (from LSB to MSB).

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 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.

12. 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.

13. Polynomial division in Z₂ 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.