Рубрика: Задачи с собеседований

Предположим, у вас есть 32-битное число, и вы хотите перевернуть его побитово, независимо от знака: 0x00000001 станет 0x80000000, а 0x71643257, или 01110001 01100100 00110010 01010111 в двоичной записи, станет 11101010 01001100 00100110 10001110, или 0xEA4C268E.

Как сделать это наиболее эффективно?

Простейший способ — выполнить итерацию в цикле по всем 32 битам и на каждой итерации брать последний бит с одной из сторон, создавая новое число бит за битом:

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;
}

И это работает, но неэффективно, главным образом из-за самого цикла, который добавляет ветвления. Мы можем немного поиграть с циклом, заменив for на do { … } while, но это мало что изменит. Можно ли вообще избавиться от цикла?

Вообще-то, можно!

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;
}

Никаких ветвлений, никаких циклов, только сдвиги и логические операции.

Разве это не гениально? Какая жалость, что это не мой код! 🙂 Я бы тоже решал эту задачу с помощью цикла.