Мог кто-то помогать объяснить, что этот C делает один лайнер?
Я могу обычно выяснять большую часть кода C, но этот находится вне моего понимания.
#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
использование в качестве примера было бы чем-то как:
int x = 57;
kroundup32(x);
//x is now 64
Несколько других примеров:
От 1 до 1
От 2 до 2
7 - 8
31 - 32
60 - 64
3 000 - 4 096
Я знаю, что это округляет целое число к, он - ближайшее питание 2, но это о том, насколько мое знание идет.
Любые объяснения значительно ценились бы.
Спасибо
3 ответа
(--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
- Уменьшить x на 1
- ИЛИ x с помощью (x / 2).
- ИЛИ x с (x / 4).
- ИЛИ x с (x / 16).
- ИЛИ x с (x / 256).
- ИЛИ x с (x / 65536).
- Увеличить x на 1.
Для 32-битового целого числа без знака это должно переместить значение до ближайшей степени 2, которая равна или больше. Разделы OR устанавливают все младшие биты ниже самого высокого бита, так что в итоге получается степень 2 минус один, а затем вы добавляете к нему единицу. Похоже, он несколько оптимизирован и поэтому не очень удобочитаем; выполняя это только с помощью побитовых операций и битового сдвига, а также в виде макроса (поэтому нет накладных расходов на вызов функции).
На моей машине kroundup32 дает 6000 м выстрелов / сек
А следующая функция дает 7,693 млн. Об / сек
inline int scan_msb(int x)
{
#if defined(__i386__) || defined(__x86_64__)
int y;
__asm__("bsr %1, %0"
: "=r" (y)
: "r" (x)
: "flags"); /* ZF */
return y;
#else
#error "Implement me for your platform"
#endif
}
inline int roundup32(int x)
{
if (x == 0) return x;
else {
const int bit = scan_msb(x);
const int mask = ~((~0) << bit);
if (x & mask) return (1 << (bit+1));
else return (1 << bit);
}
}
Так что @thomasrutter я бы не сказал, что он «сильно оптимизирован».
И соответствующая (только значимая часть) сборка (для GCC 4.4.4):
kroundup32:
subl $1, %edi
movl %edi, %eax
sarl %eax
orl %edi, %eax
movl %eax, %edx
sarl $2, %edx
orl %eax, %edx
movl %edx, %eax
sarl $4, %eax
orl %edx, %eax
movl %eax, %edx
sarl $8, %edx
orl %eax, %edx
movl %edx, %eax
sarl $16, %eax
orl %edx, %eax
addl $1, %eax
ret
roundup32:
testl %edi, %edi
movl %edi, %eax
je .L6
movl $-1, %edx
bsr %edi, %ecx
sall %cl, %edx
notl %edx
testl %edi, %edx
jne .L10
movl $1, %eax
sall %cl, %eax
.L6:
rep
ret
.L10:
addl $1, %ecx
movl $1, %eax
sall %cl, %eax
ret
По какой-то причине я не нашел подходящей реализации scan_msb (например, #define scan_msb (x ) if (__builtin_constant_p (x)) ... ) в стандартных заголовках GCC (только __ TBB_machine_lg / __ TBB_Log2 ).
Побитовые операции или и сдвиг по существу устанавливают каждый бит между самым высоким установленным битом и нулевым битом. Это даст число вида 2 ^ n - 1 . Последнее приращение добавляет единицу, чтобы получить число вида 2 ^ n . Начальный декремент гарантирует, что вы не округлите числа, которые уже являются степенями двойки, до следующей степени, так что, например, 2048 не становится 4096.