Сдвиг влево только части номера

Question

Мне нужно найти самую быструю эквивалентность следующего кода C.

int d = 1 << x; /* d=pow(2,x) */
int j = 2*d*(i / d) + (i % d);

То, что я думал, это сдвинуть влево верхние 32 - x биты i.
Например, следующее i с x= 5:
1010 1010 1010 1010
станет:
0101 0101 010 0 1010
Есть ли для этого команда сборки?Как я могу быстро выполнить эту операцию?

Answer 1

делений медленные:

int m = (1 << x) - 1;
int j = (i << 1) - (i & m);

обновление

или, возможно, быстрее:

int j = i + (i & (~0 << x));

Answer 2

x86 32-битная сборка (синтаксис AT & T):

/* int MaskedShiftByOne(int val, int lowest_bit_to_shift) */
mov 8(%esp), %ecx
mov $1, %eax
shl %ecx, %eax            ; does 1 << lowest_bit_to_shift
mov 4(%esp), %ecx
dec %eax                  ; (1 << ...) - 1 == 0xf..f (lower bitmask)
mov %eax, %edx
not %edx                  ; complement - higher mask
and %ecx, %edx            ; higher bits
and %ecx, %eax            ; lower bits
lea (%eax, %edx, 2), %eax ; low + 2 * high
ret

Это должно работать как в Linux, так и в Windows.

Редактировать: i + (i & (~0 << x)) короче:

mov 4(%esp), %ecx
mov $-1, %eax
mov 8(%esp), %edx
shl %edx, %eax
and %ecx, %eax
add %ecx, %eax
ret

Мораль: никогда не начинай со сборки. Если вам это действительно нужно, разберите высоко оптимизированный вывод компилятора ...

Answer 3

Сдвиг влево на одну верхнюю x бит.

unsigned i = 0xAAAAu;
int x = 5;
i = (i & ((1 << x) - 1)) | ((i & ~((1 << x) - 1)) << 1); // 0x1554A;

Некоторые объяснения:

(1 << x) - 1 создает маску для обнуления старших 32 - x битов.

~((1 << x) - 1) делает маску для обнуления младших x битов.

После обнуления битов мы сдвигаем верхнюю часть и or их вместе.

Попробуйте это на Кодовая панель .

Answer 4

int m = (1 << x) - 1;
int j = ((i & ~m) << 1) | (i & m);

Нет команды ассемблера, которая делает то, что вы хотите, но решение, которое я даю, быстрее, так как избегает разделения.

Answer 5

Синтаксис Intel:

mov ecx,[esp+4]      ;ecx = x
mov eax,[esp+8]      ;eax = i

ror eax,cl
inc cl
clc
rcl eax,cl
ret

Мораль: высокооптимизированный вывод компилятора ... нет.