битовые операции
Valery Ivanov
1) как "перевернуть" байт ?
те изначально биты расположены 0,1,..7
нужно получить байт с битами 7,6,..0
интересует алгоритм (код на c++)
2) какая на спарках (sparc) структура памяти по отношению к intel
если рассматривать структуры с битовыми полями
3) тот же вопрос если рассматривать сложные структуры где чередуются
обычные данные (double,int) c битовыми полями
в частности как получить адрес битового поля ?
4) url про sparc плз
ob
01 Aug 06 20:32 --> 01 Aug 06 23:37
Valery Ivanov (2:452/112.42@FidoNet) --> All
*VI*> 1) как "перевернуть" байт ?
*VI*> те изначально биты расположены 0,1,..7
*VI*> нужно получить байт с битами 7,6,..0
*VI*> интересует алгоритм (код на c++)
*VI*> 2) какая на спарках (sparc) структура памяти по отношению к intel
*VI*> если рассматривать структуры с битовыми полями
*VI*> 3) тот же вопрос если рассматривать сложные структуры где чередуются
*VI*> обычные данные (double,int) c битовыми полями
*VI*> в частности как получить адрес битового поля ?
*VI*> 4) url про sparc плз
Может не надо?.. ;-}
PS1: http://www.sun.com/processors/
LPS: Не стоит принимать близко к сердцу мой бред...
Руку отпускаю, пока. ob.
[*Соседи спят спокойно*]
[_/Necromant's Voice team/_] [*451°F*] [/_Death after Life team_/]
... Мёртвые за углом стоят ...
Igor Krassikov
19:32 01 Aug 06, Valery Ivanov -> All:
VI> 1) как "перевернуть" байт ?
VI> те изначально биты расположены 0,1,..7
VI> нужно получить байт с битами 7,6,..0
VI> интересует алгоритм (код на c++)
Hапример, так:
unsigned char bitRev(unsigned char x)
{
x = ((x&0x55) << 1) | ((x&0xAA) >> 1);
x = ((x&0x33) << 2) | ((x&0xCC) >> 2);
x = ((x&0x0F) << 4) | ((x&0xF0) >> 4);
return x;
}
Best regards.
Igor
Igor Krassikov
14:31 02 Aug 06, Igor Krassikov == Valery Ivanov:
Совсем забыл - можно еще и так, например:
unsigned char BitRev(unsigned char x)
{
unsigned int s = (x*0x00020202)&0x01044010;
unsigned int t = (x*0x00080808)&0x02088020;
return (s+t)%4095;
}
Best regards.
Igor
Kirill Frolov
> 1) как "перевернуть" байт ?
> те изначально биты расположены 0,1,..7
> нужно получить байт с битами 7,6,..0
> интересует алгоритм (код на c++)
Сдвиг влево в флаг переноса, сдвиг вправо из флага переноса. И так 8
раз подряд. C-два-креста тут не помогут. Табличным методом -- не
спортивно.
> 3) тот же вопрос если рассматривать сложные структуры где чередуются
> обычные данные (double,int) c битовыми полями
> в частности как получить адрес битового поля ?
А в эём этот адрес считать? В каких единицах?
Stanislav Shwartsman
02 Aug 06 13:39, you wrote to Valery Ivanov:
IK> Совсем забыл - можно еще и так, например:
IK> unsigned char BitRev(unsigned char x)
IK> {
IK> unsigned int s = (x*0x00020202)&0x01044010;
IK> unsigned int t = (x*0x00080808)&0x02088020;
IK> return (s+t)%4095;
IK> }
Ужас. Два умножения, еще и деление.
IMHO первый приз в конкурсе на самую медленную версию :)
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye ! [Team Intel Centrino Technology]
Stanislav (AKA Night's Man) [Team Technion]
Igor Krassikov
17:26 02 Aug 06, Stanislav Shwartsman -> Igor Krassikov:
IK>> unsigned char BitRev(unsigned char x)
IK>> {
IK>> unsigned int s = (x*0x00020202)&0x01044010;
IK>> unsigned int t = (x*0x00080808)&0x02088020;
IK>> return (s+t)%4095;
IK>> }
SS> Ужас. Два умножения, еще и деление.
SS> IMHO первый приз в конкурсе на самую медленную версию :)
Интересно, что Уоррен ее приводит как шаг вперед по сравнению с версией со
сдвигами :). Переписывается как
u = x*0x00020202
m = 0x01044010
s = u&m
t = (u<<2)&(m<<1)
x = (0x01001001*(s+t))>>24
так что делений нет, умножений 2. По компактности так точно не уступает первому
варианту :))
Best regards.
Igor
Stanislav Shwartsman
03 Aug 06 06:36, you wrote to me:
IK> Интересно, что Уоррен ее приводит как шаг вперед по сравнению с
IK> версией со сдвигами :). Переписывается как
IK> u = x*0x00020202
IK> m = 0x01044010
IK> s = u&m
IK> t = (u<<2)&(m<<1)
IK> x = (0x01001001*(s+t))>>24
IK> так что делений нет, умножений 2. По компактности так точно не
IK> уступает первому варианту :))
Это уже звучит лучше, но все равно, вариант с одними сдвигами должен быть
быстрее. Hа современных out-of-order процессорах, чем меньше зависимостей
между инструкциями, тем быстрее будут выполнены вычисления.
А тут мало того, что два умножения (умножение операция не быстрая,
выполняется за несколько тактов), так еще и все от всего зависит, код
абсолютно сериальный.
Evgenij Masherov
VI> 1) как "перевернуть" байт ?
VI> те изначально биты расположены 0,1,..7
VI> нужно получить байт с битами 7,6,..0
VI> интересует алгоритм (код на c++)
Сделать таблицу в 256 элементов. И выбирать.
Евгений Машеров АКА СанитарЖеня
Igor Krassikov
11:45 03 Aug 06, Stanislav Shwartsman -> Igor Krassikov:
SS> Это уже звучит лучше, но все равно, вариант с одними сдвигами должен быть
SS> быстрее. Hа современных out-of-order процессорах, чем меньше зависимостей
SS> между инструкциями, тем быстрее будут выполнены вычисления.
SS> А тут мало того, что два умножения (умножение операция не быстрая,
SS> выполняется за несколько тактов), так еще и все от всего зависит, код
SS> абсолютно сериальный.
Скорее наоборот... А во втором варианте как минимум s и t вычисляются
отдельно. Впрочем "к чему слова, зачем так много треска?" (с) :-)) Практика,
как известно, критерий истины...
#include <stdio.h>
unsigned char br(unsigned char x)
{
x = ((x&0x55) << 1) | ((x&0xAA) >> 1);
x = ((x&0x33) << 2) | ((x&0xCC) >> 2);
x = ((x&0x0F) << 4) | ((x&0xF0) >> 4);
return x;
}
unsigned char BR(unsigned char x)
{
unsigned int u = x*0x00020202;
const unsigned int m = 0x01044010, n = 0x2088020;
unsigned int s = u&m;
unsigned int t = (u<<2)&n;
return (0x01001001*(s+t))>>24;
}
void main()
{
long long start = muTime();
for(int i = 0; i < 100000; ++i)
{
for(unsigned int x = 0; x <=0xFE; ++x)
{
unsigned char z = br(x);
}
}
long long stop = muTime();
printf("Time: %ld mks\n",stop-start);
start = muTime();
for(int i = 0; i < 100000; ++i)
{
for(unsigned int x = 0; x <=0xFE; ++x)
{
unsigned char z = BR(x);
}
}
stop = muTime();
printf("Time: %ld mks\n",stop-start);
}
muTime() - моя функция, которая под OS/2 честно меряет время с точностью до
микросекунд.
Open Watcom 1.5, wcl386 -otx.
Hачнем с того, что код br - 74 байта, код BR - 54 байта. Время соответственно -
0.249 и 0.175 секунд (Celeron IV).
Best regards.
Igor
Valery Ivanov
VI>> 1) как "перевернуть" байт ?
VI>> те изначально биты расположены 0,1,..7
VI>> нужно получить байт с битами 7,6,..0
VI>> интересует алгоритм (код на c++)
EM> Сделать таблицу в 256 элементов. И выбирать.
если честно то я давным давно уже написал две функции
переворачивания байта
одна - честно работает по битам
вторая - реализована через union и структуры в которых
перевернуто расположения полей
но ты просто уже третий или четвертый чел, который написал что нужна
таблица
детский вопрос : на кой черт эта таблица ?
или я чего то не догоняю ?
Valery Ivanov
VI>> 1) как "перевернуть" байт ?
VI>> те изначально биты расположены 0,1,..7
VI>> нужно получить байт с битами 7,6,..0
VI>> интересует алгоритм (код на c++)
IK> Hапример, так:
IK> unsigned char bitRev(unsigned char x)
IK> {
01234567
IK> x = ((x&0x55) << 1) | ((x&0xAA) >> 1);
перестановка1
1010101 55
10101010 AA
10325476
IK> x = ((x&0x33) << 2) | ((x&0xCC) >> 2);
перестановка2
110011 33
11001100 CC
32107654
IK> x = ((x&0x0F) << 4) | ((x&0xF0) >> 4);
перестановка3
0F 1111
F0 11110000
76543210
IK> return x;
все верно
IK> }
математическое обьяснение :
перестановка = перестановка3*перестановка2*перестановка1
в самом деле
перестановка3 : i -> (i-4) mod 8
перестановка2 : i -> i1= (i-2) mod 4 если рассматривать внутренний
набор в 4 бита и в общем - i -> i1 + ( i div 4) * 4
перестановка1: i -> i2 = (i-1) mod 2 если рассматривать
внутренний набор и в общем i -> i2 + (i div 2)*2
теперь считаем:
1: i-> (i-1) mod 2 + (i div 2)* 2 = i_1
2: i_1 -> (i_1-2) mod 4 + (i_1 div 4)*4 = i_2
3: i_2 -> (i_2 - 4) mod 8 = i_3
подсчитав получаем i_3 = 7-i
действительно представим индекс i = 2^2*i2+2*i1+1*i0 = (i2,i1,i0) в двоичной
системе
тогда перестановка 1:
i div 2 = 2*i2+i1
(i-1) mod 2 = (i0-1) mod 2 = (1-i0)
те i=(i2,i1,i0) -> 2*(2*i2+i1)+(1-i0) = 4*i2 + 2*i1 + (1-i0) -> (i2,i1,1-i0)
перестановка 2:
i div 4 = i2
(i-2) mod 4 = (2*(i1-1) + 1*i0) mod 4 = 2*(1-i1)+i0
те i = (i2,i1,i0) -> 4 * (i2) + 2* (1 -i1) + i0 -> (i2,1-i1,i0)
перестановка3
i -> (i-4) mod 8 = (4*(i2-1)+2*i1+1*i0) mod 8 = 4*(1-i2)+2*i1+1*i0 ->
(1-i2,i1,i0)
комбинация перестановок даст нам i = (i2,i1,i0) -> (1-i2,1-i1,1-i0) = 7-i
ps это я просто прокомментировал
кстати, при разборе можно попробовать воспользоваться
1) средствами мат логики
тогда последняя строка например расшифруется так
((x&0x0F)<<4)| ((x&0xF0)>>4) = ((x<<4)&0xF0)|(x>>4)&0x0F)=
= (x<<4)|(x>>4)
2) средствами чистой математики
вспомним что x mod k = k*{x/k} , {x} - дробная часть x
x div k = [x/k] [x] - целая часть x, x = {x}+[x],
0<={x}<1
тогда например перестановка 1 разберется так :
(i-1) mod 2 + 2* (i div 2) =
{(i-1)/2}*2 + 2* ( [i/2] )=
(i-1) + 2* ( [i/2]-[(i-1)/2])
но [i/2] - [(i-1)/2] = 1 , i - четное, = 0 , i - нечетное
следовательно
перестановка1 : i -> i+1 , i- четное,
i-1, i- нечетное
Miguel Mitrofanov
VI>>> 1) как "перевернуть" байт ?
VI> но ты просто уже третий или четвертый чел, который написал что
VI> нужна таблица детский вопрос : на кой черт эта таблица ? или я
VI> чего то не догоняю ?
Ну дык самый простой способ
byte reverse(b:byte){return table[b];}
Правда, самый простой не значит самый быстрый; всё-таки обращение к
памяти... С другой стороны, при частом использовании таблица имеет все
шансы закэшироваться.
--
Miguel migue...@yandex.ru
LJ migmit http://miguel-0.narod.ru
Evgenij Masherov
VI>>> 1) как "перевернуть" байт ?
VI>>> те изначально биты расположены 0,1,..7
VI>>> нужно получить байт с битами 7,6,..0
VI>>> интересует алгоритм (код на c++)
EM>> Сделать таблицу в 256 элементов. И выбирать.
VI> если честно то я давным давно уже написал две функции
VI> переворачивания байта
VI> одна - честно работает по битам
VI> вторая - реализована через union и структуры в которых
VI> перевернуто расположения полей
VI> но ты просто уже третий или четвертый чел, который написал что нужна
VI> таблица
VI> детский вопрос : на кой черт эта таблица ?
VI> или я чего то не догоняю ?
Для "переворачивания" в одну операцию...
Hасколько эффективно - зависит от конкретной машины.
Евгений Машеров АКА СанитарЖеня
Stanislav Shwartsman
05 Aug 06 23:22, you wrote to Evgenij Masherov:
VI>>> 1) как "перевернуть" байт ?
VI>>> те изначально биты расположены 0,1,..7
VI>>> нужно получить байт с битами 7,6,..0
VI>>> интересует алгоритм (код на c++)
EM>> Сделать таблицу в 256 элементов. И выбирать.
VI> если честно то я давным давно уже написал две функции
VI> переворачивания байта
VI> одна - честно работает по битам
VI> вторая - реализована через union и структуры в которых
VI> перевернуто расположения полей
VI> но ты просто уже третий или четвертый чел, который написал что нужна
VI> таблица
VI> детский вопрос : на кой черт эта таблица ?
VI> или я чего то не догоняю ?
Потому что сделать переворот быстрее и проще, чем коммандой
a = table[b]
очень и очень сложно.
Michael Mamaev
Сyббота Авгyст 05 2006 23:22, Valery Ivanov wrote to Evgenij Masherov:
VI> но ты пpосто yже тpетий или четвеpтый чел, котоpый написал что нyжна
VI> таблица
VI> детский вопpос : на кой чеpт эта таблица ?
VI> или я чего то не догоняю ?
Hе догоняешь :)
Все зависит от того, насколько тебя жмёт по памяти и по скоpости. В некотоpых
аpхитектypах, где сиё действо тpебyется пpовоpачивать часто и быстpо, вообще
сyществyет специальная команда пpоцессоpа, котоpая делает все за один такт.
А если не жмёт - делай как полyчится, делов-то.
Майкл
Valery Ivanov
IK> Совсем забыл - можно еще и так, например:
unsigned char BitRev(unsigned char x)
{
unsigned int s = (x*0x00020202)&0x01044010;
unsigned int t = (x*0x00080808)&0x02088020;
return (s+t)%4095;
}
IK> unsigned char BitRev(unsigned char x)
IK> {
IK> unsigned int s = (x*0x00020202)&0x01044010;
0x00020202= a0 = 2^1 + 2^9 + 2^17
0x01044010 = b0 = 2^4 + 2^14 + 2^18 + 2^24
0x00080808= a1 = 4*a0
0x02088020= b1 = 2*b0
наш x = (x7,...,x0)
рассмотрим число xk= x*2^k = x<<k = (x7,...,x0, 0,...0)
тогда выражение k
(x*2^k)&2^m = xk[m]*2^m = x[m-k]*2^m, 7 => m-k >=0
= 0, (m-k)<0 || (m-k)>7
тогда составив табличку получим
s = (x*a0)&b0 = (x*(2^1 + 2^9 + 2^17)) & (2^4 + 2^14 + 2^18 + 2^24)
= x[2]*2^5 + x[4]*2^15 + x[0]*2^19 + x[6]*2^25
t =(x*a1)&b1 = x[3]*2^4 + x[5]*2^14 + x[1]*2^18 + x[7]*2^24
IK> unsigned int t = (x*0x00080808)&0x02088020;
4095 = 2^12 - 1
s+t = 2^12*A0+B0 = (2^12-1)*A0+A0 +B0
где
A0 = x[5]*2^2 + x[1]*2^6 + x[7]*2^12 + x[4]*2^3 + x0*2^7 + x6*2^13
B0 = x[3]*2^4 + x[2]*2^5
A0 = 2^12*A1 + B1 = (2^12-1)*A1 + A1 + B1
A1 = x[7]*2^0 + x[6]*2^1
B1 = x[5]*2^2 + x[1]*2^6+x[4]*2^3 + x[0]*2^7
IK> return (s+t)%4095;
(s+t)%4095 = B0 + A1+B1 = x[3]*2^4 + x[2]*2^5 + x[7]*2^0 + x[6]*2^1
+ x[5]*2^2 + x[1]*2^6 + x[4]*2^3 + x[0]*2^7
по последней строчке
видно что байт переставлен
IK> }
Igor Krassikov
20:58 07 Aug 06, Valery Ivanov -> Igor Krassikov:
VI> видно что байт переставлен
При всем уважении к теории :) замечу, что для байта (8 бит, 256 вариантов)
проще проверить практически, набросав за 5 минут соответствующую программку.
Еще раз оговорюсь - для нашего случая - 8 бит.
Best regards.
Igor