2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 20:48 
Собственно не понятно как реализуется сравнение двух чисел на компьютере.
Т.е. как узнаётся отношение между числами >, < или ==(равенство).

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 21:13 
Как и все остальное - с помощью небольшого набора команд процессора RISK или CISC архитектуры. А конкретно в каждом случае - как компилятор переведет на этот язык код программера и оптимизирует его в соответствии со своими предустановками.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 21:28 
_Ivana в сообщении #638475 писал(а):
Как и все остальное - с помощью небольшого набора команд процессора RISK или CISC архитектуры. А конкретно в каждом случае - как компилятор переведет на этот язык код программера и оптимизирует его в соответствии со своими предустановками.

А не знаете где можно прочитать подробнее про сам механизм, алгоритм реализации сравнения?

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 21:53 
В интернете. Про форматы представления чисел, фиксированные и плавающие запятые, знаковые биты, ассемблерные команды и т.п. Также можно написать простейшие операции сравнения в программке на С и посмотреть листинг ассемблерного кода, который наваял компилятор, разобраться в нем.

ЗЫ лично я, когда писал на ассемблере с использованием формата плавающей запятой, сравнивал вручную следующим образом - вычитал одно число из другого (с помощью функции из пары десятков команд) и проверял результат на ноль и смотрел его знаковый бит.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 22:03 
Цитата:
ЗЫ лично я, когда писал на ассемблере с использованием формата плавающей запятой, сравнивал вручную следующим образом - вычитал одно число из другого (с помощью функции из пары десятков команд) и проверял результат на ноль и смотрел его знаковый бит.

Это я уже понял. Но тут как-то сравнение через сравнение. Проверить результат на ноль и смотреть знаковый бит это же тоже вроде как сравнение.
То есть как я понимаю всё сходится к проверке значений определённых ячеек в регистре. А далее наверняка к логике, электрическим сигналам и т.д. к физике Вселенной) Это конечно нормально. Просто хотелось бы выяснить существует ли какой-нибудь математический алгоритм сравнения чисел, без сравнение через сравнение.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 22:16 
zm_sansan в сообщении #638506 писал(а):
То есть как я понимаю всё сходится к проверке значений определённых ячеек в регистре.
А в компьютере кроме нулей и единичек в ячейках регистров вообще ничего нет.
zm_sansan в сообщении #638506 писал(а):
Просто хотелось бы выяснить существует ли какой-нибудь математический алгоритм сравнения чисел, без сравнение через сравнение.
Сказано сильно, но непонятно. Поясните вашу мысль.

UPD давайте так - сравнение (чисел) - некая бинарная операция. которая может возвращать всего три значения - равно, больше, меньше. Что вы хотите из этого выжать далее? Аналогии с расположением точек слева-справа на координатной прямой?

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 22:18 
Пока мысль не пояснена, рискну спросить.

Чем, например, следующий алгоритм сравнения чисел в дополнительном коде не «математический»?

Дано два числа $A$ и $B$, заданные двоичными строками $a \equiv (a_0,a_1,\ldots,a_n)$ и $b \equiv (b_0,b_1,\ldots,b_n)$.
1. Получаем разность $C = A - B$, вычитая по соотв. алгоритму $b$ из $a$ и получая представление $c \equiv (c_0,c_1,\ldots,c_n)$. Вычисление разности выглядит вполне понятным и «математизируемым», но здесь его долго описывать — ТС наверняка знает, как разность в дополнительном коде вычисляется.
2. Проверяем, совпадают ли записи $c$ и $(0,0,\ldots,0)$ — это выполняется, если совпадают попарно каждые компоненты записей. Если совпадают, выходим с результатом $A = B$.
3. Проверяем, совпадает ли $c_0$ (знаковый бит) с $1$. Если да, результат $A < B$. Если нет, $A > B$.


Как-нибудь разложить проверку совпадения двух «атомарных» значений нельзя.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 23:01 
Если рассматривать процессоры древние x86-процессоры 8086, то инструкция сравнения на самом деле это инструкция вычитания одного числа из второго, но без записи результата в регистр, но зато с установкой флагов. По флагам "перенос", "переполнение" можно таким образом определить, какое число было больше. Если стоит флаг "ноль", то значит числа были одинаковые.
Поздние x86-процессоры с точки зрения программера работают так же, но внутри там, конечно, всё может быть сильно по-другому.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение01.11.2012, 12:11 
Цитата:
ЗЫ лично я, когда писал на ассемблере с использованием формата плавающей запятой, сравнивал вручную следующим образом - вычитал одно число из другого (с помощью функции из пары десятков команд) и проверял результат на ноль и смотрел его знаковый бит.

Я просто думал, что проверка результата на ноль и просмотр знакового бита осуществляется через проверку на равенство с нулём или единицей. Типа "если(результат ==0)..". То есть операция сравнения исходных чисел выражается через сравнение результата вычитания с нулём и просотра знакового бита тем же сранением с 0 или 1. Получается тупик, так как сравнение выражается через сравнение.
Но потом понял, что ту же проверку на ноль или на значение знакового бита можно реализовать через Булеву логику, т.е. "если ($\neg$результат ^ 1)...", т.е. проверка осуществляется через какую либо бинарную операция. Вычитание тоже можно реализовать с помощью Булевой логики. А булева логика в компе реализуется с помощью логических элементов, реализующих какую либо бинарную операция. Из Вики: Физически логические элементы могут быть выполнены механическими, электромеханическими (на электромагнитных реле), электронными (на диодах и транзисторах), пневматическими, гидравлическими, оптическими и др.
То есть мне теперь понятно, что сравнение можно реализовать так:
(часть уже тут описали)
Дано два числа $A$ и $B$, заданные двоичными строками $A\equiv(a_0,...,a_n)$ и $B\equiv(b_0,...,b_n)$.
1. Получаем разность $C = A - B$, где $C\equiv(c_0,...,c_n)$. Вычисление разности выглядит вполне понятным и «математизируемым», но здесь его долго описывать — ТС наверняка знает, как разность в дополнительном коде вычисляется. (Я так пониманию, что разность теме же бинарными операциями осуществляется)
2. Проверяем, совпадают ли записи C и $(0_0,...,0_n)$— это выполняется, если совпадают попарно каждые компоненты записей. Если совпадают, выходим с результатом $A=B$. (Совпадение проверяем той же бинарной операцией)
3. Проверяем, совпадает ли $c_0$(знаковый бит) с 1 . Если да, результат $A<B$. Если нет, $A>B$.
Может в компе это не совсем так и реализуется, но это один из работоспособных результатов.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение01.11.2012, 12:46 
Все очень просто - в компьютере есть только биты, которые могут принимать только 2 значения - 0 и 1. И есть коротенький (порядка полутора десятков) набор команд процессора для работы с ними. Все остальное - уже натянутые на это абстракции: байты, числа, строки, массивы, типы, данные, протоколы, форматы, среды, операционные системы и т.д.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение01.11.2012, 12:57 
_Ivana в сообщении #638690 писал(а):
Все очень просто - в компьютере есть только биты, которые могут принимать только 2 значения - 0 и 1. И есть коротенький (порядка полутора десятков) набор команд процессора для работы с ними. Все остальное - уже натянутые на это абстракции: байты, числа, строки, массивы, типы, данные, протоколы, форматы, среды, операционные системы и т.д.

Да, уже понятно=) Спасибо, всем, что помогли разобраться!

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение01.11.2012, 14:21 
Аватара пользователя
Ч. Петцольд Код. Тайный язык информатики. - М.: Русское издательство, 2001.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение03.11.2012, 09:46 
Аватара пользователя
profrotter в сообщении #638731 писал(а):

Ну Вы и ссылку дали! Там для получения книги надо вводить номер сотового телефона, на который придёт смс-код подтверждения... Книга мне показалась интересной, но я ещё не настолько выжил из ума, чтобы номер своего сотового направо и налево в интернете раздавать... Нельзя ли получить более приемлемую ссылку на эту книгу?

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение03.11.2012, 10:18 
Аватара пользователя
1. На странице, на которую ведёт моя ссылка, выбираете depositfiles.com
2. На depositfiles.com давите на кнопку "обычное скачивание"
3. В форме запроса о получении пробного "голд-статуса" давите на ссылку "нет, спасибо".
4. Ждёте 60 секунд.
5. вводите данные в форму защиты от роботов (1-2 раза)
6. Нажимаете на кнопку "скачать файл"

Только что проверил - скачалось. Короче, везде, где предлагают голд-аккаунт надо отказываться и выбирать бесплатное скачивание. Это обычная процедура скачивания с файлообменника depositfiles.com. Думаю, через гугл можно найти ещё массу мест, где можно взять книгу.

Если честно, когда я давал ссылку, я её не проверял. В своё время я держал в руках бумажную версию. Предупреждаю сразу: книжка для детей с фонариками и азбукой морзе - научно-популярная то бишь.

 
 
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение03.11.2012, 12:48 
Аватара пользователя
zm_sansan
Тут бы профессиональное что-то выложить, но видимо тут нет специалистов. Есть вузы в которых это подробно проходят. Если задаться вопросом то книги можно найти.

На пальцах попробую описать. Тоже в свое время как и автор интересовался этим вопросом.

Почти каждая операция выставляет флаги.
Сравнение происходит в 2 стадии.
1) Вначале выполняется операция сравнения результат заносится в регистр и выставляются флаги.
2) Затем на основе флагов выполняется условный переход.


1.1) В качестве операции сравнения обычно применяют вычитание или булевую операцию "И"
1.2) флаги существует 3-4 основных флага.
- флаг нуля;
- Флаг переноса/заёма
- флаг переполнения;
- флаг знак числа(+,-).

Выставление флага выполняется при помощи булевых операций.
К примеру флаг нуля выставляется при помощи "или не".

К примеру нам надо сравнить 2 числа на равенство. Загружаем числа в регистры вычитаем одно из другого. Процессор выставляет флаги, а после выполняется сравнение.
Код на языке высокого уровня
Код:
if a=b then
  begin
  ...
  end;
...

Этот код преобразованный в ассемблер
Код:
mov al,Byte PTR [0001]   ;// загружаем байт в регистр
mov bl,Byte PTR [0002]   ;// загружаем второй байт в другой регистр
sub al,bl                ;// вычитание
jz begin                 ;// условный переход
                         ;// jz и je обозначение одной команды, которая выполняется при zf=0
jmp end                  ;// безусловный переход
begin:                   ;// метка
  ...
end:                     ;// метка
  ...


Вот как это выглядит в эмуляторе
Код:
// Команда вычитания 8 битых чисел.
function SUB8(a,b:UInt8):UInt16;
begin
Result:=a-b;

_ZF:=Ord(Boolean(not Result));                 // Флаг нуля
_SF:=(Result  shr 7)  and 1;                   // Флаг знак числа
_PF:=Result and 1;                             // Флаг чётности(означает чёт или нечет)
_OF:= ((a xor b) and (a xor Result)) shr 7;    // Флаг переполнения
_CF:=Result  shr 8;                            // Флаг заёма или флаг переноса

_AF:=((a xor b xor Result) shr 4) and 1;       // Вспомогательный Флаг переполнения в x86 используется для десятичной арифметике
end;

// Команда условного перехода.
procedure JccNear16(ofs:Word; cc:Byte);
var Flag:Boolean;
begin
Flag:=False;
case сс of
0:Flag:=(_of=1);                        // JO
1:Flag:=not(_of=1);                     // JNO
2:Flag:=(_cf=1);                        // JB
3:Flag:=not(_cf=1);                     // JAE
4:Flag:=(_zf=1);                        // JZ  или JE  или "="
5:Flag:=not(_zf=1);                     // JNZ или JNE или "<>"
6:Flag:=(_cf=1) and (_zf=1);            // JBE
7:Flag:=not((_cf=1) and (_zf=1));       // JNA
8:Flag:=(_sf=1);                        // JS
9:Flag:=not (_sf=1);                    // JNS
$A:Flag:=(_pf=1);                       // JP
$B:Flag:=not (_pf=1);                   // JNP
$C:Flag:=(_sf<>_of);                    // JL
$D:Flag:=(_sf=_of);                     // JGE
$E:Flag:=(_zf=1) or (_sf<>_of);         // JLE
$F:Flag:=not (_zf=1) or (_sf<>_of);     // JG
end;
if Flag then
NewRegs._EIP:=(NewRegs._EIP+ofs) and $FFFF;
end;


Схемно реализовать не трудно. На логических элементах и сумматорах.
Сумматор в свою очередь реализуется, опять таки на логических элементах.
Вычитание можно сделать по разному. Если числа в дополненном коде. То можно изменить знак числа и выполнить сложение
Было:
$$a-b$$
Стало:
$$c=-b$$
$$a+c$$
Изменение знака для чисел в дополненном коде можно сделать как.
$$c=not (b)+1$$

 
 
 [ Сообщений: 24 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group