Эффективный код для определения, какое из двух чисел больше

Question

У меня есть два символьных массива (каждый из многих байтов длиной; например, каждый может быть 10-12 байтов), и они представляют число в двоичном формате.Я хочу проверить, больше ли одно число, чем другое.Какой самый эффективный способ проверить, какой из двух является самым крупным?Есть ли побитовые операции, которые можно выполнить, чтобы эффективно определить это?

Answer 1

Простое решение состоит в том, чтобы сравнить их от старшего к младшему значащему байту:

// assuming MSB is at index 0
for(int i = 0; i < len; ++i) {
    if(a[i] > b[i]) return a;
    if(b[i] > a[i]) return b;
}
// what to return if they're equal?
return a;

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

Вы можете улучшить это, рассматривая массивы char как массивы unsigned (или лучше, тип с размером, равным машинному слову), еслиих размер кратен sizeof(unsigned), так как это сделает сравнение по словам.

Answer 2

Я предполагаю, что это тип данных bignum. У вас есть 10-12 символов для хранения 80-96-битных целочисленных значений. Для простоты я собираюсь принять значения без знака.

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

Но так как вы получаете эти значения по проводам, кажется странным, что класс bignum является узким местом. Конечно, сеть будет вашим узким местом. Более того, хороший класс Bignum будет хорошо оптимизирован. Почему ваш собственный код побил его?

Answer 3

Я думаю, что вы можете сначала использовать два указателя, чтобы указать на первый ненулевой байт в обоих (слева). Если теперь две эффективных длины отличаются, выведите более длинную. Я имею в виду, давайте предположим, что first - это 10 байтов, а second - это 12 байтов. Байт 4 (first[3]) - первый ненулевой байт в first, а байт 2 (second[1]) - первый ненулевой байт в second. Теперь эффективная длина из first равна 7 байтов, а second равна 11. Очевидно, second больше.

Теперь для равных эффективных длин . Сравните байты. Если равны, переходите к следующему. Иначе, больший байт существует в большем числе, и мы заканчиваем.

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

Answer 4

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

Если значения подписаны, в зависимости от кодировки (например, дополнения к 2), первая итерация, возможно, должна быть особым случаем.

РЕДАКТИРОВАТЬ: Вы только что прокомментировали, что числа без знака, поэтому это должно быть довольно просто, и вам нужно беспокоиться только о первой части.