In Fortran, variables which start with letters from I to N, by default are allocated with type „integer”, and those which start with any other letter get the type „real”. The programmer could override the default allocation by declaring the type of the variable explicitly. That led to the following joke:
In Fortran, God is real (unless declared integer).
What I do love about IKEA is their faith in people.
Look at the Variera pot lid holder. The entire assembly manual consists of just one step: „Screw 14 big thingies onto the little thingies”. And on top of that they added a thoughtful little comic strip: „Confused by the instructions? Call us, we’ll help!”
Guys, do you really believe that if someone managed to get confused by these instructions, they’d be able to call you?..
Let’s say you have a 32-bit number and you want to reverse it bitwise, regardless of the sign; 0x00000001 will become 0x80000000, and 0x71643257, or 01110001 01100100 00110010 01010111 in binary, will become 11101010 01001100 00100110 10001110, or 0xEA4C268E.
How do you do it in the most efficient way?
The trivial way is to iterate in a loop over 32 bits and on every iteration get a last bit from one of the ends, creating a new number bit by bit:
unsigned reverseBits(unsigned n) {
unsigned result = 0;
for (int i = 0; i < 32; ++i) {
// Extract the least significant bit of `n` and shift it to the correct position
result = (result << 1) | (n & 1);
// Shift `n` to process the next bit
n >>= 1;
}
return result;
}And it works, but it is not efficient, mainly because of the loop itself, which introduces branches. We can play a bit with the loop, replacing for with do { … } while, but it will not save much. Is there a way to remove the loop altogether?
As a matter of fact, yes!
unsigned reverse(unsigned x) {
x = ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
x = ((x & 0x33333333) << 2) | ((x >> 2) & 0x33333333);
x = ((x & 0x0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F);
x = (x << 24) | ((x & 0xFF00) << 8) |
((x >> 8) & 0xFF00) | (x >> 24);
return x;
}No branches, no loops, only shifts and logical operations.
Isn’t it genious? What a pity it’s not my code! 🙂 I also would solve the problem with the loop.