Сравнение двоичных чисел

← →
Delphman (2005-10-13 22:04) [0]

Допустим есть число (двоичное) заданное строкой типа string s="10001111"
Как автоматизировать следующий процесс:
Эта строка делится пополам и сравнивается:
1000<=1111
затем делится так (от цендра или концов не важно):
00<=11
10 <= 11
затем так:
1 <= 1
0 <= 1
0 <= 1
0<=1

Длина строки равна 2^n, n=2,3,4...26

Можно ли такое сделать? Чё то в голову ничего не приходит.

← →
ArtemESC © (2005-10-13 22:47) [1]

1)Перевод числа из двоичного в десятичное (если нужно)

function BinToDecimal(str: string): DWORD; var len: integer; i : integer; begin len := length(str); Result := 0; for i := 1 to len do If (str[i] = "1") then Result := Result + Round(IntPower(2, len - i)); end;

2)+ Несложные Манипуляции с shl и shr

← →
Игорь Шевченко © (2005-10-14 00:06) [2]

ArtemESC © (13.10.05 22:47) [1]

Откуда пример, если не секрет ?

← →
ArtemESC © (2005-10-14 00:19) [3]

>>Игорь Шевченко
А что не так?

← →
Fay © (2005-10-14 01:12) [4]

2 ArtemESC © (14.10.05 0:19) [3]
Сравни.

uses Math; {$DEFINE ArtemESC} {$IFDEF ArtemESC} function BinToDecimal(str : string) : DWORD; var len : integer; i : integer; begin len := length(str); Result := 0; for i := 1 to len do if (str[i] = "1") then Result := Result + Round(IntPower(2, len - i)); end; {$ELSE} function BinToDecimal(const s : String) : DWORD; var i, n : Integer; begin Result := 0; n := Length(s); for i := 1 to n do if (s[i] = "1") then Result := Result or DWORD($01 shl (n - i)); end; {$ENDIF} {$R *.dfm} procedure TForm1.Button1Click(Sender : TObject); const TEST_STR = "010101010101010101010101010101"; var pf, pc1, pc2 : Int64; i : Integer; s : String; begin s := TEST_STR; QueryPerformanceFrequency(pf); QueryPerformanceCounter(pc1); for i := 0 to 999999 do BinToDecimal(s); QueryPerformanceCounter(pc2); ShowMessage(Format("%d ms", [((pc2 - pc1) * 1000) div pf])) end;

P.S.
Нафиг ваще потребовался сопр?

← →
Fay © (2005-10-14 10:57) [5]

Delphman (13.10.05 22:04)
затем делится так (от цендра или концов не важно):
00<=11
10 <= 11
затем так:
1 <= 1
0 <= 1
0 <= 1
0<=1

Чё это значит?

← →
Игорь Шевченко © (2005-10-14 11:07) [6]

Fay © (14.10.05 01:12) [4]

function BinToDecimal(const s : String) : DWORD; var I: Integer; begin Result := 0; for i := 1 to Length(s) do if S[I] in ["0","1"] then Result := (Result shl 1) + (Ord(S[I]) - Ord("0")); else raise EConvertError.CreateFmt ("Illegal character %c", [S[I]]); end;

?

← →
Fay © (2005-10-14 11:17) [7]

2 Игорь Шевченко © (14.10.05 11:07) [6]
Вы пессимист 8)

← →
Fay © (2005-10-14 11:29) [8]

2 Игорь Шевченко © (14.10.05 11:07) [6]
... И это самый быстрый способ из уже предложенный...
8)

← →
Anatoly Podgoretsky © (2005-10-14 16:12) [9]

Не требуется самый быстрый, требуется решение именно по институтскому заданию.

← →
Fay © (2005-10-14 16:43) [10]

2 Anatoly Podgoretsky © (14.10.05 16:12) [9]
Анатолий, Вы понимаете суть задания?

← →
Anatoly Podgoretsky © (2005-10-14 16:46) [11]

Меня суть не интересовала, не готов решать задания в форумах. Да и суть не важно, надо не думать, а трясти.

← →
Delphman (2005-10-14 17:08) [12]

Переводить числа в десятичные я и сам умею, мне их нужно сравнивать именно так. Строка делится пополам, сравнивается; эти строки делются тоже пополам, сравниваются, и так далее.
Если условие верно то
Result:="+" else begin Result:="-"; exit; end;

← →
Delphman (2005-10-14 21:59) [13]

В теории это выглятит так:
http://dvo.sut.ru/libr/himath/w163rabk/7.htm
см. класс монотонных функций, может легче можно сделать, чем я тут писал.

← →
Fay © (2005-10-14 22:04) [14]

2 Delphman (14.10.05 17:08) [12]

>> Строка делится пополам, сравнивается; эти строки
>> делются тоже пополам, сравниваются и так далее.
Что "и так далее" ?

>> Если условие верно
Какое условие?

← →
palva © (2005-10-14 23:57) [15]

Да, чему теперь в институтах учат! Ничего не понятно.
Самое образованное поколение!

← →
Delphman (2005-10-15 12:56) [16]

>> Да, чему теперь в институтах учат! Ничего не понятно.
Да, еслиб это было в институте, а то в технаре, а в институте вообще ничему не учат покрайне мере в моём.

>>Какое условие?
во пример есть при длине строки 2^2:
0110
01<=10 result="+"
0 <= 0 result="+"
1<=1 result="+"

1110
11<=10 result="-" exit

1010
10<=10 result="+"
1<=0 result="-" exit

← →
Delphman (2005-10-15 13:06) [17]

<= вот это условие если выполняется, то дальше делим и сравниваем, если нет result="-" и выходим

← →
Delphman (2005-10-15 17:55) [18]

Во кое чё получилось, но бажет непойму где (хотя я вижу где, но не знаю как
исправить).

procedure TForm1.Button1Click(Sender: TObject);
const
s="1001110010011100";
var
i,j: integer;
x: real;
op1,op2: string;
begin
i:=0;x:=1;
memo1.Lines.add(s);
repeat
x:=exp(ln(2) * i);
for j:=1 to trunc(x) do begin
op1:=copy(s,j,(length(s) div 2) div trunc(x));
op2:=copy(s,(length(s) div 2)+j,(length(s) div 2) div trunc(x));
memo1.Lines.add(floattostr(x)+" op1="+op1+" op2="+op2);
end;
inc(i);
until x=length(s) div 2;
end;

← →
Delphman (2005-10-15 18:49) [19]

Во посмотрите правильно ли сдела? Может чтонибудь можно сделать для
оптимизации кода, с учётом того что длина строки может быть 2^26
procedure TForm1.Button1Click(Sender: TObject); const s="1234567887654321"; //test1 n=16 //s="12344321"; //test2 n=8 //s="1221"; //test3 n=4 //s="12"; //test4 n=2 var i,j,cols: integer; x: real; op1,op2,r: string; begin i:=0;x:=1; memo1.Lines.add(s); repeat x:=exp(ln(2) * i); cols:=(length(s) div 2) div trunc(x); for j:=1 to trunc(x) do begin op1:=copy(s,j*cols-cols+1,cols); op2:=copy(s,length(s)-(j*cols-1),cols); if strtoint(op1)<=strtoint(op2) then r:="+" else r:="-"; memo1.Lines.add(floattostr(x)+" op1="+op1+" op2="+op2+" r= "+r); end; inc(i); until x=length(s) div 2; end;

> x:=exp(ln(2) * i);

Это что?

← →
Delphman (2005-10-16 10:54) [21]

так вычисляется количество повторений

Может я чего-то не понял, но по твоим примерам сделал вот это:

function MonoFunc(const BinStr: string): Boolean; var I, L: Integer; begin Result := True; L := Length(BinStr); if L mod 2 = 0 then for I := 0 to L div 2 - 1 do if (PChar(BinStr)[I] = "1") and (PChar(BinStr)[L-(I+1)] = "0") then begin Result := False; Break; end; end; procedure TForm1.Button1Click(Sender: TObject); begin if MonoFunc(Edit1.Text) then Caption := "+" else Caption := "-"; end;

> Delphman (15.10.05 18:49) [19]

Или важно место, где возникает "-", а не то, возникает он вообще или нет?

← →
Delphman (2005-10-17 18:59) [24]

Fenik спасибо, так кароче чем у меня, но я ещё не проверял.

← →
Delphman (2005-10-18 11:20) [25]

Всё бы хорошо, но 1001 выдаёт +, а должен - т.к.
10<=01 result="-"

Блин, точно. Теперь вьехал :)
Завтра доделаю.

uses Math; function MonoFunc(const BinStr: string): Boolean; var I, J, L, N, Left, Right: Integer; begin Result := False; L := Length(BinStr); if L > 1 then begin if Frac(Log2(L)) <> 0 then Exit; { Длина строки не является степенью двойки, поэтому выходим. } N := L div 2; { длина сравниваемых подстрок } repeat Left := 0; { позиция начала текущей левой подстроки в BinStr } Right := L - N; { позиция начала текущей правой подстроки в BinStr } for I := 1 to L div (N+N) do begin for J := 0 to N - 1 do begin if PChar(BinStr)[Left + J] = "1" then begin if PChar(BinStr)[Right + J] = "0" then Exit; { Условие нарушено. Выходим с отрицательным результатом. } end else if PChar(BinStr)[Right + J] = "1" then Break; { Дальше проверять не стоит: ясно, что правое число больше левого. } end; Inc(Left, N); Dec(Right, N); end; N := N div 2; until N < 1; Result := True; end; end;

Сравнение двоичных чисел Найти похожие ветки