Мне задали этот вопрос в интервью, чтобы описать вывод в комментариях.Отдел на 3 без оператора деления
unsigned int d2(unsigned int a)
{
__int64 q = (__int64)a * 0x0AAAAAAAB; // (2^33+1)/3
return (unsigned int)(q >> 33);
}
Я проверил другие вопросы в Stackoverflow, связанные с делением на 3, но никто не кажется таким быстрым и маленьким. Может ли кто-нибудь помочь мне объяснить, как функция дает результат, написанный в комментариях?
Функция делит 32-разрядное целое число без знака на 3.
Если умножить на 2^33, а затем разделить на 2^33 (правом сдвиг), то вы получите оригинальный номер. Но если умножить на (2^33)/3 и затем разделить на 2^33, вы фактически разделите на три.
Последняя цифра: B вместо A, чтобы результат был округлен.
Нет необходимости писать это в коде, потому что компилятор обычно сделает это за вас. Try it and see. (Кроме того, для подписанного ввода компилятор может безопасно генерировать сдвинутый сдвиг вправо, но язык C не определяет такую операцию.)
q >> 33 делится на 2^33, но как 0x0AAAAAAAB составляет 2^33/3 ?? –
@Learner Вот что это ... это всего лишь номер. Он округляется от точной доли. – Potatoswatter
Должен быть способ, которым номер поднялся. Не могли бы вы рассказать? –
Должно быть, что-то связано с переполнением. –
Это двоичный эквивалент взятия числа, умножающий его на 100000/3, что составляет около 33333, а затем деление на 100000, оставив его приблизительно равным исходному числу, деленное на 3. – Max
Нечетный вопрос для интервью :) –