2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Как реализуется сравнение чисел в компьютере?
Сообщение31.10.2012, 20:48 


26/08/12
45
Собственно не понятно как реализуется сравнение двух чисел на компьютере.
Т.е. как узнаётся отношение между числами >, < или ==(равенство).

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


05/09/12
2587
Как и все остальное - с помощью небольшого набора команд процессора RISK или CISC архитектуры. А конкретно в каждом случае - как компилятор переведет на этот язык код программера и оптимизирует его в соответствии со своими предустановками.

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


26/08/12
45
_Ivana в сообщении #638475 писал(а):
Как и все остальное - с помощью небольшого набора команд процессора RISK или CISC архитектуры. А конкретно в каждом случае - как компилятор переведет на этот язык код программера и оптимизирует его в соответствии со своими предустановками.

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

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


05/09/12
2587
В интернете. Про форматы представления чисел, фиксированные и плавающие запятые, знаковые биты, ассемблерные команды и т.п. Также можно написать простейшие операции сравнения в программке на С и посмотреть листинг ассемблерного кода, который наваял компилятор, разобраться в нем.

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

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


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

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

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


05/09/12
2587
zm_sansan в сообщении #638506 писал(а):
То есть как я понимаю всё сходится к проверке значений определённых ячеек в регистре.
А в компьютере кроме нулей и единичек в ячейках регистров вообще ничего нет.
zm_sansan в сообщении #638506 писал(а):
Просто хотелось бы выяснить существует ли какой-нибудь математический алгоритм сравнения чисел, без сравнение через сравнение.
Сказано сильно, но непонятно. Поясните вашу мысль.

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

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


27/04/09
28128
Пока мысль не пояснена, рискну спросить.

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

Дано два числа $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 


31/10/12
5
Если рассматривать процессоры древние x86-процессоры 8086, то инструкция сравнения на самом деле это инструкция вычитания одного числа из второго, но без записи результата в регистр, но зато с установкой флагов. По флагам "перенос", "переполнение" можно таким образом определить, какое число было больше. Если стоит флаг "ноль", то значит числа были одинаковые.
Поздние x86-процессоры с точки зрения программера работают так же, но внутри там, конечно, всё может быть сильно по-другому.

 Профиль  
                  
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение01.11.2012, 12:11 


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

Я просто думал, что проверка результата на ноль и просмотр знакового бита осуществляется через проверку на равенство с нулём или единицей. Типа "если(результат ==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 


05/09/12
2587
Все очень просто - в компьютере есть только биты, которые могут принимать только 2 значения - 0 и 1. И есть коротенький (порядка полутора десятков) набор команд процессора для работы с ними. Все остальное - уже натянутые на это абстракции: байты, числа, строки, массивы, типы, данные, протоколы, форматы, среды, операционные системы и т.д.

 Профиль  
                  
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение01.11.2012, 12:57 


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

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

 Профиль  
                  
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение01.11.2012, 14:21 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
Ч. Петцольд Код. Тайный язык информатики. - М.: Русское издательство, 2001.

 Профиль  
                  
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение03.11.2012, 09:46 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
profrotter в сообщении #638731 писал(а):

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

 Профиль  
                  
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение03.11.2012, 10:18 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
1. На странице, на которую ведёт моя ссылка, выбираете depositfiles.com
2. На depositfiles.com давите на кнопку "обычное скачивание"
3. В форме запроса о получении пробного "голд-статуса" давите на ссылку "нет, спасибо".
4. Ждёте 60 секунд.
5. вводите данные в форму защиты от роботов (1-2 раза)
6. Нажимаете на кнопку "скачать файл"

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

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

 Профиль  
                  
 
 Re: Как реализуется сравнение чисел в компьютере?
Сообщение03.11.2012, 12:48 
Аватара пользователя


31/10/08
1244
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  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group