powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит
25 сообщений из 104, страница 1 из 5
Микширование бит
    #40022657
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дано: 2 Word-а по 16 бит :)
Необходимо объединить их так, чтобы биты шли последовательно
Можно ли сделать это без многочисленных умножений или огромных заранее рассчитанных таблиц?

Пример:

0101010101010101 op 1100111000111100 = 0111001001110110111001110010
...
Рейтинг: 0 / 0
Микширование бит
    #40022663
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
О, в моём примере не так
Но важное уточнение

На практике не бывает, что оба n-ных бита равны 1
Может быть пригодится
...
Рейтинг: 0 / 0
Микширование бит
    #40022674
bk0010
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
makewparam(lo,hi),
makelong(lo,hi),
LongRec(MyIntVariable).Lo := ..., LongRec(MyIntVariable).Hi := ...,
MyIntVariable:= Lo + Hi shl 16; ?
...
Рейтинг: 0 / 0
Микширование бит
    #40022678
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ошибся.
...
Рейтинг: 0 / 0
Микширование бит
    #40022681
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Ну у меня как-то так получилось в блокнотике:
Код: pascal
1.
2.
3.
4.
5.
6.
Result := 0; // DWORD;
for var i := 15 downto 0 do
begin
  Mask := 1 shl i; // Word
  Result := Result shl 1 or DWORD(WordA and Mask) shl 1 or DWORD(WordB and Mask);
end;
...
Рейтинг: 0 / 0
Микширование бит
    #40022767
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
Дано: 2 Word-а по 16 бит :)
Необходимо объединить их так, чтобы биты шли последовательно
Можно ли сделать это без многочисленных умножений или огромных заранее рассчитанных таблиц?

Пример:

0101010101010101 op 1100111000111100 = 0111001001110110111001110010


Ассемблер подойдет?
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
function Mix( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    ESI
     Push    EDI
     Push    EBX

     Xor     ESI,    ESI    // обнуляем временный результат
     Mov     EDI,    01h    // маска установки единичных битов w1 и w2

     Mov     ECX,    0Fh    // количество итераций
     Mov     EBX,    01h    // текущий сравниваемый бит для w1 и w2

@@10:
     Test    EAX,    EBX    // проверяем текущий бит для w1
     Jz      @@20

     Or      ESI,    EDI    // устанавливаем единичный бит w1

@@20:
     Shl     EDI,    01h    // сдвигаем текущий бит для w2
     Test    EDX,    EBX    // проверяем текущий бит для w2
     Jz      @@30

     Or      ESI,    EDI    // устанавливаем единичный бит w2

@@30:
     Shl     EDI,    01h    // сдвигаем текущий бит для w1
     Shl     EBX,    01h    // сдвигаем общий проверяемый бит
     Loop    @@10

     Mov     EAX,    ESI    // присваиваем временный результат

     Pop     EBX
     Pop     EDI
     Pop     ESI
end;
...
Рейтинг: 0 / 0
Микширование бит
    #40022828
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я честно говоря думал есть способ обойтись парой умножений и битовыми операциями
В общем спасибо за участие!
...
Рейтинг: 0 / 0
Микширование бит
    #40022831
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Polesov,

А зачем ассемблер?
Типа показать, что умеешь?
Или думаешь, так быстрее?
...
Рейтинг: 0 / 0
Микширование бит
    #40022844
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,
Такие вещи на ассемблере, как правило, быстрее.
В основном, за счет регистровой ручной оптимизации - нет обращений к стеку.
Ну, а показывать - не цель, чать не в детском садике )
...
Рейтинг: 0 / 0
Микширование бит
    #40022850
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Polesov

Такие вещи на ассемблере, как правило, быстрее.
В основном, за счет регистровой ручной оптимизации - нет обращений к стеку.

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

Другое дело, что если использовать ASM, то тогда можно и MMX регистры использовать

Polesov

Mov ECX, 0Fh // количество итераций

Мне кажется, что задача должна решаться за log(32) операций, т.е. максимум 5 операций.
...
Рейтинг: 0 / 0
Микширование бит
    #40022852
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev,
согласен, надо смотреть в каждом конкретном случае.

Код: pascal
1.
  Mov ECX, 0Fh // количество итераций


Ну, это в лоб )
...
Рейтинг: 0 / 0
Микширование бит
    #40022853
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Polesov,

Давай зарубимся
Я напишу ту же функцию на паскале и она будет быстрее :)
С меня паскалевский вариант, с тебя бенчмарк )
...
Рейтинг: 0 / 0
Микширование бит
    #40022854
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev,

А как ты решишь за 5 операций?
Интересно
...
Рейтинг: 0 / 0
Микширование бит
    #40022855
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,
хорошо, выкладывай код.

Да уже с кем-то гонялись - в каких-то случаях asm проиграл почти в 1.5 раза.
...
Рейтинг: 0 / 0
Микширование бит
    #40022858
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Polesov,

Давай ты бенчмарк
Я часа через 2 подтянусь
...
Рейтинг: 0 / 0
Микширование бит
    #40022861
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
Необходимо объединить их так, чтобы биты шли последовательно
Я правильно понял, что из abc и xyz надо получить axbycz ?

SOFT FOR YOU
огромных заранее рассчитанных таблиц?
А если не огромных? 128 Кбайт - это огромная?
...
Рейтинг: 0 / 0
Микширование бит
    #40022864
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
miksoft,

Да

Да

:)
...
Рейтинг: 0 / 0
Микширование бит
    #40022868
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
Polesov,
Давай ты бенчмарк

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
type
  TMixFunc = function ( w1, w2 : word ) : dWord;

function MixNop( w1, w2 : word ) : dWord; assembler; register;
asm
     Nop
end;

function MixAsm( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    EBX

     Xor     EBX,    EBX    // обнуляем временный результат
     Mov     ECX,    01h    // устанавливаем маску единичного бита

@@10:
     Test    EAX,    01h    // проверяем бит для w1
     Jz      @@20

     Or      EBX,    ECX    // устанавливаем единичный бит w1

@@20:
     Shl     ECX,    01h    // сдвигаем маску единичного бита для w2
     Test    EDX,    01h    // проверяем бит для w2
     Jz      @@30

     Or      EBX,    ECX    // устанавливаем единичный бит w2

@@30:
     Shr     EAX,    01h    // сдвигаем w1 для проверки следующего бита
     Shr     EDX,    01h    // сдвигаем w2 для проверки следующего бита

     Shl     ECX,    01h    // сдвигаем маску единичного бита для w1
     Jecxz   @@40

     Jmp     @@10

@@40:
     Mov     EAX,    EBX

     Pop     EBX
end;

function MixPas( w1, w2 : word ) : dWord;
// реализация alekcvp
var
  i : integer;
  Mask : dWord;
begin
  Result := 0;
  for i := 15 downto 0 do
  begin
    Mask := 1 shl i;
    Result := Result shl 1 or DWORD(w1 and Mask) shl 1 or DWORD(w2 and Mask);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Nop : Int64;

  function Exec( Mix : TMixFunc ) : Int64;
  var
    t1, t2 : Int64;
    i : integer;
  begin
    QueryPerformanceCounter( t1 );
    for i := 1 to 1000000 do
      Mix( $1234, $4321 );
    QueryPerformanceCounter( t2 );
    Result := t2 - t1;
  end;

begin
  Nop := Exec( MixNop );
  Label1.Caption := 'Asm: ' + IntToStr( Exec( MixAsm ) - Nop );
  Label2.Caption := 'Pas: ' + IntToStr( Exec( MixPas ) - Nop );
end;



У меня получился выигрыш ~17%
...
Рейтинг: 0 / 0
Микширование бит
    #40022869
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вариант alekcvp мне нравиться больше.
...
Рейтинг: 0 / 0
Микширование бит
    #40022870
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Корректность работы проверяли?
...
Рейтинг: 0 / 0
Микширование бит
    #40022872
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp
SOFT FOR YOU,

Ну у меня как-то так получилось в блокнотике:
Код: pascal
1.
2.
3.
4.
5.
6.
Result := 0; // DWORD;
for var i := 15 downto 0 do
begin
  Mask := 1 shl i; // Word
  Result := Result shl 1 or DWORD(WordA and Mask) shl 1 or DWORD(WordB and Mask);
end;



Почему "Result shl 1" ?
...
Рейтинг: 0 / 0
Микширование бит
    #40022873
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Корректность работы проверяли?

asm проверял
функцию alekcvp - нет (вместо нее SOFT FOR YOU обещался свою выложить)
...
Рейтинг: 0 / 0
Микширование бит
    #40022876
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Та-даааа )

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
unit Unit1;

{$O+}

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  TMixFunc = function ( w1, w2 : word ) : dWord;

function MixNop( w1, w2 : word ) : dWord; assembler; register;
asm
     Nop
end;

function MixAsm( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    EBX

     Xor     EBX,    EBX    // обнуляем временный результат
     Mov     ECX,    01h    // устанавливаем маску единичного бита

@@10:
     Test    EAX,    01h    // проверяем бит для w1
     Jz      @@20

     Or      EBX,    ECX    // устанавливаем единичный бит w1

@@20:
     Shl     ECX,    01h    // сдвигаем маску единичного бита для w2
     Test    EDX,    01h    // проверяем бит для w2
     Jz      @@30

     Or      EBX,    ECX    // устанавливаем единичный бит w2

@@30:
     Shr     EAX,    01h    // сдвигаем w1 для проверки следующего бита
     Shr     EDX,    01h    // сдвигаем w2 для проверки следующего бита

     Shl     ECX,    01h    // сдвигаем маску единичного бита для w1
     Jecxz   @@40

     Jmp     @@10

@@40:
     Mov     EAX,    EBX

     Pop     EBX
end;

function MixPas( w1, w2 : word ) : dWord;
// реализация alekcvp
var
  i : integer;
  Mask : dWord;
begin
  Result := 0;
  for i := 15 downto 0 do
  begin
    Mask := 1 shl i;
    Result := Result shl 1 or DWORD(w1 and Mask) shl 1 or DWORD(w2 and Mask);
  end;
end;

function MixPlane(w1, w2 : word ) : dWord;
// реализация SoftForYou
var
  X: Cardinal;
begin
  X := (Cardinal(w2) shl 16) + Cardinal(w1);

  Result := Cardinal(w1) and (1 shl 0);
  Inc(Result, (X and (1 shl 1)) shl 1);
  Inc(Result, (X and (1 shl 2)) shl 2);
  Inc(Result, (X and (1 shl 3)) shl 3);
  Inc(Result, (X and (1 shl 4)) shl 4);
  Inc(Result, (X and (1 shl 5)) shl 5);
  Inc(Result, (X and (1 shl 6)) shl 6);
  Inc(Result, (X and (1 shl 7)) shl 7);
  Inc(Result, (X and (1 shl 8)) shl 8);
  Inc(Result, (X and (1 shl 9)) shl 9);
  Inc(Result, (X and (1 shl 10)) shl 10);
  Inc(Result, (X and (1 shl 11)) shl 11);
  Inc(Result, (X and (1 shl 12)) shl 12);
  Inc(Result, (X and (1 shl 13)) shl 13);
  Inc(Result, (X and (1 shl 14)) shl 14);
  Inc(Result, (X and (1 shl 15)) shl 15);
  Inc(Result, (X and (1 shl (16 + 0))) shr (16 + 0 - 1));
  Inc(Result, (X and (1 shl (16 + 1))) shr (16 + 1 - 1));
  Inc(Result, (X and (1 shl (16 + 2))) shr (16 + 2 - 1));
  Inc(Result, (X and (1 shl (16 + 3))) shr (16 + 3 - 1));
  Inc(Result, (X and (1 shl (16 + 4))) shr (16 + 4 - 1));
  Inc(Result, (X and (1 shl (16 + 5))) shr (16 + 5 - 1));
  Inc(Result, (X and (1 shl (16 + 6))) shr (16 + 6 - 1));
  Inc(Result, (X and (1 shl (16 + 7))) shr (16 + 7 - 1));
  Inc(Result, (X and (1 shl (16 + 8))) shr (16 + 8 - 1));
  Inc(Result, (X and (1 shl (16 + 9))) shr (16 + 9 - 1));
  Inc(Result, (X and (1 shl (16 + 10))) shr (16 + 10 - 1));
  Inc(Result, (X and (1 shl (16 + 11))) shr (16 + 11 - 1));
  Inc(Result, (X and (1 shl (16 + 12))) shr (16 + 12 - 1));
  Inc(Result, (X and (1 shl (16 + 13))) shr (16 + 13 - 1));
  Inc(Result, (X and (1 shl (16 + 14))) shr (16 + 14 - 1));
  Inc(Result, (X and (1 shl (16 + 15))) shr (16 + 15 - 1));
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Nop : Int64;

  function Exec( Mix : TMixFunc ) : Int64;
  var
    t1, t2 : Int64;
    i : integer;
  begin
    QueryPerformanceCounter( t1 );
    for i := 1 to 1000000 do
      Mix( $1234, $4321 );
    QueryPerformanceCounter( t2 );
    Result := t2 - t1;
  end;

begin
  Nop := Exec( MixNop );
  Label1.Caption := 'Asm: ' + IntToStr( Exec( MixAsm ) - Nop );
  Label2.Caption := 'Pas: ' + IntToStr( Exec( MixPas ) - Nop );
  Label3.Caption := 'Plane: ' + IntToStr( Exec( MixPlane ) - Nop );
end;

...
Рейтинг: 0 / 0
Микширование бит
    #40022878
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUогромных заранее рассчитанных таблиц?

Табличка в 256 word (то бишь 512 байт) - огромна?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Микширование бит
    #40022879
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU

Пример:

0101010101010101 op 1100111000111100 = 0111001001110110111001110010

Похоже, у меня ошибка - в ТЗ младший бит результата = младший бит 2-го аргумента
У меня наоборот.
Вот подправленный вариант (на скорость не влияет):
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
function MixAsm( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    EBX

     Xor     EBX,    EBX    // обнуляем временный результат
     Mov     ECX,    01h    // устанавливаем маску единичного бита

@@10:
     Test    EDX,    01h    // проверяем бит для w2
     Jz      @@20

     Or      EBX,    ECX    // устанавливаем единичный бит w2

@@20:
     Shl     ECX,    01h    // сдвигаем маску единичного бита
     Test    EAX,    01h    // проверяем бит для w1
     Jz      @@30

     Or      EBX,    ECX    // устанавливаем единичный бит w1

@@30:
     Shl     ECX,    01h    // сдвигаем маску единичного бита
     Jecxz   @@40

     Shr     EAX,    01h    // сдвигаем w1 для проверки следующего бита
     Shr     EDX,    01h    // сдвигаем w2 для проверки следующего бита
     Jmp     @@10

@@40:
     Mov     EAX,    EBX

     Pop     EBX
end;


Результаты asm и pas совпадают.
...
Рейтинг: 0 / 0
25 сообщений из 104, страница 1 из 5
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]