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

Три момента, которые видимо не давали мне ключ к пониманию:

1) Сдвиг это действительно сдвиг, а не умножение/деление на два!
2) В школьном варианте мы сдвигаем сразу всю цифру (десятичную) целиком, а тут мы это делаем по одному биту (грубо говоря, тупо ждём, когда протащится вся цифра);
3) Пожалуй, принципиальный момент, который скрывал логику: поскольку мы работаем в двоичной с/с, то на каждой итерации нам не нужно делать реальное деление цифры на делитель, как это делается в школьном столбике, а достаточно лишь понять делится оно или нет, точнее - результат ноль или больше, и так как за одну двоичную итерацию у нас не может ничего произойти с результатом больше, чем на единицу, то достаточно либо оставлять "халявный" автоматический "0" или добавлять "1".

Я бы до такого не додумался сам! Я бы стал подгонять алгоритм под известный школьный столбик, т.е. сдвигать байт сразу на тетраду и честно делить вычитаниями. Тут какой-то двоичный переворот сознания %)

Всем спасибо! Теперь можно спать спокойно