Как быстро выполнить операцию?

← →
Dmitry S © (2008-08-18 16:06) [0]

Пусть даны два числа:
01001001001001001001001001001001 - 1. маска
00000111010110111100110100010101 - 2. данные

Из второго числа (данные) выбираем те биты, которые в маске равны 1:
-0--0--1--0--0--1--0--0--0--0--1 - 3.
затем "складываем" биты:
---------------------00100100001 - 4.

Как можно быстро выполнить данную операцию (имея числа 1. и 2., получить число 4.)? И обратную (имея числа 4. и 1., получить 2.).

← →
Рамиль © (2008-08-18 16:11) [1]

AND и сдвигать?

> И обратную (имея числа 4. и 1., получить 2.).

Действия необратимы.

← →
Рамиль © (2008-08-18 16:13) [2]

Не, неправильно прочитал.

← →
Ega23 © (2008-08-18 16:14) [3]

Обратно - в принципе никак.

R=число_1 and число_2; cnt=0; while (R>0) do begin cnt := cnt + (R and 1); R := shr 1; end;

← →
Dmitry S © (2008-08-18 16:18) [4]

> Обратно - в принципе никак.

Забыл уточнить. В обратной задачи те биты, которые в маске равны нулю не имеют значения. Можно установить их в 0.

← →
Pavia © (2008-08-18 16:18) [5]

3 число через and.
4. Используетм табличку 256*256 со сдвинутами битами По вертикали маски по горизонтали данные. В самой табличке хранить сдвинутые биты
плюс в нейже хранить число бит в маске. окончательный результат через сдвиги и and.

← →
Smile (2008-08-18 16:19) [6]

> Dmitry S © (18.08.08 16:06)
> И обратную (имея числа 4. и 1., получить 2.).

Чтобы не "париться" с обратно, просто запоминай
> 00000111010110111100110100010101 - 2. данные

← →
DiamondShark © (2008-08-18 16:34) [7]

> Dmitry S © (18.08.08 16:18) [4]
> > Обратно - в принципе никак.Забыл уточнить. В обратной
> задачи те биты, которые в маске равны нулю не имеют значения.
> Можно установить их в 0.

Можно установить, а можно не установить -- всё равно однозначного обратного преобразования нет:

маска 1100
данные 1000
=1

маска 1100
данные 0100
=1

ну и какой результат должна выдавать обратная функция для 1?

← →
Rouse_ © (2008-08-18 16:35) [8]

> Smile

+1 :)))

← →
Dmitry S © (2008-08-18 16:42) [9]

> Можно установить, а можно не установить -- всё равно однозначного
> обратного преобразования нет:
>
> маска 1100
> данные 1000
> =1
>
Тут результат будет 10, а не 1.
Результат обратной операции будет "10xx". где xx - два, не важно каких, бита :)

← →
han_malign © (2008-08-18 17:35) [10]

pack
src_mask:= 1; dst_mask:= 1; result:= 0; while(src_mask)do begin if(mask and src_mask <> 0)then begin if(val and src_mask <> 0)then result:= result or dst_mask; dst_mask:= dst_mask shl 1; end; src_mask:= src_mask shl 1; end;unpack
src_mask:= 1; dst_mask:= 1; result:= 0; while(src_mask)do begin if(mask and src_mask <> 0)then begin if(val and dst_mask <> 0)then result:= result or src_mask; dst_mask:= dst_mask shl 1; end; src_mask:= src_mask shl 1; end;

Если маска фиксирована, то дарю идею:
Нужно создать несколько таблиц преобразования. Каждая таблица - по 256 байт. Вся операция сведётся к фиксированному количеству сдвигов, выборки из таблицы и or. Никаких циклов. Если делать на basm, так вообще будет быстро.

Если не фиксирована, но меняется редко, а операцию нужно делать часто, то таблицы можно генерить на лету.

> Dmitry S © (18.08.08 16:42) [9]
> Тут результат будет 10, а не 1.
> Результат обратной операции будет "10xx". где xx - два,
> не важно каких, бита :)

Поскольку (как я понял) если в маске 0, данные не рассматриваются, то
результатов обратной операции несколько:
10хх, 1х0х, 1хх0, х10х, х1х0, хх10

Выбирай...

> oldman © (19.08.08 11:58) [12]

Либо ты, либо я неверно поняли. В оригинальном примере показано выборка каждого третьего бита. Обратная операция однозначна, если все добаляемые биты нули. Так что я не вижу неоднозначности.
Подобные преобразования обычно делают либо аппаратно, либо таблицами.
Что я и предложил. То есть это не моя идея, это стандартный подход к таким задачам.
Всё-таки образование и опыт играют роль.

> Либо ты, либо я неверно поняли. В оригинальном примере показано
> выборка каждого третьего бита.

Тогда не 10хх, а 1хх0
:)))

если тупо выборка каждого третьего бита, на фига тогда маска вообще?
тогда данные обрабатываются легко и просто.

Как быстро выполнить операцию? Найти похожие ветки