Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Вопросы начинающих программистов
Перезагрузить страницу Изменение порядка бит в 32-битном числе на обратный
Ответ
 
Опции темы Опции просмотра
  (#16 (permalink)) Старый
Arachnelis Arachnelis вне форума
Member
 
Сообщений: 1,324
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2007
Angry 19.10.2007, 17:26

Потестил по-внимательнее свое последнее решение - оказалось, что оно работает не так, как надо - все единицы зеркалятся, т.е. 0x0F00A00F превращается в 0xFF05A0FF. Тоже, конечно, может пригодиться...

Переработал решение, результат лично мне почему-то здорово напоминает по виду Lisp:
Код:
unsigned long BinaryInvert32_2( unsigned long a )
{
    for( unsigned long i=0, j=31; i<16; i++, j-- )
        if ( ( ( a & (1uL<<i) ) << (j-i) ) != ( ( a & (1uL<<j) ) >> (j-i) ) )
            a ^= ( (1uL<<i) << (j-i) ) | ( (1uL<<j) >> (j-i) );
    return a;
}
Наверное, можно еще проще, но башка все никак не остывает...

Angel5a, спасибо, но я уже успел догнать как работает метод Rosty... Ваша версия была намного очевиднее, я бы сам так мог написать (если бы была подходящая фаза Луны ).
Ответить с цитированием
  (#17 (permalink)) Старый
Rius Rius вне форума
Программист
 
Аватар для Rius
 
Сообщений: 7,294
Сказал(а) спасибо: 21
Поблагодарили 919 раз(а) в 903 сообщениях
Регистрация: 27.08.2004
Адрес: Russian Federation
По умолчанию 19.10.2007, 17:28

дааа, не стоило мне писать это по памяти
на самом деле юзаю такую функцию (с учётом переделки под unsigned long)
Код:
    //разворот байта 10110111 -> 11101101
    // union ub { U8 bytes[2]; U16 byte16;} ub1;
    unsigned long result = 0;
    int i;
    // ub1.byte16 = 0;
    // ub1.bytes[0] = inByte;
    for(i=0; i<31; i++)
    {
        result |= (a & 0x80000000);
        result = result >> 1;
        a = a << 1;
    }
    result |= (a & 0x80000000);
    return result;
p.s. юзаю в развороте байта перед отправкой данных для отображения в индикатор BG160160B (контроллер LC7981)
Ответить с цитированием
  (#18 (permalink)) Старый
Arachnelis Arachnelis вне форума
Member
 
Сообщений: 1,324
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2007
Cool 19.10.2007, 17:49

Ну конечно, можно проще!
Как только описал метод работы - сразу понял, что наделал кучу лишних операций!
Метод - если два зеркально стоящих бита в числе (например, 2-й и 30-й) одинаковы - то переставлять их нет смысла, а если разные, то формируем маску, содержащую только эти два бита и XOR'им число, переключая сразу оба.
Код:
unsigned long BinaryInvert32_3( unsigned long a )
{
    for( unsigned long i=0, j=31; i<16; i++, j-- )
        if ( ( a & (1uL<<i) )  !=  ( a & (1uL<<j) ) )
            a ^= (1uL<<i) | (1uL<<j);
    return a;
}
Объяснял, пока сам понял!
P.S. На ФП уже не так похоже. До скорости быстрой сортировки AlexeDejnek'и - вообще, как до Пекина раком...
Ответить с цитированием
  (#19 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 19.10.2007, 19:11

Код:
def r(a):
    re=0
    for i in xrange(32):
        a,b = divmod(a,2)
        re = re*2+b
    return re


импортирован с progz.ru
Ответить с цитированием
  (#20 (permalink)) Старый
Arachnelis Arachnelis вне форума
Member
 
Сообщений: 1,324
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2007
Cool 19.10.2007, 19:35

Цитата:
Помогите новичку написать простенькую программку пожалуйста.
Это мы так далеко уйдем!!!
Ответить с цитированием
Ads.
  (#21 (permalink)) Старый
Rius Rius вне форума
Программист
 
Аватар для Rius
 
Сообщений: 7,294
Сказал(а) спасибо: 21
Поблагодарили 919 раз(а) в 903 сообщениях
Регистрация: 27.08.2004
Адрес: Russian Federation
По умолчанию 19.10.2007, 20:20

на ваше принятие решений об отражении бита уйдёт больше времени, чем на простой сдвиг-перенос

Цитата:
И почему наСИльников не видать в "Самом крутом языке"?
они занимаются более полезными делами...
Ответить с цитированием
  (#22 (permalink)) Старый
Angel5a Angel5a вне форума
Member
 
Сообщений: 1,213
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 28.02.2005
По умолчанию 19.10.2007, 23:44

Цитата:
Код:
def r(a):
    re=0
    for i in xrange(32):
        a,b = divmod(a,2)
        re = re*2+b
    return re
5 балоф, внесли разнообразие в наши сишные споры

2 Rius, посмотрите в сторону замены местами строчек сдвига и установки битов. ненадо будет после цикла бит устанавливать.

Некоторый вариант "ускорения" алгоритма, правда мне он не сильно нравицца... если нужна скорость, то тогда на асемблере будит лучше... :
Код:
unsigned int ReversBits(unsigned int value) {
 unsigned int result = 0;
 unsigned int mask = 0x80000000;
 while ( value ) {
  if ( value & 1 ) result |= mask;
  value >>= 1;
  mask >>= 1;
 }
 return result;
}
В завершении привиду пример на асемблере. Как ни странно всё коротко и понятно число находиться в регистре EAX результат помещается обратно в EAX :
Код:
 mov edx, eax  // value -> EDX;
 mov eax, 0     // result = 0;
 mov cl, 32      // i = 32;
m1:
 ror edx, 1       // flag = (value & 1) , value >>= 1; 
 rcl eax, 1       // result <<= 1 , result |= flag;
 loop m1         // if ( --i  > 0 ) goto m1;
Ответить с цитированием
  (#23 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 20.10.2007, 00:12

ничего странного - такие задачи на асме решаются быстрее и легче чем на чём бы то ни было.


импортирован с progz.ru
Ответить с цитированием
  (#24 (permalink)) Старый
Arachnelis Arachnelis вне форума
Member
 
Сообщений: 1,324
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2007
Cool 21.10.2007, 14:14

Ну ладно, извращаться - так по полной!
Код:
template < class TAnyType >
TAnyType BitInverter( TAnyType tnData )
{
  //--------------------------------
    auto const unsigned nLen = sizeof(TAnyType);
  //--------------------------------
    union TUField
    {
      //----------------
        TAnyType atValue;
        struct TSBits
        {
            unsigned char bit7 : 1;
            unsigned char bit6 : 1;
            unsigned char bit5 : 1;
            unsigned char bit4 : 1;
            unsigned char bit3 : 1;
            unsigned char bit2 : 1;
            unsigned char bit1 : 1;
            unsigned char bit0 : 1;
        }  AnByte[ nLen ];
      //----------------
        inline TUField( TAnyType tnValue = (TAnyType)(0) )
            : atValue( tnValue ) { }
      //----------------
    };
  //--------------------------------

    auto const TUField UOData( tnData );
    auto TUField UOResult;
    for ( register unsigned i = nLen; i; )
    {
        register TUField::TSBits * const pUOResult = &UOResult.AnByte[ --i ];
        register const TUField::TSBits * const pUOData = &UOData.AnByte[ nLen - 1u - i ];
        pUOResult->bit7 = pUOData->bit0;
        pUOResult->bit6 = pUOData->bit1;
        pUOResult->bit5 = pUOData->bit2;
        pUOResult->bit4 = pUOData->bit3;
        pUOResult->bit3 = pUOData->bit4;
        pUOResult->bit2 = pUOData->bit5;
        pUOResult->bit1 = pUOData->bit6;
        pUOResult->bit0 = pUOData->bit7;
    }
    return UOResult.atValue;
}
Ответить с цитированием
Ads
  (#25 (permalink)) Старый
kodjan kodjan вне форума
Member
 
Сообщений: 65
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 25.10.2005
По умолчанию 26.10.2007, 09:24

Вчера был на собеседовании и там дали такую задачку: дано целое число, превратить в единицу (1) крайне правый нулевой бит,
т.е. 1000011 -> 1000111, 10011101 -> 10011111. Так вот, самое интересное: сделать это надо БЕЗ циклов и БЕЗ рекурсии
Ответить с цитированием
  (#26 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 26.10.2007, 12:44

Цитата:
Вчера был на собеседовании и там дали такую задачку: дано целое число, превратить в единицу (1) крайне правый нулевой бит,
т.е. 1000011 -> 1000111, 10011101 -> 10011111. Так вот, самое интересное: сделать это надо БЕЗ циклов и БЕЗ рекурсии
Дано - a

b=not a
f=a*2
c= f and b
e = 255 ( или сколько надо. в общем not 0)
d = e*c
k= d and с
result = k or a (Уря!!!!!!!)


импортирован с progz.ru
Ответить с цитированием
  (#27 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 26.10.2007, 13:24

Кажется можно проще:

b= not a
e = 255 ( или сколько надо. в общем not 0)
d= b*e
k = d and b
result = a or k


импортирован с progz.ru
Ответить с цитированием
  (#28 (permalink)) Старый
Rosty Rosty вне форума
Member
 
Сообщений: 84
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 13.11.2006
По умолчанию 26.10.2007, 14:00

Можно еще:

b = a + 1;
b = b xor a;
result = a or b;
Ответить с цитированием
  (#29 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 26.10.2007, 14:27

Цитата:
Это мы так далеко уйдем!!!
Да! Объявляется конкурс на самый эффективный вариант
Ответить с цитированием
  (#30 (permalink)) Старый
Rosty Rosty вне форума
Member
 
Сообщений: 84
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 13.11.2006
По умолчанию 26.10.2007, 16:07

Чуть измененный вариант Angel5a
Код:
#include <conio.h>
#include <stdio.h>

unsigned int ReverseBits(unsigned int value)
{
  unsigned int b;
  _asm
  {
     mov  eax, value  
     mov  ebx, 0
     mov  cx, 32
m1:
     ror  eax, 1
     rcl  ebx, 1        
     loop m1          
     mov  b, ebx
  }
  return b;
}

void print_bin(unsigned int value)
{
  char buff[33];
  char *ch = buff + 32;
  *ch-- = 0;
  for(int i = 0; i <32; i++)
  {
    if(value&0x1)
      *ch-- = '1';
    else
      *ch-- = '0';
    value>>=1;
  }
  printf(buff);
  printf("\n");
}

int main(int argc, char* argv[])
{
  print_bin(1001);

  print_bin(ReverseBits(1001));

  _getch();

  return 0;
}
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сколько цифр в числе turtles Java 4 08.12.2011 21:24
как подсчитать количество цифр в числе N NOK25 Вопросы начинающих программистов 2 23.10.2011 19:31
Посчитать количество цифр в числе Network22 С/С++ 15 23.10.2011 15:55
Изменение порядка созданных индексов для сортировки данных Aziz C++ Builder 2 10.04.2010 20:24
обратный вывод списка steklyashka Prolog 3 06.12.2009 18:37
Не понятен обратный ход рекурсии John_Dee Prolog 1 04.07.2007 12:24
Зачем нужен и обратный , и дополнительный код ra1n Assembler 1 18.10.2005 10:13
Подсчет цифр в числе AntStr Pascal 2 21.08.2005 12:18
Можно ли подменить обратный порт в UDP пакете DENIS451 C++ Builder 1 21.01.2005 09:31
Как послать char по UDP, указав обратный порт DENIS451 C++ Builder 1 22.10.2004 10:17
Формат пикселя в 16-ти битном режиме Rirt Программирование графики 1 26.10.2003 11:19
Как на 32 битном процессоре VC++ оперирует int64 Alexey_kv Visual C++ 3 16.09.2003 18:48



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов