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

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

  1. knefedev

    knefedev Гость

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

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

    LordPingvin Гость

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

    lazybiz Well-Known Member
    C\C++ Team

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

    knefedev Гость

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

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

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

    lazybiz Well-Known Member
    C\C++ Team

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

    dreamer Гость

    Маловато будет :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
     
  7. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

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

    Вложения:

    • RCL.png
      RCL.png
      Размер файла:
      7,6 КБ
      Просмотров:
      55
  8. dreamer

    dreamer Гость

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

    lazybiz Well-Known Member
    C\C++ Team

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

    dreamer Гость

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

    lazybiz Well-Known Member
    C\C++ Team

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

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

    dreamer Гость

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

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

    lazybiz Well-Known Member
    C\C++ Team

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

    dreamer Гость

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

    knefedev Гость

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

    lazybiz Well-Known Member
    C\C++ Team

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

    knefedev Гость

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

    dreamer Гость

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

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

    lazybiz Well-Known Member
    C\C++ Team

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

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