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

  • Автор темы knefedev
  • Дата начала
K

knefedev

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

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

lazybiz

Well-known member
03.11.2010
1 339
0
#3
knefedev
А что такое "побитовое XOR умножение переменной" ??
 
K

knefedev

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

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

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

lazybiz

Well-known member
03.11.2010
1 339
0
#5
C++:
a = 12345;
b = a ^ (a << 1);
Я так понимаю тебе что-то такое нужно...
 
D

dreamer

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

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

C++:
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

Well-known member
03.11.2010
1 339
0
#7
Да, но у тебя тут CF даже и не пахнет. Чтобы сделать через CF, нужно прибегать к средствам ассемблера.

(для наглядности взял размер данных за байт, и закомментировал операцию XOR)
C++:
#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" );
}
 

Вложения

  • 7.6 КБ Просмотры: 55

lazybiz

Well-known member
03.11.2010
1 339
0
#9
Сам же писал что товарищу нужен закольцованный сдвиг, где старший бит будет "перенесён" во флаг CF процессора.
Обговариваешь одно, а предлагаешь другое.
 
D

dreamer

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

lazybiz

Well-known member
03.11.2010
1 339
0
#11
Ну ты чудишь))) А это кто писал вчера в 23:42:
Товарищу нужен закольцованный сдвиг, а в этом случае, ЕМНИП, старший бит будет "перенесён" во флаг CF процессора. Младший же станет нулём.
К тому же никто не говорил в какую сторону нужно сдвигать значение.

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

dreamer

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

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

lazybiz

Well-known member
03.11.2010
1 339
0
#13
Я не знаю для кого ты это написал)) Ты же не сказал что под словами "а в этом с случае" ты подразумеваешь неправильный вариант решения. Да и с другой стороны почему он будет не правильным, если сам автор темы упомянул про использование CF.

Вот тебе закольцованный сдвиг влево без CF если ты его не заметил:
C++:
	__asm {
mov	al, [a]
rol	al, 1
mov	[b], al
}
Добавлено: knefedev
Для минимального количества тактов можно записать так:
C++:
	__asm {
mov	al, [a]
rol	 al, 1
xor	al, [a]
mov	[b], al
}
 
D

dreamer

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

knefedev

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

lazybiz

Well-known member
03.11.2010
1 339
0
#16
knefedev
Подожди минут 30. Щас настрою свой компилер GCC и отвечу в тему. Там синтаксис совершенно другой.
 
K

knefedev

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

dreamer

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

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

lazybiz

Well-known member
03.11.2010
1 339
0
#19
GCC:
C++:
	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