Как компьютер определяет, является ли число меньше или больше другого?

34

Это может звучать как глупый вопрос, но мне действительно интересно узнать, как компьютер знает, что ? Кроме того, как компьютер узнает, что порядок целых чисел равен и алфавит A, B, C, D, ...? Это где-то хранится в оборудовании или операционная система предоставляет такую ​​информацию?1 , 2 , 3 , 4 , 5 , 1<21,2,3,4,5,...

Рики Стам
источник
1
Для того чтобы на этот вопрос можно было ответить удовлетворительно, нам нужно знать, что Рикки Стам знает о компьютерной архитектуре. Из вопроса это выглядит очень мало, поэтому ни один из причудливых ответов ниже не будет для него понятным.
Андрей Бауэр
@AndrejBauer: На самом деле, он не вошел в систему с тех пор, как задал вопрос. Может быть, он теперь знает все, что ему нужно.
Дэйв Кларк

Ответы:

31

Сначала ваши целые числа преобразуются в двоичные числа. Например, целое число 2 преобразуется в 0010.

ЦП использует цифровой компаратор :

Цифровой компаратор или величина компаратор представляет собой электронное устройство , аппаратное обеспечение , которое принимает два числа в качестве входных данных в двоичной форме и определяет , является ли одно число больше или меньше или равна другой номер.

Компараторы используются в центральных процессорах (ЦП) и микроконтроллерах.

Источник: https://en.wikipedia.org/wiki/Digital_comparator

В оборудовании компаратора используются некоторые вентили (AND, OR, NAND, NOR, XOR и т. Д.). Эти ворота принимают двоичные входы и дают результат в двоичном виде. Вывод можно увидеть из таблицы истинности.

Inputs           Outputs
A   B     A>B    A=B    A<B
0   0     0       1      0
0   1     0       0      1
1   0     1       0      0
1   1     0       1      0

Здесь 0& 1электронные напряжения для ворот.
1- Представляет некоторое пороговое напряжение, которое указывает на некоторое положительное напряжение.
0- Представляет напряжение ниже порога.

Например, предположим, что компаратор работает на 5 вольт (это рассмотрение для объяснения) тогда:
Напряжение более 3 вольт можно рассматривать как binary-1.
Напряжение ниже 3 вольт считаетсяbinary-0

Если логический элемент получает один вход как 3,5 вольт, а другой вход как 2 вольт, то он считает, что он принимает один вход как двоичный 1 и другой вход как двоичный 0.

Эти последовательности единиц и нулей очень быстро передаются через схему переключения.

Работа двухразрядного цифрового компаратора может быть выражена в виде таблицы истинности:

 Inputs                            Outputs
   A1   A0  B1  B0  A>B    A=B   A<B        
    0   0   0   0    0      1     0
    0   0   0   1    1      0     0
    0   0   1   0    1      0     0
    0   0   1   1    1      0     0
    0   1   0   0    0      0     1
    0   1   0   1    0      1     0
    0   1   1   0    1      0     0
    0   1   1   1    1      0     0
    1   0   0   0    0      0     1
    1   0   0   1    0      0     1
    1   0   1   0    0      1     0
    1   0   1   1    1      0     0
    1   1   0   0    0      0     1
    1   1   0   1    0      0     1
    1   1   1   0    0      0     1
    1   1   1   1    0      1     0

Цитировать из Википедии :

Примеры: рассмотрим два 4-битных двоичных числа A и B, такие, что
введите описание изображения здесь
введите описание изображения здесь
здесь каждый нижний индекс представляет одну из цифр в числах.

равенство

Двоичные числа A и B будут равны, если все пары значащих цифр обоих чисел равны, т
введите описание изображения здесь. Е. введите описание изображения здесь, введите описание изображения здесь, введите описание изображения здесь

Поскольку числа являются двоичными, цифры равны 0 или 1, а логическая функция для равенства любых двух цифр введите описание изображения здесьи> введите описание изображения здесьможет быть выражена как
введите описание изображения здесь

введите описание изображения здесь 1, только если введите описание изображения здесьи введите описание изображения здесь равны.

Для равенства A и B все введите описание изображения здесьпеременные (для i = 0,1,2,3) должны быть равны 1. Таким образом, условие качества A и B может быть реализовано с использованием операции AND в качестве
введите описание изображения здесь
двоичной переменной (A = B) равен 1, только если все пары цифр двух чисел равны.

Неравенство

Чтобы вручную определить большее из двух двоичных чисел, мы проверяем относительные величины пар значащих цифр, начиная с самого старшего бита, постепенно продвигаясь к младшим значащим битам, пока не будет найдено неравенство. Когда найдено неравенство, если соответствующий бит A равен 1, а бит B равен 0, то мы заключаем, что A> B. Это последовательное сравнение может быть логически выражено как:

введите описание изображения здесь

Ravindra Bagale
источник
2
Вау, что здесь происходит?
Жиль "ТАК - перестань быть злым"
1
«Сначала ваши целые числа преобразуются в двоичные числа» ... неправильно, во-первых, в памяти есть только двоичные числа, все 1 и 0 на машинном уровне, поэтому «преобразования» нет, 2 обозначается как 10 от начала до конца ..
Dr.Haimovitz
При копировании материалов из других источников вы должны предоставить правильную ссылку на свои источники. Смотрите здесь и здесь .
DW
Таблица двухразрядного цифрового компаратора неверна. ijesi.org/papers/Vol(2)1%20(version%202)/C211324.pdf, когда A1, A0 оба равны нулю, а B0 и B1 равны 0, 1 A> B будет 0, например.
user1455116
14

Он не просто «знает», он проверяет каждый раз. По сути, он делает то же самое, что и вы: для сравнения он проверяет (слева), какое число имеет первую цифру, которая больше соответствующей цифры в другом номере. Конечно, вы должны добавить ведущие нули к более короткому числу.

Буквы - это просто цифры для компьютера. Людям присваиваются буквы , например, ASCII или Unicode , так что сравнения чисел также дают «правильный» порядок для букв.

Рафаэль
источник
Кроме того, это обычно называют " лексикографическим порядком ". Обычно мы можем думать об этом как о порядке упорядочения по длине (от самого короткого до самого длинного), а затем в алфавитном порядке.
Усул
@usul Это напоминает мне, что особенности сравнения целых чисел, очевидно, зависят от конкретной кодировки; То, что я описываю, работает для «наивных» двоичных чисел, которые могут быть далеки от того, что использует реальный процессор.
Рафаэль
Да, абсолютно. Я слишком много думал о машинах Тьюринга в последнее время :). Реальные машины не совсем соответствуют тому, что мы говорили здесь все время ...
usul
9

Это не операционная система, которая сравнивает целые числа, процессор заботится об этом. Это сделано на уровне логических ворот, пожалуйста, обратитесь к этим слайдам, чтобы увидеть, как это можно сделать.

Что касается алфавита, то в ASCII буквенно-цифровые и другие специальные символы представлены в виде целых чисел, поэтому сравнение их также является операцией сравнения целых чисел, которая выполняется ЦП.

Бартош Прзыбыльски
источник
4

На самом деле, и для того, чтобы получить его полное изображение, я думаю, что было бы весьма полезно увидеть собственными глазами путь к данным реального процессора, например MIPS: введите описание изображения здесь

Как вы можете видеть, на самом деле есть второй выход из АЛУ, который является сигналом под названием Ноль. Он существует для выполнения быстрых операций ветвления, после определения, равны ли два операнда сравнения нулю или нет , так как большинство сравнений в программе относятся к ветвям. Поэтому, когда вы создаете возможность ветвления в вашем коде, например:

if (a <b) {...}

Это переводится в машинный код, например, в мипс : blt s0, s1, If  если a <b выполнить инструкции в скобках, иначе продолжить выполнение вне if {}. В частности, эта инструкция является псевдоинструкцией, что означает, что она переводится в две другие (простые) инструкции MIPS. 
slt at, s0, s1, а затем bne at, ноль, If (slt: установить меньше, чем & bne: ветвь на неравных).

Обратите внимание, что нулевой сигнал является одним из входов логического элемента И, который определяет, откуда Программный счетчик (ПК) будет принимать свое значение: Предполагая, что сигнал ветвления равен '1', поскольку у нас есть операция ветвления

  • Ноль = 0 Результат вычитания не был равен нулю, поэтому мультиплексор выберет адрес из целевой ветви, и выполнение будет продолжено из инструкции, которую ведет ветвь.
  • Ноль = 1 Результат был 0 (a = b), поэтому MUX выбирает адрес из сумматора, где вычисляется адрес следующей инструкции в обычном исполнении (последовательный). Прыжок не выполняется, так как условие (a <b) недопустимо.

Надеюсь, я помог вам увидеть "под капотом". Не стесняйтесь просить дальнейшего анализа по этому вопросу. Многие вещи мы считаем само собой разумеющимся, процессоры делают их очень увлекательно!

Итан
источник
Итан, как работает операция "меньше" в этом канале данных? Как я понимаю, вы описали операцию "не равной". Что значит "slt" инструкция?
osgx
2

Если вы хотите узнать о том, как это делает настоящий процессор, это что-то вроде этого.

Процессор работает на числах только до определенного размера. В настоящее время это обычно 64-битные целые числа (мы будем игнорировать числа с плавающей точкой; идея будет аналогичной).

Таким образом, мы должны признать, что

  1. Процессор хранит числа до (скажем) 64-битных в двоичном, в некотором формате (вероятно, с дополнением 2s, но это не имеет большого значения, что).

  2. Процессор не может ничего сделать с числами, большими этого. Мы должны написать программные алгоритмы, если мы хотим сравнить большие числа.

Итак, скажем, у нас есть два числа, каждое из которых помещается в 64-разрядное целое число обычного размера. Сказатьa а также б, Как процессор сравнивает их? Обычно он вычитает одно из другого (это отдельная нативная операция, реализованная на аппаратном уровне).

Теперь процессор сохранил одно число a-б, Опять же, это число не более 64 бит, поэтому оно помещается в «регистр» длиной 64 бита, в котором мы храним наши числа для расчета. Теперь он просто проверяет,a-бменьше нуля. Это делается с помощью единственной собственной операции, которая может работать на уровне схемы, как алгоритмы сравнения, описанные в других ответах. Это будет выглядеть примерно так, но все они реализованы в схемах (поскольку число составляет не более 64 бит, это схема определенного размера, которую мы можем подключить и прикрепить к ЦП.) В зависимости от того, как ЦП хранит числа, может быть даже быстрее, потому что все отрицательные числа могут иметь первый бит, равный единице, или что-то в этом роде. В любом случае, всего 64 бита, поэтому мы можем точно проверить, является ли это число отрицательным.

Если это так, то мы знаем a<б; если нет, то мы знаемaб,

Теперь для больших чисел мы должны реализовать что-то в программном обеспечении, которое будет использовать эти небольшие сравнения в качестве подпрограмм.

усул
источник
1

Чтобы ответить на этот вопрос, позвольте мне сначала указать, что существует по крайней мере два уровня абстракции для чисел сравнения на компьютере, на уровне машины и на уровне программного обеспечения .

Сравнение чисел на машинном уровне

В современном компьютере процессор имеет богатый набор инструкций. Эти инструкции включают в себя, например, загрузку ячейки памяти в регистр, увеличение регистра, добавление двух регистров и многое другое. Также должны быть инструкции для условных переходов . Например, процессоры семейства Intel x86 поддерживают инструкции jnz(переход, если не ноль), jne(переход не равен) и так далее. Если они будут отсутствовать, то процессор не будет завершен по Тьюрингу. Переменные, от которых зависит условный переход, сохраняются в регистрах. Таким образом, эти инструкции встроены в архитектуру ЦП как схема, построенная из логических элементов. Только так процессор может сравнивать два числа.

Сравнение чисел на уровне программного обеспечения

Если вы сравните два числа, скажем, в программе на С ++, то это преобразуется в машинный код и поэтому выполняется на машинном уровне. Однако такое сравнение может быть более сложным. Это действительно зависит от того, какой тип данных вы использовали, как сравнение переводится в машинный код. Просто один пример, числа, которые вы хотите сравнить, взяты из 64-битных слов, но ваша машина работает только с 32-битными. Тогда это число не помещается в регистр, следовательно, компилятор разбивает сравнение на последовательность сравнений на уровне машинного кода. То же самое относится к более сложным типам данных / структурам данных, представляющим, например, рациональные числа, или строки, или символы. Следовательно, когда вам нужно сравнить два символа, это должно быть переведено программным обеспечением (операционная система, компилятор, интерпретатор, ...) в машинный код.

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

A.Schulz
источник
0

другие ответы хороши, просто добавьте еще один для дальнейшего рассмотрения / изучения с CS-вкусом / изюминкой. Можно построить FSM , конечный автомат, который может сравнивать два двоичных числа любой длины, начиная попарно от старших значащих битов и заканчивая младшим значащим битом (LSB). он также может быть использован для концептуализации цифрового компаратора, приведенного в другом ответе, однако FSM не требует двоичных чисел конечной длины. он может даже работать с целыми числами с двоичными дробями после LSB. он имеет индуктивный и рекурсивный вкус и может быть доказан правильным путем простой индукции. это работает следующим образом:

  • введите две верхние двоичные цифры в виде пары (a, b)
  • если a = 1 и b = 0, левое число больше.
  • если a = 0 и b = 1, правильное число больше.
  • в противном случае числа «равны по времени», переходите к следующей паре.

другими словами, наибольшее число - это число с первым появлением бита, равным единице, а другое - нулем, после начального цикла, состоящего из нуля или более идентичных единиц. цифровой компаратор конечной длины, состоящий из вентилей или 1-битных компараторов, можно рассматривать как основанный на фиксировании длины этой операции FSM к некоторому фиксированному числу битов. (да, существует сильная связь между всеми конечными цепями и «фиксированием длины» вычислений FSM.)

это может показаться теоретическим упражнением, но на самом деле логика в программном обеспечении для представления произвольных чисел точности работает в чем-то аналогично этому FSM, за исключением того, что оно закодировано в компьютерном цикле, которое можно рассматривать как зацикливание или моделирование шагов FSM (эффективная реализация может отслеживать через индекс местоположение MSB).


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

в основном это работает, сравнивая показатель степени и мантиссу, где число находится в формеa×10б, aмантисса, б экспонента. мантисса может быть нормализована до числа, где первая цифра всегда отлична от нуля. затем для сравнения двух чисел логика сначала сравнивает показателиби, если они неравны, он может вернуть результат без сравнения мантисс (используя, скажем, схему компаратора). если показатели равны, он сравнивает мантиссы.

ВЗН
источник