VPF::Порядок битов поменять на обратный

Crafty

Дата 4.7.2009, 00:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 319
Регистрация: 3.11.2008

Репутация: 12
Всего: 14

Необходимо написать функцию, которая меняет порядок битов в целом числе без знака на обратный.
Вот кое-что написал, посоветуйте как можно улучшить функцию 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 (ссылка)

(голосов:3)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 2
Всего: 121

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

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

Soah

Дата 12.7.2009, 11:53 (ссылка)

(голосов:5)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 512
Регистрация: 18.2.2009

Репутация: 6
Всего: 54

Код


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

Леопольд

Дата 13.7.2009, 20:38 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Цитата(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

Это сообщение отредактировал(а) Леопольд - 13.7.2009, 20:51

--------------------

вопросов больше чем ответов

mes

Дата 13.7.2009, 20:45 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

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

)

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

а предложенное тут, чем не устраивает то ?

Это сообщение отредактировал(а) mes - 13.7.2009, 20:46

--------------------

http://opendots.net

Леопольд

Дата 13.7.2009, 20:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

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

а предложенное тут, чем не устраивает то ?

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

--------------------

вопросов больше чем ответов

GoldFinch

Дата 13.7.2009, 20:52 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 6
Всего: 26

Код


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" операции если там деление и умножение %)
както это нежизнеспособно ниразу

Это сообщение отредактировал(а) GoldFinch - 13.7.2009, 20:53

mes

Дата 13.7.2009, 21:26 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

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

)

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

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

--------------------

http://opendots.net

GoldFinch

Дата 13.7.2009, 21:29 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 6
Всего: 26

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

Леопольд

Дата 13.7.2009, 21:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

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

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

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

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

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

Это сообщение отредактировал(а) Леопольд - 13.7.2009, 21:34

--------------------

вопросов больше чем ответов

W4FhLF

Дата 14.7.2009, 11:42 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 2
Всего: 121

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 6
Всего: 26

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

W4FhLF

Дата 14.7.2009, 12:20 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 2
Всего: 121

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

)

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

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

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

--------------------

GoldFinch

Дата 14.7.2009, 13:06 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 6
Всего: 26

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

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

mes

Дата 14.7.2009, 13:52 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

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

)

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

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

)

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

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

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

)

Это сообщение отредактировал(а) mes - 14.7.2009, 13:52

--------------------

http://opendots.net

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »