Интервалы со знаковыми числами (статья по программированию)

____ __                                                      __
\  // / -- ------------------------------------------- - -__/  \
 \ \    Intervals with signed numbers by mike/zeroteam   /  \__/
--\ -------------------------------------------------- - \__/  \
                                                            \__/

Во время программирования одного эффекта я столкнулся с интересной задачей. Мне нужно было выяснить, находится ли знаковое число ВНЕ заданного интервала, и если да, то лежит ли оно ниже или выше этого интервала. Для демонстрации определим интервал как <-6, 6).

Проблема со знаковыми числами заключается в том, что благодаря представлению «дополнительный код» (two's complement) они хорошо работают для простых вычислений, но не для сравнений.

Когда мы сравниваем числа без знака, после команды CP 6 становится ясно, меньше ли число (если установлен флаг CARRY) или больше/равно (если флаг не установлен). Однако при сравнении знаковых чисел возникает проблема: все отрицательные числа будут ошибочно оцениваться как «большие».

Попробуем составить таблицу результатов сравнения для каждой части интервала (0 означает NC, 1 означает C):

            -6     0     6
        -----<-----|-----)-----
CP  6     0     0     1     0
CP -6     1     0     1     1

 ________,-----,
 \__          /----,____,----,__  _____,----,____,----,___,----,
   /    /____/    /    /        \/    /              /         /
  /____     /    /    /    '   _/    '____/   _,    /    /__ _/
 /    /    /    /    /    /   <   /   \ /    /    /    /
/____     /________./____     /\___/    /    /    /\___     /
    /____/              `----'    /____/K-0s/____/    /____/

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

(CP 6) XOR (CP -6)

Таким образом, флаг CARRY говорит нам, находится ли значение вне диапазона, а значение знака указывает, ниже или выше интервала лежит результат. Но проблема с XOR в том, что нам нужно сохранить результаты обоих сравнений в регистрах, выполнить побитовую операцию и обработать результат. Однако если заменить функцию XOR простым сложением, результат будет тем же, и именно это предлагает нам инструкция ADC. Так как же выглядит моя попытка реализации?

   ld   b,a   ;4T
   cp   6     ;7T
   rl   c     ;8T
   cp   -6    ;7T
   ld   a,c   ;4T
   adc  a,0   ;7T   это XOR двух сравнений
   rra        ;4T
   sbc  a,a   ;4T
   ret  c     ;11/5T
   and  1     ;7T
   rl   b     ;8T
   adc  a,0   ;7T
   ret        ;10T
              ;=56/82T

Входное значение ожидается в регистре A, результат также возвращается в A: если установлен бит 1, значение ниже интервала, если установлен бит 0 — выше (напомню, моя главная задача — узнать, лежит ли значение ВНЕ интервала). Кроме того, рутина выглядит красиво, криптографично и трудночитаемо. Отличная работа, mikezt!

Давайте попробуем еще раз, но попроще. Сместим интервал на целый отрицательный отрезок:

Исходные значения: -6 0 6
-----<-----|-----)----
Смещенные значения: 0 6 12

Теперь очевидно, что достаточно сравнить смещенное значение с длиной интервала, а знак исходного числа подскажет, находится ли число ниже или выше интервала. Реализация?

   ld   c,0   ;7T
   add  a,6   ;7T
   cp   12    ;7T
   ret  c     ;11/5T
   inc  c     ;4T
   sub  6     ;7T
   ret  m     ;11/5T
   inc  c     ;4T
   ret        ;10T
              ;=32/47/54T

Входные данные снова в регистре A, но выход на этот раз в регистре C. Как видите, рутина короче, быстрее и читабельнее.

Можно ли это улучшить? Безусловно. При использовании таблицы результат выглядит так:

   ld   h,CP_TAB/256   ;7T
   ld   l,a            ;4T
   ld   a,(hl)         ;7T
                       ;=18T

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

mike/zeroteam