| |
|
  |
 поменять местами биты в байте, простой вопрос |
|
|
|
|
 Apr 25 2010, 20:04
|
Частый гость
Группа: Участник
Сообщений: 145
Регистрация: 11-01-08
Пользователь №: 34 001
|
я это вижу как цикл на 8 шагов где проверяется значение последнего бита в байте и это значение присваивается первому биту новому байту ну и затем сдвиг обоих на 1 вот только знаний не хватает как реализовать да в пересчете я наврал, ну думаю принцип Вы поняли что я пытался объяснить 
Сообщение отредактировал Vny4ek - Apr 25 2010, 20:05
|
|
|
|
|
|
|
|
Apr 25 2010, 20:04
|
Частый гость
Группа: Участник
Сообщений: 92
Регистрация: 23-12-08
Из: Кишинёв
Пользователь №: 42 680
|
Сумбурное описание, но если правильно понял то типа того: Код uint8_t InverseByte(uint8_t b)
{
uint8_t ret = 0;
for( int i = 0; i < 8; i++ )
{
ret |= ( ( b & ( 1 << i ) ) ? 1 : 0 ) << ( 7 - i );
}
return ret;
} 0x72->0x4E
|
|
|
|
|
|
|
|
Apr 25 2010, 20:57
|
Частый гость
Группа: Участник
Сообщений: 92
Регистрация: 23-12-08
Из: Кишинёв
Пользователь №: 42 680
|
Цитата(KRS @ Apr 25 2010, 23:46)  Можно же стандартный способ использовать примерно так он пишется: Код a = ((a & 0x55) << 1) | ((a & 0xAA) >> 1);
a = ((a & 0xCC) >> 2) | ((a & 0x33) << 2);
a = (a >> 4) | (a << 4); Прикольно, наверное Кнут? Цикл всегда можно развернуть, правда там всё равно на два действия выходит больше...
|
|
|
|
|
|
|
|
Apr 25 2010, 21:12
|
Гуру
Группа: Свой
Сообщений: 13 372
Регистрация: 27-11-04
Из: Riga, Latvia
Пользователь №: 1 244
|
Цитата(baralgin @ Apr 25 2010, 22:57) Цикл всегда можно развернуть, правда там всё равно на два действия выходит больше... То, что Вы написали весьма страшно  . И дело не в цикле (например стремимся к минимальному размеру, тогда прием KRS отдыхает) а в том, как он написан. Такое: Код uint8_t InverseByte(uint8_t b)
{
uint8_t ret = 0;
for( uint8_t i = 0x80; i; i >>= 1 )
{
if( b & 1 )
ret |= i;
b >>= 1;
}
return ret;
} будет в разы короче и быстрее. А такое, чуть увеличившись в размере, если повезет , обгонит KRS и по скорости: Код uint8_t InverseByte(uint8_t b)
{
uint8_t ret = 0;
for( uint8_t i = 0x80; b; b >>= 1 )
{
if( b & 1 )
ret |= i;
i >>= 1;
}
return ret;
}
--------------------
Feci, quod potui, faciant meliora potentes
|
|
|
|
|
|
|
|
Apr 25 2010, 21:55
|
Частый гость
Группа: Участник
Сообщений: 92
Регистрация: 23-12-08
Из: Кишинёв
Пользователь №: 42 680
|
Не поленился, проверил (плохая привычка меряться.. на ночь глядя ). CODE #include <cstdlib>
#include <iostream>
#include <windows.h>
#include <stdint.h>
static uint8_t InverseByte_zltigo(int b )
{
int ret = 0;
for( int i = 0x80; i; i >>= 1 )
{
if( b & 1 )
ret |= i;
b >>= 1;
}
return ret;
}
static uint8_t InverseByte_zltigo2(int b )
{
int ret = 0;
for( int i = 0x80; b; b >>= 1 )
{
if( b & 1 )
ret |= i;
i >>= 1;
}
return ret;
}
static uint8_t InverseByte(int b )
{
return
(
(b & 0x01) << 7 |
(b & 0x02) << 5 |
(b & 0x04) << 3 |
(b & 0x08) << 1 |
(b & 0x10) >> 1 |
(b & 0x20) >> 3 |
(b & 0x40) >> 5 |
(b & 0x80) >> 7
);
}
static void Benchmark( uint8_t (*test_func)(int))
{
LARGE_INTEGER start, end;
QueryPerformanceCounter(&start);
int seed = 0x72;
for(int i = 0; i < 100000000; i++ )
seed = test_func(seed);
QueryPerformanceCounter(&end);
std::cout << "time=" << end.QuadPart - start.QuadPart << std::endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
Benchmark( &InverseByte_zltigo );
Benchmark( &InverseByte_zltigo2 );
Benchmark( &InverseByte );
return 0;
}
Результат на моём процессоре (A64, Brisbane, L2=512kb): time=11045076 time=6801262 time=3793456 Видимо сравнения мешают. Я внёс немного самодеятельности и обозвал все внутренние переменные int'ом - так быстрее(для всего что выше avr). ps: но по скорости всё равно таблица рулит, как предложили выше. ps2: мой развёрнутый цикл идёт из немного модифицированного первого варианта: ret |= ( ( b & ( 1 << i ) ) >>i ) << ( 7 - i ); ps3: от порядка следования тестов результат конечно же зависит, но кардинально ничего не меняет.
Сообщение отредактировал baralgin - Apr 25 2010, 22:02
|
|
|
|
|
|
|
|
Apr 25 2010, 22:04
|
Гуру
Группа: Свой
Сообщений: 13 372
Регистрация: 27-11-04
Из: Riga, Latvia
Пользователь №: 1 244
|
Цитата(baralgin @ Apr 25 2010, 23:55) Не поленился Сильно поленились - у Автора всего лишь AVR а не Atlon . А во вторых и для AVR8 это фатально, переврали мои примеры и вписали int вместо insigned char. В третьих, а почему свой вариант не протестировали ? Вот как он выглядит на AVR8: Код 15 BYTE InverseByte(BYTE b)
\ InverseByte:
16 {
\ 00000000 2F59 MOV R21, R25
\ 00000002 2F68 MOV R22, R24
\ 00000004 2F30 MOV R19, R16
17 BYTE ret = 0;
\ 00000006 E020 LDI R18, 0
18 for( int i = 0; i < 8; i++ )
\ 00000008 E080 LDI R24, 0
\ 0000000A E090 LDI R25, 0
19 {
20 ret |= ( ( b & ( 1 << i ) ) ? 1 : 0 ) << ( 7 - i );
\ ??InverseByte_0:
\ 0000000C 2F48 MOV R20, R24
\ 0000000E E001 LDI R16, 1
\ 00000010 E010 LDI R17, 0
\ 00000012 .... RCALL ?S_SHL_L02
\ 00000014 2F13 MOV R17, R19
\ 00000016 2310 AND R17, R16
\ 00000018 F011 BREQ ??InverseByte_1
\ 0000001A E001 LDI R16, 1
\ 0000001C C001 RJMP ??InverseByte_2
\ ??InverseByte_1:
\ 0000001E E000 LDI R16, 0
\ ??InverseByte_2:
\ 00000020 E010 LDI R17, 0
\ 00000022 E047 LDI R20, 7
\ 00000024 1B48 SUB R20, R24
\ 00000026 .... RCALL ?S_SHL_L02
\ 00000028 2B20 OR R18, R16
21 }
\ 0000002A 9601 ADIW R25:R24, 1
\ 0000002C 3088 CPI R24, 8
\ 0000002E E000 LDI R16, 0
\ 00000030 0790 CPC R25, R16
\ 00000032 F364 BRLT ??InverseByte_0
22 return ret;
\ 00000034 2F02 MOV R16, R18
\ 00000036 2F86 MOV R24, R22
\ 00000038 2F95 MOV R25, R21
\ 0000003A 9508 RET
23 } А так нормально написанный цикл Код 15 BYTE InverseByte(BYTE b)
\ InverseByte:
16 {
17 BYTE ret = 0;
\ 00000000 E020 LDI R18, 0
18 for( BYTE i = 0x80; i; i >>= 1 )
\ 00000002 E810 LDI R17, 128
19 {
20 if( b & 1 )
\ ??InverseByte_0:
\ 00000004 FB00 BST R16, 0
\ 00000006 F40E BRTC ??InverseByte_1
21 ret |= i;
\ 00000008 2B21 OR R18, R17
22 b >>= 1;
\ ??InverseByte_1:
\ 0000000A 9506 LSR R16
23 }
\ 0000000C 9516 LSR R17
\ 0000000E F7D1 BRNE ??InverseByte_0
24 return( ret );
\ 00000010 2F02 MOV R16, R18
\ 00000012 9508 RET
25 } А в четвертых попробуйте этот Ваш сравнительный тест, например, на 0x01 и узнаете немного о везении.
--------------------
Feci, quod potui, faciant meliora potentes
|
|
|
|
|
|
|
|
Apr 25 2010, 22:31
|
Частый гость
Группа: Участник
Сообщений: 92
Регистрация: 23-12-08
Из: Кишинёв
Пользователь №: 42 680
|
Цитата(zltigo @ Apr 26 2010, 01:04) Сильно поленились - у Автора всего лишь AVR а не Atlon . А во вторых и для AVR8 это фатально, переврали мои примеры и вписали int вместо insigned char. В третьих, а почему свой вариант не протестировали ? А в четвертых попробуйте этот сравнительный тест, например, на 0x01 и узнаете немного о везении. Во первых под рукой нет avr и именно по этому uint8_t превратился в int. Для avr конечно нужно просто uint8_t. Далее свой(первый) вариант протестировал... и он оказался быстрее всех  - смотрел несколько раз, менял местами тесты. Быстрее он. Видимо архитектура процессора+ компилятор(VS2008Express, оптимизация на скорость). Насчёт 0x01: не корректно. Потому что компилятор умудряется считать результат до исполнения . Зато есть более корректный способ: подать в функцию случайную последовательность. Тогда влияние кэша и предсказателя(и возможно других фишек процессора) будет меньше. Вот новый вариант(с первой функцией) и случайным входом: CODE #include <cstdlib>
#include <iostream>
#include <windows.h>
#include <stdint.h>
static uint32_t x, y, z, w;
static void reset_xor128()
{
x = 123456789;
y = 362436069;
z = 521288629;
w = 88675123;
}
static uint32_t xor128()
{
uint32_t t;
t=(x^(x<<11));x=y;y=z;z=w;
return(w=(w^(w>>19))^(t^(t>>8)));
}
static uint8_t InverseByte_zltigo(int b )
{
int ret = 0;
for( int i = 0x80; i; i >>= 1 )
{
if( b & 1 )
ret |= i;
b >>= 1;
}
return ret;
}
static uint8_t InverseByte_zltigo2(int b )
{
int ret = 0;
for( int i = 0x80; b; b >>= 1 )
{
if( b & 1 )
ret |= i;
i >>= 1;
}
return ret;
}
static uint8_t InverseByte_unroll(int b )
{
return
(
(b & 0x01) << 7 |
(b & 0x02) << 5 |
(b & 0x04) << 3 |
(b & 0x08) << 1 |
(b & 0x10) >> 1 |
(b & 0x20) >> 3 |
(b & 0x40) >> 5 |
(b & 0x80) >> 7
);
}
static uint8_t InverseByte_first(int b )
{
int ret = 0;
for( int i = 0; i < 8; i++ )
{
ret |= ( ( b & ( 1 << i ) ) ? 1 : 0 ) << ( 7 - i );
}
return ret;
}
static void Benchmark( uint8_t (*test_func)(int))
{
LARGE_INTEGER start, end;
reset_xor128();
QueryPerformanceCounter(&start);
for(int i = 0; i < 100000000; i++ )
test_func( xor128() & 0xFF );
QueryPerformanceCounter(&end);
std::cout << "time=" << end.QuadPart - start.QuadPart << std::endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
Benchmark( &InverseByte_unroll );
Benchmark( &InverseByte_first );
Benchmark( &InverseByte_zltigo );
Benchmark( &InverseByte_zltigo2 );
return 0;
} И результат: time=4589919 time=4583382 time=18303765 time=16308624 ps: После нескольких испытаний пришёл всёже выводу что InverseByte_unroll и InverseByte_first примерно равны по скорости. Но в любом случае это всё архитектурнозависимо и тестировать нужно на том железе, где будет работать(оказывается что даже инструкции специальные для этого бывают ).
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
У некоторых есть инстркуция которая порядок битов меняет.
