(Я дурак)
Начальник говорит: хочешь заняться настоящим программированием?
В общем, выяснилось, что нужно написать алгоритм, который бы делил одно целое число на другое, но можно использовать только сложение, вычитание и битовый сдвиг.
Хмыкнув, я взял листочек и глубокомысленно вывел на нём:
A
_
B
рядом я написал ":3" (это было "делить на три") и "11" (это было три в двоичной системе счисления). Это ни к чему не привело.
Тогда я подумал, может быть можно поделить сначала на два, а потом на один? И написал
A
______
B1+B2
Это тоже помогло слабо. Тогда я решил поделить столбиком "11001011" на "11". Изображать то, что у меня вышло, я не буду, но ответ получился правильный. Однако как сделать это, я недоумевал. Я знал, что при делении столбиком реально происходит сдвиг и вычитание, однако 11 надо было сдвинуть на 6... как определить, на сколько сдвинуть, я не знал.
Полез в интернет. Там статья.
en.wikipedia.org/wiki/Division_algorithm (EN)
В статье было всё написано, но я этого не понял... и тут до меня дошло, что лучше сдвигать не делитель, а делимое. А делимое всё равно должно пробегаться по всем разрядам, так что будем пробегать по очереди. В итоге я написал учебную программу, которая показывает как это работает "изнутри" (в итоге понадобились только несколько строк основного алгоритма). Потом до меня дошло, что то, что я написал (алгоритм "столбиком") очень похож на то, что в статье (под подзаголовком Integer division (unsigned) with remainder ), только остаток не выводится (а остаётся на последнем шаге в переменной).
Вот исходник: pastebin.com/aPNXDMF1
@темы:
Программирование,
Говнокод
17.01.2013 в 22:22
я тоже, но это нормально