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

Тема в разделе "Общие вопросы по С и С++", создана пользователем knefedev, 5 янв 2011.

  1. knefedev

    knefedev Гость

    Репутация:
    0
    С новым годом всех! Успехов и здоровья!

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

    LordPingvin Гость

    Репутация:
    0
    что такое "XOR умножение"?
     
  3. lazybiz

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    knefedev
    А что такое "побитовое XOR умножение переменной" ??
     
  4. knefedev

    knefedev Гость

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

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

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

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    Код:
    a = 12345;
    b = a ^ (a << 1);
    Я так понимаю тебе что-то такое нужно...
     
  6. dreamer

    dreamer Гость

    Репутация:
    0
    Маловато будет :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
     
  7. lazybiz

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    Да, но у тебя тут 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" );
    }
     

    Вложения:

    • циклический побитовый сдвиг
      RCL.png
      Размер файла:
      7,6 КБ
      Просмотров:
      55
  8. dreamer

    dreamer Гость

    Репутация:
    0
    Вообще-то, я и не пытался.
     
  9. lazybiz

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    Сам же писал что товарищу нужен закольцованный сдвиг, где старший бит будет "перенесён" во флаг CF процессора.
    Обговариваешь одно, а предлагаешь другое.
     
  10. dreamer

    dreamer Гость

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

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    Ну ты чудишь))) А это кто писал вчера в 23:42:
    К тому же никто не говорил в какую сторону нужно сдвигать значение.

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

    dreamer Гость

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

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

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    Я не знаю для кого ты это написал)) Ты же не сказал что под словами "а в этом с случае" ты подразумеваешь неправильный вариант решения. Да и с другой стороны почему он будет не правильным, если сам автор темы упомянул про использование 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
    }
     
  14. dreamer

    dreamer Гость

    Репутация:
    0
    Ну, если автор, то да... Сорри, не заметил, что knefedev сам обратил внимание на CF.
     
  15. knefedev

    knefedev Гость

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

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    knefedev
    Подожди минут 30. Щас настрою свой компилер GCC и отвечу в тему. Там синтаксис совершенно другой.
     
  17. knefedev

    knefedev Гость

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

    dreamer Гость

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

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

    lazybiz Well-Known Member

    Репутация:
    0
    Регистрация:
    3 ноя 2010
    Сообщения:
    1.339
    Симпатии:
    0
    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
     

Поделиться этой страницей