— Arthur Schopenhauer
Winter is definitely approaching. The days are getting shorter and temperatures are dropping. Isn’t this a wonderful time for doing code katas? Sitting in your easy chair, in front of a fireplace, serenely coding away in your favorite editor.
Today, we dip once more into the realm of low-level embedded programming. Your primary job is to write code that reverses the bits of an integer. For instance, reversing the 8-bit integer value 139 (10001011) yields a new value of 209 (11010001).
Sounds simple, doesn’t it? But it’s not just about coding a bit-reversing routine, that wouldn’t teach you enough lessons. You’ll also practice unit testing, code tuning and — if you like — assembly language programming, cross-compilation, and remote debugging along the way.
The goal is not to find the best/fastest algorithm possible. Instead, the emphasis is on exercising your programming muscle and learning new things. Don’t rush this kata, rather consider it a mini project. Do the research, be persistent. Try and fail and become better. Take your time, I did it over a period of three weeks. Now, without further ado, let’s get (gently) started.
1. Implement a bit reversing function in a dynamic programming language (eg. Perl, Ruby, Python).
a) Decide on a suitable interface, eg. in Python, it could look like this:
1 2 3 4 5 6 7 8 |
def reversebits(max_bits, value): """ Reverses the order of bits of given integer. max_bits -- Bit-width of 'value' (there can be leading 0 bits in 'value') value -- The actual value that is to be reversed. """ |
b) Implement a dummy version of ‘reversebits’ that simply returns 0.
c) Implement a couple of test cases, run them against the dummy version and watch them fail, eg.
1 2 3 4 5 6 |
reversebits(8, 0x01) == 0x80 reversebits(32, 0x01) == 0x80000000 reversebits(16, 0xFFFF) == 0xFFFF0000 : |
d) Implement a straightforward solution (‘reversebits1’) that passes the unit tests.
e) Add more unit tests to gain better confidence in your solution.
f) Measure the execution time of ‘reversebits1’.
g) Be creative, find other solutions. Optimize for speed, optimize for shortest code (in terms of characters typed). Measure and compare the execution times.
h) What if ‘max_bits’ is smaller than the total number of bits already taken-up by ‘value’? For instance
1 2 3 |
reversebits(3, 0xFFFF) # 3 bits vs. 16 bits |
In this case, only the first ‘max_bits’ of ‘value’ shall be reversed and the remaining upper bits shall be discarded:
1 2 3 4 |
reversebits(3, 0xFFFF) == 3 reversebits(3, 0x13) == 6 |
Adapt your code accordingly. Probably, some of your solutions already behave correctly and need no modifications.
2. Port your code and unit tests to C/C++
a) Decide on a suitable interface. It’s OK if you use a fixed-bit unsigned integer data type for the value to be reversed, as long as it supports at least 32 bits, eg.
1 2 3 |
uint32_t reversebits(uint32_t max_bits, uint32_t value); |
b) Measure execution times and compare them against the execution times from 1.
c) Play with various compiler optimization settings. How do they impact the timings?
d) Bonus: Implement a bit reversal function in x86 assembly language.
3. Port your code and tests from 1. and 2. to a Raspberry Pi
a) Don’t have a Pi? Find out how to emulate one on your PC.
b) Measure and compare execution times using various optimization settings.
c) Bonus: Implement a bit reversal function in ARM assembly language.
d) Bonus: Want to learn even more? Build your own cross toolchain (hint: ‘crosstool-ng’) and build the Pi code on a regular PC. Debug the code remotely over a TCP connection (hint: ‘gdbserver’, ‘gdb-multiarch’).
I certainly learned a lot by doing this kata. Far more, than I can possible tell here without risking to bore you and/or spoil all the fun. Nevertheless, I uploaded my work to GitHub. Have a peek in case you get stuck, need some inspiration or are just curious.