Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Порядок битов поменять на обратный

Автор: Crafty 4.7.2009, 00:41

Необходимо написать функцию, которая меняет порядок битов в целом числе без знака на обратный.
Вот кое-что написал, посоветуйте как можно улучшить функцию reverseBits.

Код


#include <stdio.h>

void displayBits(unsigned);
unsigned reverseBits(unsigned);

int main()
{    
    unsigned x;
    scanf("%d", &x);
    displayBits(x);
    x = reverseBits(x);
    displayBits(x);
    return 0;
}

void displayBits(unsigned value)
{
    unsigned c, mask = 1 << 31;
    
    printf("%10d = ", value);
    for(c = 1; c <= 32; c++){
        putchar(value & mask ? '1' : '0');
        value <<= 1;
        if(c % 8 == 0)
            putchar(' ');
    }
    putchar('\n');
}

unsigned reverseBits(unsigned x)
{
    unsigned c, n = 31, b = 0, mask = 1 << 31;
    
    for(c = 1; c <= 32; c++){
        b = b | (x & mask) >> n ;
        x <<= 1;
        --n;
    }
    return b;
}

Автор: W4FhLF 4.7.2009, 04:50

http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

Автор: Soah 12.7.2009, 11:53

Код


// ...
displayBits(x);
x = x ^ ~0;
displayBits(x);
// ...

Автор: Леопольд 13.7.2009, 20:38

Цитата(Soah @ 12.7.2009, 11:53)

Код


x = x ^ ~0;

Это тоже самое что и x = ~x Т.е. не то. Не думаю что можно так просто сделать. Наверное, всё же, придётся в цикле.

Код


const size_t c_size = 8;
const size_t u_size = sizeof(unsigned) * c_size;

unsigned reverseBits(unsigned value){
    unsigned result = 0;
    for(size_t i=0; i<u_size; ++i)
        result |= (value >> i & 1) << (u_size - 1 - i);
    return result;
}

По моему, так попроще выглядит smile

Автор: mes 13.7.2009, 20:45

Цитата(Леопольд @ 13.7.2009, 19:38

)

. Наверное придётся в цикле.

а предложенное http://forum.vingrad.ru/index.php?showtopic=265503&view=findpost&p=1913069, чем не устраивает то ?

Автор: Леопольд 13.7.2009, 20:50

Цитата(mes @ 13.7.2009, 20:45)

а предложенное http://forum.vingrad.ru/index.php?showtopic=265503&view=findpost&p=1913069, чем не устраивает то ?

Меня устраивает полностью. Но для универа не подойдёт. Я бы шаблон написал... smile

Автор: GoldFinch 13.7.2009, 20:52

Код


int __fastcall __bswap(int x) {__asm{ bswap eax }; }

int ReverseBits(int x)
{
   x=(x>>4)&0x0F0F0F0F+(x<<4)&0xF0F0F0F0;
   x=(x>>2)&0x33333333+(x<<2)&0xCCCCCCCC;
   x=(x>>1)&0x55555555+(x<<1)&0xAAAAAAAAA;
   return __bswap(x);
}

(для x86-32)

Добавлено через 9 минут и 48 секунд

Цитата(W4FhLF @ 4.7.2009, 05:50

)

http://graphics.stanford.edu/~seander/bith...tReverseObvious

ого! нафига делать за "3-4" операции если там деление и умножение %)
както это нежизнеспособно ниразу

Автор: mes 13.7.2009, 21:26

Цитата(Леопольд @ 13.7.2009, 19:50

)

Меня устраивает полностью. Но для универа не подойдёт. Я бы шаблон написал... smile

[
или я чего то не понимаю, или .. но там же приведен не один вариант, а несколько ! в том числе подходящие для института smile

Автор: GoldFinch 13.7.2009, 21:29

я тоже сначала только 1 заметил

Автор: Леопольд 13.7.2009, 21:29

Цитата(mes @ 13.7.2009, 21:26)

или я чего то не понимаю, или .. но там же приведен не один вариант, а несколько ! в том числе подходящие для института smile

Я видел два. Но суть не в этом. Была просьба "подправить" уже написанную функцию, что я и сделал...

На первый взгляд "Reverse bits the obvious way" самый простой. Но он уже оптимизирован, причём несколькими людьми, в течении нескольких лет... smile

Если бы я был препод, я бы не поверил что он сам это написал.

Автор: W4FhLF 14.7.2009, 11:42

Цитата(GoldFinch @ 13.7.2009, 20:52

)

(для x86-32)

Ты забыл добавить: x86-32-MSC++(=> Win32 only)

Цитата(GoldFinch @ 13.7.2009, 20:52

)

както это нежизнеспособно ниразу

Не более, чем у тебя smile

Автор: GoldFinch 14.7.2009, 12:02

W4FhLF, с точки зрения наглядности, цикл лучше всего,
с точки зрения быстродействия мой вариант лучше их умножения.

Автор: W4FhLF 14.7.2009, 12:20

Цитата(GoldFinch @ 14.7.2009, 12:02

)

с точки зрения быстродействия мой вариант лучше их умножения.

Ну во-первых твой вариант можно переписать без потери переносимости. А во-вторых, я думаю когда ты его писал, то занимался premature optimization.

Есть измерения, на каких объёмах эта оптимизация становится оправдана для среднестатистических десктопов?

Автор: GoldFinch 14.7.2009, 13:06

W4FhLF, я что в голову пришло, то и написал, никакой оптимизации.
правда я было думал что в MSVC есть интринсик __bswap(), а оказалось его нет.

Добавлено через 4 минуты и 11 секунд
а то что по сравнению с циклом это premature optimization - не факт.
это чистая функция с вполне понятным названием и прототипом.
то как она реализована - никак не влияет на код где она используется.
время на ее написание - примерно такое же как и на написание цикла (если понимаешь что делаешь)
читается легко (если понимаешь что делают сдвиги и маски)

Автор: mes 14.7.2009, 13:52

Цитата(W4FhLF @ 14.7.2009, 11:20

)

А во-вторых, я думаю когда ты его писал, то занимался premature optimization.

Цитата(GoldFinch @ 14.7.2009, 12:06

)

а то что по сравнению с циклом это premature optimization - не факт.

солидарен с GoldFinch - никакой преждевременной оптимизации (__bswap не расматриваем) тут нет, просто реализация иного алгоритма,
функция изначально преднаначена для реализации некой двоичной логики,
и для программиста с точки зрения временных затрат, если он нормально ориентируется в двоичной с.с.,такой вариант, ничуть не сложней циклического подхода.
smile

P.S. только вместо inta все ж лучше использовать unsigned. (будем считать что опечатка smile

)

Автор: W4FhLF 14.7.2009, 14:10

Да я вообще-то тоже за подход с масками и сдвигами, но без ассемблера, он там не нужен.

Автор: GoldFinch 14.7.2009, 14:14

W4FhLF, глупо реализовывать bswap если она уже есть

Автор: W4FhLF 14.7.2009, 14:23

GoldFinch, глупо терять переносимость не получая ничего взамен.

Добавлено через 1 минуту и 43 секунды

Код


// bswap 32-bit word
i = (i >> 16) | (i << 16);

Автор: GoldFinch 14.7.2009, 15:18

W4FhLF, оно у тебя только 16разрядные слова местами меняет, а нада еще байты поменять

меня так просто жаба душит 1 инструкцию на 5-6 операций заменять ради переносимости на не-х86

Автор: W4FhLF 14.7.2009, 16:34

Цитата(GoldFinch @ 14.7.2009, 15:18

)

W4FhLF, оно у тебя только 16разрядные слова местами меняет, а нада еще байты поменять

Не проблема переделать. Хотя для задачи и не требуется.

Код


unsigned ReverseBits1(unsigned v)
{
    v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
    v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
    v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
    v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
    return ( v >> 16 ) | ( v << 16 );
}

Цитата(GoldFinch @ 14.7.2009, 15:18

)

меня так просто жаба душит 1 инструкцию на 5-6 операций заменять ради переносимости на не-х86

Что-то твой код у меня вообще неправильно работает. А переносимости у него нет даже в пределах одной аппаратной платформы, между компиляторами (http://www.comeaucomputing.com/tryitout/).

Плюс у тебя в коде идёт вызов доп. процедуры (__bswap), студия не инлайнит её на /O2. Из-за этого происходит сброс конвеера, а это куда хуже 3-4 операций сдвига и or.

Автор: mes 14.7.2009, 16:36

Цитата(GoldFinch @ 14.7.2009, 14:18

)

меня так просто жаба душит 1 инструкцию на 5-6 операций заменять ради переносимости на не-х86

GoldFinch, как всегда в своем репертуаре smile

Автор: GoldFinch 14.7.2009, 17:43

W4FhLF, я его не проверял, неудивительно что не работает smile