Чем вы тут занимаетесь или как поделить число на два

Подходили к вам когда-нибудь ваши знакомые или друзья с вопросом: “А чем вы, программисты, вообще занимаетесь, кроме того, что просто тычете по клавишам?”. Наверное, людей и правда интересует, зачем платят деньги за набор (к тому же медленный) текста на клавиатуре, даже если эти люди целый день таскают с собой мобильный телефон¹.

Но вопрос есть вопрос. И если попытаться ответить без шутки, что же мы на самом деле делаем (кроме того, что спим и едим). Да, можно попробовать. Ну, думаю, что тем же, чем занимаются и другие инженеры. Пытаемся заставить ресурсы (в нашем случае это вычислительные машины) работать на человека и приносить какую-то пользу (считается ли пользой для человечества перекладывание JSON из одного места в другой?).

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

— Расскажи, как работает нейросеть? Или не, как работает блокчейн?

— Ну, я могу рассказать, как работает блокчейн, но во-первых, это потребует объяснений математической логики, дискретной математики и много каких ещё наук. Об этой вещи не получится рассказать просто потому что это вещь сложная. И тут я не соглашусь с высказываниями людей о том что если ты не можешь объяснить ребёнку ты это не понимаешь. Может быть любопытству ребёнка и будет достаточно знаний о том, что та летящая вверх палка это ракета, а летает она потому что у неё есть двигатель, но это нисколько не приблизит ребёнка ни к постройке ракеты-носителя, ни к постройке ракетного двигателя. Во-вторых, программирование это абстракции, не так просто объяснить с приведением корректной аналогии, что такое, например, хеширование. В-третьих, я не работаю ни над нейросетями, ни над блокчейнами. Не работаю в смысле не работаю профессионально. Например, у меня нет своей криптовалюты, что к счастью. Поэтому тонкостей я не знаю. Я работаю над сетевыми сервисами, можешь спросить что-нибудь об этом.

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

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

И этот вопрос - “как поделить число на 2?”. Это отличный вопрос, если вы думаете что это слишком сложно, я попробую убедить вас в том, что чтобы научить ЭВМ делить на два нужно совсем немного знаний, знать как представлены числа и самую простую математику. Если же наоборот, вы думаете что это слишком легко, поверьте, и вас есть чем удивить. А задача совершенно реальная, так как вы согласитесь что людям нужно делить числа и, некоторые компьютеры (точнее сказать микропроцессоры, небольшие устройства внутри компьютера) не умеет делить числа и их нужно учить. Кроме этого, можно показать процесс исследования проблемы и то как мы подходим к её решению.

Ещё вопрос интересен тем, что большинство программистов у которых я так же интересовался этим самым, ответили на этот вопрос не правильно (ниже вопрос будет приведён полностью, если вы хотите попробовать ответить до моего разбора). Сначала я хотел назвать статью - “НА ЭТОТ ВОПРОС 100 ПРОГРАММИСТОВ ИЗ 100 ОТВЕТИЛИ НЕ ПРАВИЛЬНО.”, но потом счёл, что это какой-то слишком кликбейтный заголовок. Безусловно задача проста, и неправильные ответы были даны, скорее, из-за скорости и нехватки времени для обдумывания. В конце концов любой программист получит решение примерно тем же способом, что я опишу в статье.

Что нужно знать

Статью можно читать если вы не занимаетесь программированием профессионально. Я постараюсь сделать так, чтобы читателю можно было пропустить тот или иной участок статьи который связан с программированием напрямую (например какой-то кусок программного кода) и не упустить основную идею. Если вы не программируете, раздел Сдвинуть на 1 бит вправо может быть вам непонятен, он является настоящим введением и, скорее, несёт художественную цель (хотя и содержит программный код). Начиная с раздела Как устроены числа в компьютере нужно читать внимательно. Раздел Extra тоже можно пропустить, там показаны некоторые особенности для языка Go.

Математика не превышает 6 класса, и то, только за счёт упоминания отрицательных чисел, да я погуглил когда проходят отрицательные числа, в остальном мы не будем затрагивать понятия выше 2 класса. Умение складывать числа столбиком сделает чтение и понимание статьи простым.

Когда я говорю о делении, я всегда подразумеваю целочисленное деление, операция в результате которой получается целая часть частного без остатка. То есть корректным результатом деления 6 на 2 и 7 на 2 будет число 3, а корректным результатом деления -6 на 2 и -7 на 2 будет -3.

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

В записях часто будет встречаться ведущие нули у чисел, например число 12 в десятичной СС может быть записано с помощью 4 знаков - 0012. А число 7 в двоичной СС может быть записано с помощью 8 знаков так - 00000111. Ведущие нули не влияют на значение числа, их можно отбросить, но для наглядности иногда они будут присутствовать (например при сложении столбиком, когда удобно что соответствующие друг другу разряды обоих чисел стоят на одной вертикали, даже если сами числа отличаются на порядки).

   // Можно так
   + 1
     123
     124

   // Но такая запись удобнее
   + 0001
     0123
     0124

Слово бит в статье имеет значения слова разряд (когда вы видите слово бит, можете читать разряд, но не наоборот!). Значение слова регистр не совпадает со значением этого слова в схемотехнике. В статье это просто набор бит.

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

Статья всё ещё на этапе сбора фитбека и проверки орфографии. Я всё ещё ей не доволен. Вероятно, в ней что-то будет изменено. Если у вас есть предложения, забегайте.

Сдвинуть на 1 бит вправо

Но вернёмся к задаче. Разные люди с разной подготовкой могут задать разные уточняющие вопросы. Меня не проведёшь - заговорит программист уже не раз, попадавший на уловки, не уточнения задачи. Какое именно число нужно поделить? Ладно, я это и хотел сказать. Мы будем делить целые, знаковые числа представленные в дополнительном коде. Это ровно такое представление что используется современными вычислительными машинами, например вашим компьютером или телефоном с которого вы читаете эту статью. Разрядность (то есть число порядков) числа возьмём небольшую, например 8 разрядов, для сути разницы нет, но манипулировать числами вида - 10010011 намного приятнее глазу чем - 10101010101010101010101011001100010100000011110000101110000111.

Если попытаться задать вопрос программисту, самый классический ответ который я получаю, это:

- Сдвинуть на 1 бит вправо.

Сдвинуть на 1 бит вправо? Что это вообще значит? Убрать один разряд. Самый правый. На самом деле, тут не нужно иметь инженерное образование, чтобы понять что удаление самого правого разряда приводит к делению числа на показатель основания СС, достаточно лишь немного проницательности. Вы можете попробовать провести эту операцию на любом десятичном числе по вашему выбору. Но если не поняли сходу то пока просто идём дальше.

По идее это должно работать, поэтому мы можем просто попробовать запрограммировать.

Существует ровно один способ сдвига вправо и выражающий его оператор воскликнет программист на Go. Существует не одна функция сдвига, можно сдвигать через флаг переноса, есть логический и арифметический сдвиг и циклический сдвиг скажет ему в ответ программист на языке ассемблера.

Ну, раз мы хотим научить компьютер нам нужен какой-то способ выражения наших мыслей понятный, в том числе и компьютеру. Язык Go для этого подходит чуть лучше, чем ассемблер, потому что похож на псевдокод. Давайте поищем в документации что-то на счёт сдвигов.

The shift operators shift the left operand by the shift count specified by the right operand, which must be non-negative. If the shift count is negative at run time, a run-time panic occurs. The shift operators implement arithmetic shifts if the left operand is a signed integer and logical shifts if it is an unsigned integer. There is no upper limit on the shift count. Shifts behave as if the left operand is shifted n times by 1 for a shift count of n. As a result, x « 1 is the same as x*2 and x » 1 is the same as x/2 but truncated towards negative infinity.

Как видим да, оператор сдвига есть. Он сдвигает левый операнд на величину указанную правым операндом. Ещё нам указывают что величина сдвига не может быть отрицательной. И то, что есть разница в механизме сдвига в зависимости от того знаковый левый операнд или нет.

Ну раз существует только один оператор, выбора у нас нет. И выглядеть это будет вот так:

func fakediv(a int8) int8 {
	return a >> 1
}

// fakediv(6) ; 3
// fakediv(7) ; 3

Работает? На сколько вы уверены по шкале от одного до сорока двух? Да, так как деление целочисленное, правильный ответ 3 в обоих случаях, но попробуйте поделить число -1 и вы поймёте, ЧТО ЧТО_ТО РАБОТАЕТ НЕ ТАК. Как программисты вообще понимают что что-то работает не корректно? Ну, можно отдать этот код в релиз. В продакшн. Пользователи придут минут через 5. А ещё? Тестирование. Тестированием мы можем попытаться выявить самые явные ошибки и в конце концов снизить их стоимость (да, их не придётся отлавливать вам, пользователями. Но не беспокойтесь, вам мы тоже что-нибудь оставим). Штош. Давайте напишем тест. Например, при работе с числами можно проверять разные виды чисел. Отрицательные, положительные, четные и нечетные. Чем больше разных тестовых данных мы придумаем, тем больше будет наша уверенность в работоспособности решения. Интересно что входные данные к выбранной нами задачи (а именно деление восьмиразрядных целых знаковых чисел, int8 в Go) вообще, множество конечное. Но чтобы определить его, нужно знать представление, поэтому пока, давайте попробуем поделить числа, допустим, от -5 до 5.

Итак - тест:

package main

import (
	"testing"
)

func truediv(i int8) int8 {
	return i / 2
}

func fakediv(a int8) int8 {
	return a >> 1
}

func TestDiv(t *testing.T) {

	const x int8 = -5
	const y int8 = 5

	i := x
	for {
		got := fakediv(i)
		want := truediv(i)

		if got != want {
			t.Errorf("incorreсt result of division %d, want %d, got %d", i, want, got)
		}

		if i == y {
			break
		}

		i++
	}
}

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

--- FAIL: TestDiv (0.00s)
    main_test.go:26: incorreсt result of division -9, want -4, got -5
    main_test.go:26: incorreсt result of division -7, want -3, got -4
    main_test.go:26: incorreсt result of division -5, want -2, got -3
    main_test.go:26: incorreсt result of division -3, want -1, got -2
    main_test.go:26: incorreсt result of division -1, want 0, got -1
FAIL
exit status 1
FAIL    einbuch 0.244s

Ошибка деления происходит при всех нечётных отрицательных числах. Либо оператор >> не сдвиг, либо сдвигом нельзя делить. Но если вы сами попробуете провести эксперимент и поспрашивать программистов, вы с очень высокой вероятностью получите именно такой ответ - “сдвинуть на один разряд вправо”. Иногда это будет звучать как заклинание, и как мы все знаем, чтобы оно нормально сработало необходимо ко всему прочему взмахнуть волшебной палочкой нарисовав в воздухе схему сдвигового регистра.

Проблему можно решить вообще не вникая в представления чисел. Что бы вы например сделали не знай вы про дополнительный код и про механизм работы сдвигов?

Так, давайте подумаем, если результат отличается на 1 в меньшую сторону и только для отрицательных нечётных чисел, то можно добавить 1 к результату если делимое число отрицательное и нечётное. Л-ЛОГИКА. “Улучшаем”:

func isBadNumber(a int8) bool {
	return (a < 0) && (a % 2 != 0)
}

func fakedivImproved(a int8) int8 {
	if isBadNumber(a) {
		return (a >> 1) + 1
	}

	return a >> 1
}

B запуск тестов говорит нам что сейчас всё отлично:

PASS
ok      einbuch 0.244s

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

И такое решение вполне можно увидеть в продакш коде. Не с делением конечно, а в том моменте, что вообще мы до конца не разобрались, но вроде работает. Если вы сейчас улыбаетесь, напомню, во-первых, как я сказал, оно работает, во-вторых есть набор тестов. Кому как ни вам знать что в прод может поехать фича которая не может похвастаться ни первым ни вторым ¯\_(ツ)_/¯.

Проблемы начинаются тогда, когда цена ошибки становится велика. Например, когда от программы зависят деньги либо даже жизнь человека³. Поэтому такое решение нам не подходит. Тут есть куда копать дальше.

Заключеие

Если бы мы, программисты, всегда тщательно читали документацию, то находили бы решение намного быстрее. В документации ясно сказано, что деление происходит с округлением в сторону отрицательной бесконечности — truncated towards negative infinity. Классическая же операция деления в математике должна работать как truncated towards zero или округление в сторону 0.

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

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

Как устроены числа в компьютере.

Что такое операция сдвига? Почему она работает, или по крайней мере пытается казаться работающей?

Тему устройства чисел можно разделить на несколько подтем. Я бы реально хотел рассказать, а может даже показать как смастерить штуковину, которая может считать числа не хуже вашего айфона (если рассматривать только корректность вычисления, а не скорость), благо какие-нибудь К155ЛА3 (или даже КТ315) найти не составляет труда. Но видя как разрастается объем я решил вытащить это в отдельную статью. Тут сосредоточимся только на минимально необходимых знаниях чтобы хватило на деление.

Когда мы говорим о том что компьютер умеет считать (проводить операции над числами) мы должны понимать что он должен и хранить эти числа, как они хранятся?

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

    // Коробка с яблоком
    +---+
    | @ |
    +---+

    // Коробка с двумя яблоками
    +-----+
    | @ @ |
    +-----+

    // Коробка с четырмя яблоками
    +---------+
    | @ @ @ @ |
    +---------+

    // Коробка вообще без яблок
    +---+
    |   |
    +---+

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

    // Коробка с четырьмя яблоками во втором
    // разряде и двумя яблоками в первом.
    // Какое это число? Правильно, 42.
    +---------+-----+
    | @ @ @ @ | @ @ |
    +---------+-----+

Хотя и десятичная СС нам, как людям понятна, но кодировать такое представление в реальном устройстве тяжело, и это работает не только на таком бутафорском примере как коробки с яблоками. В реальном электронном устройстве, например оперативной памяти, число кодируется не кол-вом яблок, а уровнем напряжения, и достаточно тяжело физически построить устройство которое бы отличало более чем 2 уровня из-за погрешности как измерений, так и отклонения в параметрах самих устройств хранения, достаточно хорошо можно отличать два уровня — напряжение около 0 и напряжение отличное от нуля (в схемотехнике обычно используются 5V или 3.3V, но могут быть и другие). Если это не совсем понятно, просто поймите что больше одного яблока в коробку класть не выходит.

Из этого следует что необходимо использовать СС с максимально небольшим значением основания (чем меньше основание, тем меньше проблем с реализацией). Двоичная СС подходит лучше всего. Два возможных значения (вместо 10). Легко построить реальное устройство. Так, если мы договоримся что в коробке может либо отсутствовать яблоко, либо присутствовать, но только одно, как представлять числа больше чем единица? Точно так же, как в десятичной СС — путём увеличения разрядов числа. С десятичными числами один разряд позволяет вам представить числа от 0 до 9, а два разряда дадут возможность представить от 0 до 99. В двоичной СС, один разряд позволяет нам представить только два числа, 0 и 1. Два разряда дадут возможность представить 4 числа, от 0 до 3, вот так:

   // Два разряда, в каждом может присутствовать только 0 или 1
   // дают в общей сложности 4 возможных комбинации

   // Двоичное число   Десятичное
   00                  0
   01                  1
   10                  2
   11                  3

Насколько много чисел можно представить имея 8 разрядов, 16, 32? Посчитаете? Для удобства мы отойдём от примера с яблоками и будем говорить что можем положить я коробку либо цифру 0 (яблок нет), либо цифру 1 (яблоко есть).

Ещё нужно знать что, в вычислительной машине каждое число хранятся в фиксированном кол-ве коробок. Так удобно, больше ничего не скажу. То есть в 8 разрядной вычислительной машине даже число 1 будет занимать 8 разрядов⁴:

    // Мы ещё поговорим с какой стороны начинать записывать число
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
    +---+---+---+---+---+---+---+---+

Назовём такой набор коробок — регистром, конкретно этот — восьмиразрядный регистр. В каждый разряд регистра мы можем положить либо 0, либо 1. Как представить число 0 в таком представлении? Очевидно что все разряды должны быть заполнены нулями. А число 255?

    // Число 0, во все разряды помещены нули.
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
    +---+---+---+---+---+---+---+---+

    // Десятичное число 255, восемь единиц в двоичном представлении.
    +---+---+---+---+---+---+---+---+
    | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
    +---+---+---+---+---+---+---+---+

Остаётся вопрос в какой последовательности записывать число, например число 11 — 1011, можно разместить двумя разными способами (вы можете попробовать придумать свои):

    // Можно записывать самый старший разряд в самой левой ячейке, а остальные разряды сразу после.
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
    +---+---+---+---+---+---+---+---+

    // Можно записывать самый младший разряд в самой правой ячейке, а остальные разряди сразу после.
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
    +---+---+---+---+---+---+---+---+

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

Вот посмотрите на это:

    0012
   +
    0341
   =
    0353

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

Чтобы однозначно идентифицировать отдельные разряды в регистре мы их пронумеруем. Раз записываем число мы с самой левой ячейки она и будет под номером 0.

    // Пронумерованные коробки справа на лево.

      7   6   5   4   3   2   1   0
    +---+---+---+---+---+---+---+---+    
    |   |   |   |   |   |   |   |   |    
    +---+---+---+---+---+---+---+---+

Коробку с номером 0 будем называть младшим разрядом, коробку номер 7 назовём старшим разрядом.

Что насчёт сложения таких чисел? Как сложить 25 и 11? Давайте допустим что у нас есть устройство, которое называется сложитель, считатель или сумматор. Его устройство сейчас нам не важно, главное понять что он умеет складывать числа столбиком.

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

Сложение 25 и 11:

    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |   // 25
    +---+---+---+---+---+---+---+---+
PLUS
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |   // 11
    +---+---+---+---+---+---+---+---+
EQUL
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |   // 36
    +---+---+---+---+---+---+---+---+

Единственное отличие от начальной школы в том, что в школе у нас были дохрена большие тетрадки и вы могли всегда найти место, чтобы разместить разряд N если он получался больше чем у любого из слагаемых. Компьютер же имеет ограниченные блоки хранения и обработки информации и, как пример, наша вычислительная машина не может представить число превышающее 255. Разрядов для хранения одного числа только 8.

Так, если максимальное число представимое к нашей ЭВМ это 255, что будет если сложить два числа которые меньше или равны 255, но их сумма чисел больше чем 255? Что мы получим? Ну давайте попробуем сложить 127 (0111 1111) и 171 (1010 1011), если мой калькулятор не врёт должны получить 298. НО.

    +---+---+---+---+---+---+---+---+
    | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |   // 127
    +---+---+---+---+---+---+---+---+
PLUS
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |   // 171
    +---+---+---+---+---+---+---+---+
EQUL
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |   // 42?
    +---+---+---+---+---+---+---+---+

Пруф. Да, происходит перенос из разряда под индексом 7, но переносить некуда и компьютер его просто отбрасывает (так как негде хранить)⁵. И ответ мы получаем по модулю 256. Остаток от деления 298 на 255 как раз и будет 42.

Хорошая математика да? Это недостаток называется целочисленным переполнением, но рассматривать сейчас мы его не будем⁶. Можно сказать что возможность представить в компьютере большие числа есть, но для этого нужно использовать больше ячеек памяти, и, как вы понимаете, программа сложения будет сложнее.

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

Отрицательные числа

Отрицательные числа проходят в начальной школе, но что такое отрицательные числа в представлении компьютера?

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

Вариантов на самом деле не много. Думаю очевидно что знак мы можем закодировать используя какой-либо бит в нашем регистре. Больше одного не нужно, ведь нужно хранить только два состояния — отрицательное число или нет. Да, просто договоримся, что в бите номер N лежит не показатель разряда числа, а указание, отрицательное число или нет.

Какой бит для этого использовать? Если мы вспомним что складываем числа мы столбиком, было бы неудобно имею бит отвечающий за знак где-то посередине. Так же исходя из того что мы можем получить перенос от 0-го разряда в 1-й при сложении двух отрицательных чисел, то и 0 бит использовать тоже неудобно.

Получается, единственный вариант остаётся крайний правый, 7 бит. Посмотрим на два числа:

    // Положительное число 5
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
    +---+---+---+---+---+---+---+---+

    // Отрицательно число 5
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
    +---+---+---+---+---+---+---+---+

У такого представления есть занятные артефакты. При попытке сложить число 1111111 (127) и 1 (1) мы получим перенос в 7 разряд, а раз мы договорились что 7 разряд отвечает за знак то согласно нашему представлению мы получили число -0.

    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | // Это число 1
  + +---+---+---+---+---+---+---+---+
    | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | // Это число 127
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | // Это число -0?
    +---+---+---+---+---+---+---+---+

Вспомним границы беззнакового чиcла, от 0 до 255. Так как для хранения знака мы выделили один разряд, то границы будут сдвинуты. Мы уже не можем представить число 128. Посмотрим на крайние значения:

    // Положительное число 127
    +---+---+---+---+---+---+---+---+
    | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
    +---+---+---+---+---+---+---+---+

    // Ноль
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
    +---+---+---+---+---+---+---+---+

    // Минус ноль
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
    +---+---+---+---+---+---+---+---+

    // Минус 127
    +---+---+---+---+---+---+---+---+
    | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
    +---+---+---+---+---+---+---+---+  

Как вы можете догадаться отрицательных чисел столько же сколько и положительных, значит положительных от 1 до 127, отрицательных от -1 до -127.

Если -5 это 129, то получается 129 вообще нельзя представить с помощью 8-битного знакового числа. Как насчёт математики? Попробуем складывать числа нашим сумматором:

    // Пример 1. -1 + -2 = -3
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | // Это число -1
  + +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | // Это число -2
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | // Это число 3 (лол что?)
    +---+---+---+---+---+---+---+---+

    // Пример 2. -1 + 2 = 1
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | // Это число -1
  + +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | // Это число 2
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | // Это число -3 (лол что?)
    +---+---+---+---+---+---+---+---+

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

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

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

Как изобрести дополнительный код с нуля?

Наверное обьяснение о том как работает дополнительного кода и зачем он нужен можно с помощью интернет статей. Там такого добра навалом. Если вы понимаете что Дополнительный код для отрицательного числа можно получить инвертированием его двоичного модуля и прибавлением к инверсии единицы возможно этот раздел можно пропустить. Если просто рассказать про то как получить дополнительный код отрицательного числа у незнакомого с темой человека всегда возникает вопросы. А как это поняли? Как до этого додумались?

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

Как мы помним самая главная проблема прошлого представления это то что наш сумматор не работает. Но что если изменить нашу логику, не искать представление которое даёт удовлетворительное результат сложения, а подойти с другой стороны. У нас есть ограниченное число последовательностей доступных для представления отрицательных чисел. Мы можем брать каждую такую последовательность бит, складывать её на сумматоре (например с единицей) и смотреть для какой последовательности мы получим 0. Эта последовательность и будет минус единицей.

Тут предлагаю уменьшить разрядность нашего регистра до 4, чтобы возможных комбинаций стало только 16, потому что желательно обхватить их взглядом все, что для восьмиразрядного регистра с 256 комбинациями достаточно сложно.

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

0000   0
0001   1
0010   2
0011   3
0100   4
0101   5
0110   6
0111   7
1000   8
1001   9
1010   10
1011   11
1100   12
1101   13
1110   14
1111   15
0000   0   // ПЕРЕПОЛНЕНИЕ, РАЗРЯД 5 ПОТЕРЯН
0001   1
...

Мы видим что последовательность зацикливается. При прибавлении единицы к самому наибольшему числу мы получаем самое минимальное число.

Возвращаемся к отрицательным. Идея что старший разряд будет указывать на знак жизнеспособна, так как позволяет легко отличить отрицательные числа от неотрицательных. Поэтому, если мы далее не споткнёмся о какую-либо проблему, связанную с тем, что отрицательные числа всегда содержат единицу в старшем разряде, будем считать это главной идеей и не будем рассматривать другие. Сколько отрицательных чисел мы можем сохранить? Если всего для четырёх разрядов у нас 16 вариантов, один - ноль и 7 положительных остаётся 8 слотов для отрицательных, вот они:

1000
1001
1010
1011
1100
1101
1110
1111

Так же хотелось бы хранить числа наиболее близкие к нулю. То есть начиная с -1 и меньшие. Раз вариантов 8 то числа которые мы можем сохранить подпадают под диапазон от -1 до -8.

Как помним из математики в при сложении -1 и 1 хотелось бы получить 0. Возвращаемся к нашему сумматору и посмотрим какая последовательность из вышеперечисленного при сложении с единицей даст 0. Я прибавил единицу ко всем вариантам за вас:

1000 + 1 = 1001
1001 + 1 = 1010
1010 + 1 = 1011
1011 + 1 = 1100
1100 + 1 = 1101
1101 + 1 = 1110
1110 + 1 = 1111
1111 + 1 = 0000  // Произошло переполнение, но кому какое дело. 
                 // Результат 0.

Да, последовательность 1111 при сложении на сумматоре с последовательностью 0001 даёт результат 0000. Значит мы можем сказать что 1111 это и есть представление минус единицы. Если вы попробуете придумать представление числа -2 используя эту же простую логику у вас получился 1110, попробуйте придумать как выглядит -3, -4, -5, -6, -7, -8. Так как есть только 8 слотов, мы можем представить числа от -1 до -8. Я думаю стоит остановиться и попробовать посчитать самостоятельно, но если вы сделали вот полная таблица:

0000 // 0
0001 // 1
0010 // 2
0011 // 3
0100 // 4
0101 // 5
0110 // 6
0111 // 7
1000 // -8
1001 // -7
1010 // -6
1011 // -5
1100 // -4
1101 // -3
1110 // -2
1111 // -1

Мы получаем такое же циклическое представление. Прибавление единицы к максимальному положительному числу даёт самое большое отрицательное число. Перед тем как мы попробуем математику (по правде сказать нам не нужно проверять как работает сумматор на этом представлении потому что мы вывели представление на основе результатов сумматора) можно поговорить о недостатках.

Самый очевидный это не читаемость, единственное что можно сказать быстро это то что число отрицательное, потому что старший разряд выставлен в 1 - 1100. Но что это за число по модулю? Пока мы можем только посмотреть в таблицу, таблица говорит что это -4. Есть несколько способов как быстро понять что 1110 это -2, но вы правда хотите это знать⁸?

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

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

Небольшое отступление, в независимости от представления знаковых чисел мы не можем сказать знаковое ли число или нет. Посмотрите на число 1111. Это может быть как число 15, так и число -1. Мы должны заранее знать как мы работаем с числами, либо как с числами со знаком, либо как с беззнаковыми.

Операции сдвига

Осталось разобраться со сдвигом.

Сначала разберёмся с беззнаковыми числами. Представим число 187 в двоичной системе счисления, это будет 10111011:

     7                           0
   +---+---+---+---+---+---+---+---+
   | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
   +---+---+---+---+---+---+---+---+

Определим сдвиг вправо как операцию где мы в каждый N-ый разряд начиная с 0 помещаем значение лежащее сейчас в разряде N+1. За исключением разряда номер 7, восьмого по счёту, так как у нас нет девятого разряда и значению попросту неоткуда взяться. Поэтому в разряде номер 7 будет значение 0.

// Unsigned shift right

   +---+---+---+---+---+---+---+---+
   | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
   +---+---+---+---+---+---+---+---+
 0 -->--->--->--->--->--->--->--->
   +---+---+---+---+---+---+---+---+    
   | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |    
   +---+---+---+---+---+---+---+---+

По аналогии, сдвиг в право определим как операцию где мы в каждый N-ый разряд начиная с 7 помещаем значение лежащее сейчас в разряде N-1. За исключением разряда номер 0, первого по счёту, так как у нас нет минус первого разряда и значению также взяться неоткуда. Поэтому в разряде номер 0 будет значение 0.

// Unsigned shift left
   +---+---+---+---+---+---+---+---+
   | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
   +---+---+---+---+---+---+---+---+
     <---<---<---<---<---<---<---<-- 0
   +---+---+---+---+---+---+---+---+    
   | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |    
   +---+---+---+---+---+---+---+---+

Может ли быть эта операция полезна для работы с числами? Как она влияет на значение числа?

Если вы ещё не догадались, то попробуйте провернуть эту операцию с числами в десятичной системе счисления. Например, с числом 123 сдвиг в право: 0123 -> 0012, 0012 -> 0001, 0012 -> 0001. Ведущие нули не влияют на значения, но я привел их для наглядности. Думаю тут не нужно много думать, чтобы понять, что сдвиг вправо делит число на 10.

Если провести аналогию, то сдвиг в двоичной системе счисления приводит к умножению на два и делению соответственно.

До каких пор можно сдвигать? Попробуем с делением максимально представимого числа для 8 бит.

// Двоичное       Десятичное
   1111 1111   |  255
   0111 1111   |  127
   0011 1111   |  63
   0001 1111   |  31
   0000 1111   |  15
   0000 0111   |  7
   0000 0011   |  3
   0000 0001   |  1
   0000 0000   |  0

Сдвиг преставления числа 0 всегда будет 0. Что выглядит корректно так как и математики ожидают получить 0 при делении 0 на 2, давайте теперь попробуем со сдвигом влево.

// Двоичное       Десятичное
   0000 0001   |  1
   0000 0010   |  2
   0000 0100   |  4
   0000 1000   |  8
   0001 0000   |  16
   0010 0000   |  32
   0100 0000   |  64
   1000 0000   |  128
   0000 0000   |  0     WAT?

Всё за исключением последней операции выглядит подозрительно похожее на умножение. Вот только математики негодуют, очевидно, они хотели бы получить число 256, но мы, как программисты нашего 8-битного компьютера говорим что ответ 0. Тут интуитивно понятно, что имея 1 в самом правом разряде, при ещё одном сдвиге для неё не остаётся места и она пропадет.

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

Для мира 8 устройств сказать что умножение беззнакового числа 128 на 2 мы должны получить 0, и мы его получаем.

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

Как мы помним, самый левый бит отвечает за наличие знака, и если этот знак присутствует, то, чтобы получить значение числа, нужно провести математические операции с оставшимися 7-ю битами.

Попробуем поделить какое-нибудь отрицательное число которое делилось нормально. Например, -2:

0000 0010 // 2
1111 1101 // Инвертируем биты
1111 1110 // Прибавляем единицу, теперь эта последовательность есть число -2

0111 1111 // Сдвигаем по нашему правилу

Впереди числа идёт теперь 0, значит это уже положительное число, математики уже не довольны. Множество единиц в старших разрядах говорит о том что число большое. На самом деле это 127. То есть если мы сдвигаем -2 на 1 бит вправо, то получаем 127. Это что угодно, но не операция деления (сноска 3).

Почему сдвиг сработал с беззнаковыми числами и не работает со знаковыми?

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

Сначала подумаем что происходит со знаком при делении отрицательного целого числа? Правильно, знак сохраняется, при делении на 2 отрицательного числа мы тоже получим отрицательное число (за исключением деления -1, мы должны получить 0, а это не отрицательное число, мы рассмотрим этот случай отдельно).

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

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

Теперь же, вооружившись этими знаниями попробуем поделить числа сдвигом.

1111 1110 // -2
1111 1111 // Единица в старшем разряде осталась, так как была в исходном числе.

1111 1111 // Проверяем что это за число, воспользуемся правилом перевода
0000 0000 // Инвертируем биты
0000 0001 // Добавляем единицу, это число 1, но со знаком минус.

То есть сейчас сдвиг дал результат аналогичный делению на 2. Продолжаем, попробуем ещё какие-нибудь чётные числа.

1001 0010 // 110
1100 1001 // Сдвигаем вправо на 1 бит

1100 1001 // Проверяем число
0011 0110 // Инвертируем биты
0011 0111 // Добавляем 1, это число 55.

Да, это верно. Проблема была с отрицательными нечётными числами. Попробуем поделить -3.

1111 1101 // -3
1111 1110 // Сдвигаем на один бит. 

1111 1110 // Проверяем
0000 0001 // Инвертируем биты
0000 0010 // Добавляем единицу, это 2, с учётом знака -2. 

Ответ -2 должен был навести на пример из начала мы поделили число и округлили результат в сторону отрицательной бесконечности. Таков механизм работы сдвига. И как мы помним мы бы хотели при делении округлять результат в сторону 0 и при делении -3 на 2 получать -1, а не -2.

Значит это только одно, только сдвига недостаточно. Как можно обойти проблему округления в низ? Например, добавить 1 до деления. Тогда для нечётных чисел проблема уйдёт, так как они будут делиться уже без округления (четное число делится на 2 без остатка). А четные числа так же не изменятся, так как делиться они будут с остатком, но округление произойдёт в сторону отрицательной бесконечности. Единицу нужно добавлять только для отрицательных чисел, потому что с положительными и нулём было всё в порядке.

Попробуем поделить некоторые числа:

// -3 / 2

1111 1101   Это число -3
1111 1110   Прибавляем единицу, так как число отрицательное
1111 1111   Сдвигаем на 1 разряд. Результат -1

Ровно то что мы и хотели. Приводить больше примеров нет смысла, попробуйте самостоятельно.

Решение

На базе всех этих знаний попробуем придумать решение на Go:

Вспомним наше начальное решение:

func isBadNumber(a int8) bool {
    return (a < 0) && (a % 2 != 0)
}

func fakedivImproved(a int8) int8 {
    if isBadNumber(a) {
        return (a >> 1) + 1
    }

    return a >> 1
}

Чем же оно плохо? Мы вставляем медленную операцию проверки условия (о) как часть операции которая должна выполняться мгновенно. Тут придётся поверить на слово, объяснять не буду.

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

Поехали. Если число отрицательное, то к результату мы должны добавить единицу, но это сломает деление четных чисел. Вспомним что мы можем добавлять единицу до операции сдвига? Сейчас мы знаем тонкости и видим что это не сломает ни деление чётных, ни деление нечётных. Если число нечётное мы должны добавить единицу без дополнительных действий. Если число чётное, то результат всё равно не изменится, так как у всех чётных чисел, нулевой разряд равен 0, а при сдвиге вправо его значение всё равно потеряется, поэтому его изменение никак на деление не повлияет. Поэтому условие чётности\нечётности можно убрать:

func fakedivImproved(a int8) int8 {
    if a < 0 {
        a++
    }

    return a >> 1
}

Уже намного лучше. Но условие осталось. Чтобы от него избавиться нам бы получить отдельную переменную которая была бы равна 1 только если число отрицательное и эту переменную мы можем добавлять к а. Что мы помним, все отрицательные числа имеют в старшем разряде единицу. Мы можем сдвинуть эту единицу вправо, на 7 разрядов и получить значение один. Для всех не отрицательных чисел мы получим значение ноль, так как старший разряд у них равен нулю. Заметим только то, что сдвигать нужно логически, а не арифметически, без распространения знака.

Это ключевой абзац статьи. Его полное понимание говорит о том, что вы внимательно прочитали статью.

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

func div(a int8) int8 {
    b := uint8(a)
    b >>= 7

    return (a + int8(b)) >> 1
}

Этот код и есть ответ на вопрос - как поделить число на два.

Extra

Основная статья закончена. В этом блоке ещё несколько Go-специфичной информации.

Нужно разобрать деление всех возможных типов целых знаковых чисел, а не только 8 битных. Чтобы формально выполнить задачу. И ещё можем посмотреть какой код генерируется самим компилятором.

Сначала простой вариант, посмотрим что реально делает компьютер⁹:

func div(a int8) int8 {
    return a / 2
}

TEXT    main.div
    MOVL    AX, CX
    SHRB    $7, AL
    ADDL    CX, AX
    SARB    $1, AL
    RET

Что тут происходит? Мы видим 5 инструкций, но само деление происходит только с помощью четырёх, инструкция RET нужна для завершения работы функции. Первая инструкция MOVL которая копирует из регистра AX, где храниться переданное функции значение в регистр CX¹⁰. Далее инструкция SHRB выполняет логический правый сдвиг вправо регистра AL на 7 бит. Мы теряем все биты кроме бита кроме знака (сдвиг логический, поэтому остальные разряды выставлены в 0). Поэтому в регистре A будет значение 1 если число отрицательное или 0 если число не отрицательное.

Далее в регистр AX помещается сумма регистров CX и AX. Далее мы сдвигаем на 1 бит вправо, сдвиг уже знаковый.

Посмотрим на нашу реализацию:

func div(a int8) int8 {
    b := uint8(a)
    b >>= 7

    return (a + int8(b)) >> 1
}

TEXT    main.div
    MOVL    AX, CX
    SHRB    $7, AL
    ADDL    CX, AX
    SARB    $1, AL
    RET

Ассемблерный код полностью эквивалентный. Попробуем с всеми возможными типами:

func div[T int8 | int16 | int32 | int64 | int](a T) T {
    return a / 2
}

Go генерирует различные реализации для каждого типа, посмотрим как выглядит, например, для int16:

TEXT    main.fakedivImproved2[go.shape.int16]
    MOVL    BX, CX
    SHRW    $15, BX
    LEAL    (CX)(BX*1), AX
    SARW    $1, AX
    RET

Всё то же самое. Обратить внимание нужно разве что сдвиг теперь происходит на 15 бит. В остальном код эквивалентный (использование инструкции LEA из-за того что компилятор передаёт первый аргумент через BX, и не хочется после сложения использовать MOV ещё раз, а в LEA могут участвовать три регистра).

Попробуем сделать что-то подобное:

func div2[T int8 | int16 | int32 | int64 | int](a T) T {
    const bytesize = 8

    s := (unsafe.Sizeof(a)*bytesize - 1)
    sign := (uintptr(a) & (uintptr(1) << s)) >> s

    return (a + T(sign)) >> 1
}

Это максимально приближённо выглядит к реальной реализации. Вот реализация для int32:

TEXT    main.div2[go.shape.int32]
    MOVLQSX BX, CX
    MOVL    $2147483648, DX
    ANDQ    DX, CX
    SHRQ    $31, CX
    LEAL    (BX)(CX*1), AX
    SARL    $1, AX
    RET

Плюс две инструкции. Усложнилось только получение единицы для отрицательных значений. Словили то чувство когда код который прогнали через ассемблер выглядит понятнее чем его же версия на языке высокого уровня? Умею могу.

Да, выглядит немного дико, но я так и не придумал как заставить компилятор сгенерировать беззнаковый сдвиг, так как я не могу сконвертировать в unsigned тип соответствующий одному из возможных типов int8/int16/int32/int64/int (в теле функции нужно указать конкретный тип, но конкретный тип зависит от того к какому типу будет применяться функция, а я этого не знаю). Поэтому uintptr.

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

P.S. Разобрался. Система типов ограничена, но есть в спецификации один пункт интересный про конверсию знаковых чисел в беззнаковых. Он мне и помог. Понимаете почему это сработает?

func div3[T int8 | int16 | int32 | int64 | int](a T) T {
    b := uint64(a)
    b >>= 63

    return (a + T(b)) >> 1
}

И пример кода для int32, те же пять инструкций:

TEXT    main.div3[go.shape.int32]
    MOVLQSX BX, CX
    SHRQ    $63, CX
    LEAL    (BX)(CX*1), AX
    SARL    $1, AX
    RET

Механизм получения 1 если число отрицательное тут представляет интерес, но я думаю оставлю это вам на подумать. Попытайтесь не гуглить инструкцию MOVLQSX, должно получиться вывести алгоритм её работы самостоятельно.

Заключение

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

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

Послесловие или деление на два циклом

Отдельная часть. Просто не знаю куда её поставить. Этого блока бы не было, если бы не один забавный момент. Как я говорил выше, я пробовал не только объяснять ЗАДАЧУ друзьям, но и спрашивать, как бы они её решили.

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

— Как бы ты поделил число на два?

— Можно попробовать вычитать делитель из делимого до тех пор, пока делимое больше или равно 0. Кол-во вычитаний и будет равно частному.

Давайте представим этот алгоритм в виде неформального описания:

ШАГ 0. Создать счётчик делений. Присвоить ему значение 0.
ШАГ 1. Вычесть делитель из исходного числа.
ШАГ 2. Если число меньше 0 вернуть счётчик делений.
ШАГ 3. Прибавить единицу к счётчику делений.
ШАГ 4. Если результат равен 0 то вернуть счётчик делений
ШАГ 5. Перейти к шагу 1.

И переведём в реальный код на языке Go:

func rudydiv(x int8) int8 {
    const divisor = 2

    sum := 0

    for {
        x -= divisor

        if x < 0 {
            return sum
        }

        sum++

        if x == 0 {
            return sum
        }
    }
}

Чтож. Это решение не оптимально, даже по сравнению с решением с условием. Так как тут присутствует цикл. Отличается не только константа, но и асимптотика. Сложность этого алгоритма линейная, а не константная как в решении со сдвигом. Но это решение корректное.

Это тоже реальный код, вполне можно увидеть решение в проде. Особенно если инженеры приняли решение, что исследование всех случаем и нахождением закономерностей в сложном решении не стоит потраченного времени и мы можем взять пусть и не оптимальное, но корректное решение (НЕТ, ОНО НЕ ДЕЛИТ ОТРИЦАТЕЛЬНЫЕ ЧИСЛА, ДА ВЫ ПРАВИЛЬНО ПОНЯЛИ, ЭТО УПРАЖНЕНИЕ).

Решение с циклом более простое так как не нужно вникать в представление чисел. Так же можете наблюдать интересную картину, что сложность рождает не дополнительные возможности, а производительность решенения.