Supozu oni havas 32-bitan nombron kaj volas inversigi ĝin bite, sendepende de la signo; 0x00000001 fariĝos 0x80000000, kaj 0x71643257, aŭ 01110001 01100100 00110010 01010111 en binara formo, fariĝos 11101010 01001100 00100110 10001110, aŭ 0xEA4C268E.
Kiel fari tion plej efike?
La simpla vojo estas ripeti en buklo tra la 32 bitoj kaj en ĉiu iteracio preni la lastan biton de unu flanko kaj konstrui novan nombron bito post bito:
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;
}Kaj ĝi funkcias, sed ne estas efika, ĉefe pro la buklo mem, kiu enkondukas branĉojn. Ni povas iom ludi kun la buklo, anstataŭigante for kun do { … } while, sed tio ne multe helpos. Ĉu ekzistas vojo tute forigi la buklon?
Fakte, jes!
Observu kun respekto:
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;
}Neniuj branĉoj, neniuj bukloj, nur ŝovoj kaj logikaj operacioj.
Ĉu ne estas genia? Kia domaĝo, ke ĝi ne estas mia kodo! 🙂 Mi ankaŭ solvintus la problemon per buklo.
