циклический побитовый сдвиг

[knefedev]

С новым годом всех! Успехов и здоровья!

Столкнулся с задачей: нужно организовать побитовое XOR умножение переменной. Хотелось бы чтобы на это XOR умножение тратилось минимальное число тактов. Говорят нужен циклический побитовый сдвиг с записью в другую переменную битового представления, а далее организация XOR между ними. Пока не нашел как организовать сдвиг и перезапись с помощью cf. Подскажите что-нибудь?...

 

[LordPingvin]

что такое "XOR умножение"?

 

[lazybiz]

knefedev
А что такое "побитовое XOR умножение переменной" ??

 

[knefedev]

Может не совсем правильно и понятно выразился, прошу прощения. Под побитовым ХОR имел ввиду применение операции исключающего ИЛИ для всех рядом стоящих битов замкнутых в кольцо.

Один из вариантов решения задачи:
есть unsigned int a
переменная
нужно сдвинуть циклически битовое представление этого числа
т.е., например
a=010101
превратить в
b=101010

потом хотелось бы выполнить ХОR для этих двух битовых векторов
т.е. a^b.
Причем хотелось бы сделать все это за минимальное количество тактов.

 

[lazybiz]

a = 12345;
b = a ^ (a << 1);

Я так понимаю тебе что-то такое нужно...

 

[dreamer]

Маловато будет :ya_lamo: Товарищу нужен закольцованный сдвиг, а в этом случае, ЕМНИП, старший бит будет "перенесён" во флаг CF процессора. Младший же станет нулём.

Как насчёт такого кода:

unsigned short a = 0xFFFE;
unsigned int a1 = (int)a << 1;
unsigned short b = (unsigned short)a1 | *((unsigned short*)&a1 + 1);
unsigned short s = a ^ b;
cout << s << endl;

Значение 'a' здесь взято для примера 0xFFFE

 

[lazybiz]

Да, но у тебя тут CF даже и не пахнет. Чтобы сделать через CF, нужно прибегать к средствам ассемблера.

(для наглядности взял размер данных за байт, и закомментировал операцию XOR)

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char		u8;
typedef unsigned short	u16;

void print_bin( u8 v )
{
int	i;
for ( i = 0; i < 8; i++ ) {
printf( "%d", (v >> (7 - i)) & 1 );
}
}

u8 wo_carry( u8 a )
{
u16	a1;
u8	b;
a1 = (short)a << 1;
b = (u8)a1 | *((u8 *)&a1 + 1);
return /*a ^*/ b;
}

u8 w_carry_rcl( u8 a )
{
u8	b;
__asm {
mov	al, [a]
rcl	al, 1
adc	al, 0
mov	[b], al
}
return /*a ^*/ b;
}

u8 wo_carry_rol( u8 a )
{
u8	b;
__asm {
mov	al, [a]
rol	al, 1
mov	[b], al
}
return /*a ^*/ b;
}

void main()
{
u8	a = 0x85;
print_bin( a );
printf( "\n\n" );

printf( "Without CF (C):\n" );
print_bin( wo_carry( a ) );
printf( "\n\n" );

printf( "With CF (asm)\':\n" );
print_bin( w_carry_rcl( a ) );
printf( "\n\n" );

printf( "Without CF (asm)\':\n" );
print_bin( wo_carry_rol( a ) );
printf( "\n" );
}

 

[dreamer]

Да, но у тебя тут CF даже и не пахнет

Вообще-то, я и не пытался.

 

[lazybiz]

Сам же писал что товарищу нужен закольцованный сдвиг, где старший бит будет "перенесён" во флаг CF процессора.
Обговариваешь одно, а предлагаешь другое.

 

[dreamer]

Я такого не говорил. Я сказал, что товарищу нужен закольцованный сдвиг, а в Вашем примере старший бит перейдёт в CF, а не в младший бит.

 

[lazybiz]

Ну ты чудишь))) А это кто писал вчера в 23:42:

Товарищу нужен закольцованный сдвиг, а в этом случае, ЕМНИП, старший бит будет "перенесён" во флаг CF процессора. Младший же станет нулём.

К тому же никто не говорил в какую сторону нужно сдвигать значение.

Добавлено:

в Вашем примере старший бит перейдёт в CF, а не в младший бит.

У меня два примера. В первом старший бит переносится в CF. Во втором старший бит переносится в младший бит.

 

[dreamer]

Ну так :happy: А для кого я написал "а в этом случае"?

К тому же никто не говорил в какую сторону нужно сдвигать значение.

Какая разница? Из сдвига влево легко сделать сдвиг вправо.

 

[lazybiz]

Я не знаю для кого ты это написал)) Ты же не сказал что под словами "а в этом с случае" ты подразумеваешь неправильный вариант решения. Да и с другой стороны почему он будет не правильным, если сам автор темы упомянул про использование CF.

Вот тебе закольцованный сдвиг влево без CF если ты его не заметил:

	__asm {
mov	al, [a]
rol	al, 1
mov	[b], al
}

Добавлено: knefedev
Для минимального количества тактов можно записать так:

	__asm {
mov	al, [a]
rol	 al, 1
xor	al, [a]
mov	[b], al
}

 

[dreamer]

Ну, если автор, то да... Сорри, не заметил, что knefedev сам обратил внимание на CF.

 

[knefedev]

Спасибки за помощь, товарищи. Вопрос к lazybiz: А как ваш ассемблерный код нужно изменить, чтобы его gcc компилятором собрать?

 

[lazybiz]

knefedev
Подожди минут 30. Щас настрою свой компилер GCC и отвечу в тему. Там синтаксис совершенно другой.

 

[knefedev]

Другой непраздный вопрос, который не дает мне покоя друзья, как осуществить XOR для заданного числа бит. например выполнить XOR для 7 бит, видимо без ассемблера не обойтись

 

[dreamer]

Не обязательно: можно сначала выполнить "И" по маске и полученное значение уже применять в операции XOR.

То есть, например, есть a и b. Нужно выполнить XOR по b для 7 бит a. В этом случае нужно сделать a ^ (b & 01111111b)

 

[lazybiz]

GCC:

	unsigned char	a, b;

// ...

a = 123;

asm(
"	movb	%1, %%al;"
"	rolb	$1, %%al;"
"	xorb	%1, %%al;"
"	mov		%%al, %0;"
: "=r" (b)	// output
: "r" (a)	// input
: "%al" );	// modified