Предположим, что cmp принимает 2 одинаковых регистра и начинает сравнивать их по своим MSB, если они равны, следующим битом и так далее. Каково среднее число бит-сравнений, прежде чем мы узнаем, какой регистр имеет большее значение?Сколько итераций делает сборка cmp в среднем?
Поблагодарили бы за решение или, по крайней мере, ответы на 2, 4 и 8 байтовые регистры.
Мы можем остановиться, как только два бита будут разными.
вероятность остановки после 1 итерации: 1/2 (Останавливаемся если 0-1 или 1-0 Мы должны продолжать, если 0-0 или 1-1.).
вероятность остановки после 2-ой итерации: вероятность продолжения после первой итерации * 1/2 = 1/4
вероятность остановки после 3-й итерации: 1/8
вероятность остановки после 4-й итерации: 1/16
вероятность остановки после n-е итерации: 1/(2^n)
Ожидаемое количество итераций для n бит: (1 * 1/2) + (2 * 1/4) + (3 * 1/8) + (4 * 1/16) + ... + (n * 1/(2^n))
Это не так, как cpus это делает, но, конечно же, давайте представим себе :) Чувство моего чувства заключается в том, что количество сравнений для равномерного распределения должно быть «n/2». – Jester
инструкции 'cmp' выполняют вычитание операнда. – NetVipeC