Ошибка на единицу

Ошибка на единицу или ошибка неучтённой единицы (англ. off-by-one error) — логическая ошибка в алгоритме, включающая в частности дискретный вариант нарушения граничных условий. Ошибка часто встречается в программировании, когда количество итераций пошагового цикла оказывается на единицу меньше или больше необходимого. Например, программист при сравнении указывает «меньше или равно», вместо «меньше», или ошибается, отсчитывая начало последовательности не с нуля, а с единицы (индексация массивов во многих языках программирования начинается с нуля).

Перебор элементов массива

Рассмотрим массив элементов, в котором обрабатываются элементы с m-го по n-й включительно. Сколько членов массива будет обработано? Ответ n-m является ошибкой на единицу и примером ошибки «заборного столба». Правильный ответ — n-m+1.

Для уменьшения ошибок из-за неучтённых единиц диапазон индексирования часто представляют полуоткрытыми интервалами. Так диапазон от m до n (включительно) представляется диапазоном от m (включительно) до n+1 (не включая последнее значение). Например, цикл, который проходит пять значений, может быть записан с использованием полуоткрытого интервала от 0 до 5 (язык C):

for (i = 0; i < 5; i++) 
{
    /* тело цикла */
}

Тело цикла выполняется, начиная с i равное 0; затем i принимает значение 1, 2, 3 и наконец на последующем шаге становится равным 4. Когда i становится равным 5, то условие i<5 не выполняется и цикл заканчивается. Однако, если условие сравнения будет <= (меньше или равно), цикл будет выполняться шесть раз: i будет принимать значения 0, 1, 2, 3, 4 и 5. Подобным же образом, если i будет инициализировано 1, а не 0, в цикле будет только 4 итерации: i примет значения 1, 2, 3 и 4. Обе эти альтернативы ведут к ошибке на единицу.

Подобная же ошибка может возникнуть, если цикл do-while используется вместо цикла while-цикл]] (или наоборот). Цикл do-while гарантирует выполнение по крайней мере одной итерации, поскольку проверка условия осуществляется после выполнения тела цикла.

Ошибки, связанные с массивами, могут также являться результатом различия в языках программирования. Отсчёт с нуля традиционен, но некоторые языки ведут отчет с 1. В языке Паскаль можно определять индексы. Это позволяет настроить модель массива на предметную область.

Ошибка заборного столба

Ошибка заборного столба (иногда её называют ошибкой телеграфного столба или фонарного столба) является частным случаем ошибки на единицу. Следующая задача иллюстрирует эту ошибку:

Если вы ставите прямой забор длиной тридцать метров и ставите столбы через три метра, то сколько столбов вам необходимо?

«Очевидный» на первый взгляд ответ — 10, ошибочен. Забор имеет 10 секций, но 11 столбов.

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

В более общем виде задача может быть сформулирована следующим образом: если есть n телеграфных столбов, сколько имеется промежутков между ними?

Корректный ответ может быть n-1, если линия столбов открыта с обеих концов; n если столбы образуют круг; n+1 — если свободные пространства с обеих концов считать промежутками. Точное определение проблемы должно быть тщательно изучено, поскольку верное решение в одной ситуации, может дать ошибочный результат в другой. Ошибка заборного столба возникает из-за того, что считаются столбы вместо промежутков между ними или наоборот, а также пренебрежения вопросом, нужно ли рассматривать один или два конца ряда.

Ошибка заборного столба может также проявить себя при счете других элементов, а не только длин. Примером может служить пирамида времени, которая должна состоять из 120 блоков, каждый из которых помещается на своё место с интервалом в 10 лет. Для её строительства с начала установки первого блока и до последнего блока требуется 1190 лет, а не 1200. Одним из самых ранних примеров ошибки заборного столба, касающихся времени, был Юлианский Календарь, где изначально неправильно рассчитывались високосные года, по причине расчета с включением, а не с исключением. Из-за этого в расчете високосный год повторялся через 3 года, а не через 4.

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

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

В качестве примера такой ошибки можно взять функцию linspace() из вычислительного языка Matlab, параметрами которой являются: наименьшая величина, наибольшая величина и количество величин, а не: наименьшая величина, наибольшая величина и количество шагов. Программист, который неправильно поймет, что из себя представляет третий параметр, будет считать, что linspace(0,10,5) сгенерирует последовательность [0,2,4,6,8,10], но вместо этого получит [0, 2.5,5, 7.5,10].

Проблемы безопасности

Обычная ошибка на единицу, которая приводит к проблеме безопасности — это некорректное использование функции strncat() из стандартной библиотеки C. Обычное недоразумение, связанное с strncat(), заключается в том, что null-байт не может быть записан дальше, чем длина строки. В действительности функция пишет null-байт за указанной длиной строки, если третий параметр равен или превышает эту длину. Следующий код содержит именно такую ошибку:

void foo (char *s) 
{
    char buf[15];
    memset(buf, 0, sizeof(buf));
    strncat(buf, s, sizeof(buf)); // последний параметр должен быть равен        
                                  //sizeof(buf)-1
}

Ошибка на единицу обычна при использовании стандартной библиотеки C, потому что в ней не реализован единый подход по поводу того, отнимать или нет 1: функции подобные fgets() и strncpy() никогда не выйдут за указанную им длину (fgets() сама отнимает 1 и извлекает (length-1) байтов), тогда как другие функции, подобные strncat(), осуществляют запись далее указанной для строки длины. По этой причине программист должен помнить для каких функций требуется отнимать 1.

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

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

См. также

1. Массив (программирование)
2. Си (язык программирования)
3. Ошибка (программирование)
4. Отладка программы
5. Стандартная библиотека языка Си
6. Список функций стандартной библиотеки Си
7. Переполнение стека

Ссылки

1. [code-live.ru/post/cpp-arrays/ Массивы в C++ ]
2. [dolphinsbay.narod.ru/Reefs.html#1 Ошибка заборных столбов]
3. [wiki.mvtom.ru/index.php/%D0%9E%D1%82%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D1%8B Ошибки программирования]
4. [shgpi.edu.ru/pirogov/cpp/ Заметки по языкам C и C++]

Отрывок, характеризующий Ошибка на единицу

В зале стояли гости, теснясь у входной двери, ожидая государя. Графиня поместилась в первых рядах этой толпы. Наташа слышала и чувствовала, что несколько голосов спросили про нее и смотрели на нее. Она поняла, что она понравилась тем, которые обратили на нее внимание, и это наблюдение несколько успокоило ее.
«Есть такие же, как и мы, есть и хуже нас» – подумала она.
Перонская называла графине самых значительных лиц, бывших на бале.
– Вот это голландский посланик, видите, седой, – говорила Перонская, указывая на старичка с серебряной сединой курчавых, обильных волос, окруженного дамами, которых он чему то заставлял смеяться.
– А вот она, царица Петербурга, графиня Безухая, – говорила она, указывая на входившую Элен.
– Как хороша! Не уступит Марье Антоновне; смотрите, как за ней увиваются и молодые и старые. И хороша, и умна… Говорят принц… без ума от нее. А вот эти две, хоть и нехороши, да еще больше окружены.
Она указала на проходивших через залу даму с очень некрасивой дочерью.
– Это миллионерка невеста, – сказала Перонская. – А вот и женихи.
– Это брат Безуховой – Анатоль Курагин, – сказала она, указывая на красавца кавалергарда, который прошел мимо их, с высоты поднятой головы через дам глядя куда то. – Как хорош! неправда ли? Говорят, женят его на этой богатой. .И ваш то соusin, Друбецкой, тоже очень увивается. Говорят, миллионы. – Как же, это сам французский посланник, – отвечала она о Коленкуре на вопрос графини, кто это. – Посмотрите, как царь какой нибудь. А всё таки милы, очень милы французы. Нет милей для общества. А вот и она! Нет, всё лучше всех наша Марья то Антоновна! И как просто одета. Прелесть! – А этот то, толстый, в очках, фармазон всемирный, – сказала Перонская, указывая на Безухова. – С женою то его рядом поставьте: то то шут гороховый!
Пьер шел, переваливаясь своим толстым телом, раздвигая толпу, кивая направо и налево так же небрежно и добродушно, как бы он шел по толпе базара. Он продвигался через толпу, очевидно отыскивая кого то.
Наташа с радостью смотрела на знакомое лицо Пьера, этого шута горохового, как называла его Перонская, и знала, что Пьер их, и в особенности ее, отыскивал в толпе. Пьер обещал ей быть на бале и представить ей кавалеров.
Но, не дойдя до них, Безухой остановился подле невысокого, очень красивого брюнета в белом мундире, который, стоя у окна, разговаривал с каким то высоким мужчиной в звездах и ленте. Наташа тотчас же узнала невысокого молодого человека в белом мундире: это был Болконский, который показался ей очень помолодевшим, повеселевшим и похорошевшим.
– Вот еще знакомый, Болконский, видите, мама? – сказала Наташа, указывая на князя Андрея. – Помните, он у нас ночевал в Отрадном.
– А, вы его знаете? – сказала Перонская. – Терпеть не могу. Il fait a present la pluie et le beau temps. [От него теперь зависит дождливая или хорошая погода. (Франц. пословица, имеющая значение, что он имеет успех.)] И гордость такая, что границ нет! По папеньке пошел. И связался с Сперанским, какие то проекты пишут. Смотрите, как с дамами обращается! Она с ним говорит, а он отвернулся, – сказала она, указывая на него. – Я бы его отделала, если бы он со мной так поступил, как с этими дамами.


Вдруг всё зашевелилось, толпа заговорила, подвинулась, опять раздвинулась, и между двух расступившихся рядов, при звуках заигравшей музыки, вошел государь. За ним шли хозяин и хозяйка. Государь шел быстро, кланяясь направо и налево, как бы стараясь скорее избавиться от этой первой минуты встречи. Музыканты играли Польской, известный тогда по словам, сочиненным на него. Слова эти начинались: «Александр, Елизавета, восхищаете вы нас…» Государь прошел в гостиную, толпа хлынула к дверям; несколько лиц с изменившимися выражениями поспешно прошли туда и назад. Толпа опять отхлынула от дверей гостиной, в которой показался государь, разговаривая с хозяйкой. Какой то молодой человек с растерянным видом наступал на дам, прося их посторониться. Некоторые дамы с лицами, выражавшими совершенную забывчивость всех условий света, портя свои туалеты, теснились вперед. Мужчины стали подходить к дамам и строиться в пары Польского.
Всё расступилось, и государь, улыбаясь и не в такт ведя за руку хозяйку дома, вышел из дверей гостиной. За ним шли хозяин с М. А. Нарышкиной, потом посланники, министры, разные генералы, которых не умолкая называла Перонская. Больше половины дам имели кавалеров и шли или приготовлялись итти в Польской. Наташа чувствовала, что она оставалась с матерью и Соней в числе меньшей части дам, оттесненных к стене и не взятых в Польской. Она стояла, опустив свои тоненькие руки, и с мерно поднимающейся, чуть определенной грудью, сдерживая дыхание, блестящими, испуганными глазами глядела перед собой, с выражением готовности на величайшую радость и на величайшее горе. Ее не занимали ни государь, ни все важные лица, на которых указывала Перонская – у ней была одна мысль: «неужели так никто не подойдет ко мне, неужели я не буду танцовать между первыми, неужели меня не заметят все эти мужчины, которые теперь, кажется, и не видят меня, а ежели смотрят на меня, то смотрят с таким выражением, как будто говорят: А! это не она, так и нечего смотреть. Нет, это не может быть!» – думала она. – «Они должны же знать, как мне хочется танцовать, как я отлично танцую, и как им весело будет танцовать со мною».
Звуки Польского, продолжавшегося довольно долго, уже начинали звучать грустно, – воспоминанием в ушах Наташи. Ей хотелось плакать. Перонская отошла от них. Граф был на другом конце залы, графиня, Соня и она стояли одни как в лесу в этой чуждой толпе, никому неинтересные и ненужные. Князь Андрей прошел с какой то дамой мимо них, очевидно их не узнавая. Красавец Анатоль, улыбаясь, что то говорил даме, которую он вел, и взглянул на лицо Наташе тем взглядом, каким глядят на стены. Борис два раза прошел мимо них и всякий раз отворачивался. Берг с женою, не танцовавшие, подошли к ним.
Наташе показалось оскорбительно это семейное сближение здесь, на бале, как будто не было другого места для семейных разговоров, кроме как на бале. Она не слушала и не смотрела на Веру, что то говорившую ей про свое зеленое платье.
Наконец государь остановился подле своей последней дамы (он танцовал с тремя), музыка замолкла; озабоченный адъютант набежал на Ростовых, прося их еще куда то посторониться, хотя они стояли у стены, и с хор раздались отчетливые, осторожные и увлекательно мерные звуки вальса. Государь с улыбкой взглянул на залу. Прошла минута – никто еще не начинал. Адъютант распорядитель подошел к графине Безуховой и пригласил ее. Она улыбаясь подняла руку и положила ее, не глядя на него, на плечо адъютанта. Адъютант распорядитель, мастер своего дела, уверенно, неторопливо и мерно, крепко обняв свою даму, пустился с ней сначала глиссадом, по краю круга, на углу залы подхватил ее левую руку, повернул ее, и из за всё убыстряющихся звуков музыки слышны были только мерные щелчки шпор быстрых и ловких ног адъютанта, и через каждые три такта на повороте как бы вспыхивало развеваясь бархатное платье его дамы. Наташа смотрела на них и готова была плакать, что это не она танцует этот первый тур вальса.
Князь Андрей в своем полковничьем, белом (по кавалерии) мундире, в чулках и башмаках, оживленный и веселый, стоял в первых рядах круга, недалеко от Ростовых. Барон Фиргоф говорил с ним о завтрашнем, предполагаемом первом заседании государственного совета. Князь Андрей, как человек близкий Сперанскому и участвующий в работах законодательной комиссии, мог дать верные сведения о заседании завтрашнего дня, о котором ходили различные толки. Но он не слушал того, что ему говорил Фиргоф, и глядел то на государя, то на сбиравшихся танцовать кавалеров, не решавшихся вступить в круг.
Князь Андрей наблюдал этих робевших при государе кавалеров и дам, замиравших от желания быть приглашенными.
Пьер подошел к князю Андрею и схватил его за руку.
– Вы всегда танцуете. Тут есть моя protegee [любимица], Ростова молодая, пригласите ее, – сказал он.