#math #operators #bitwise-operators
#математика #операторы #побитовые операторы
Вопрос:
Я нашел несколько примеров исходного кода, где автор, похоже, использует побитовый amp; оператор вместо % operator . Однако, когда я попробовал x amp; 4 , это не дало того же значения, x % 5 что и .
Комментарии:
1. @user988052 все еще есть. на 10% быстрее под .NET (только что протестировано), код здесь ideone.com/BLqZP (но обратите внимание, что на ideone разница намного меньше). Выпуск запуск без отладчика.
2. @user988052: побитовое и по-прежнему быстрее, чем любая
modреализация общего назначения, которая должна обрабатывать все числа. Но эта оптимизация настолько хорошо известна и проста, что многие компиляторы реализуют ее, так что да. @xanatos: обязательно дайте JIT сначала прогреться при тестировании.3. @xanatos: когда я говорю о «намного быстрее» в те дни, я говорю о побитовом использовании одного или двух циклов процессора и по модулю, используя оставшуюся часть div в регистре, для чего требуется около 20 циклов процессора, если не больше. Поэтому, когда я имел в виду «намного быстрее» , я имел в виду почти на порядок быстрее (в 10 раз, если не намного больше, в зависимости от аппаратного обеспечения). Я не говорю о каких-то 10%, которые, как указал Делнан, в любом случае могут быть оптимизированы автоматически в настоящее время ; )
4. @delnan Вау!! Это правда!!! Когда тепло!!! это тепло !! Нет, никаких различий! Попробовал цикл 100 раз и посмотрел только на последний тест. C # не полностью оптимизирует amp; и %
5. Компиляторы могут выполнять эту оптимизацию только для значений без знака или для значений со знаком, которые, как известно, являются положительными. Это означает, что иногда человек может выполнить эту оптимизацию в случае, когда компилятор не может (потому что у человека есть априорные знания, которых не хватает компилятору).
Ответ №1:
Это работает только для степеней 2.
В общем:
x MOD 2^n
эквивалентно:
x AND (2^n - 1)
Также обратите внимание, что это может быть верно только для x >= 0 , в зависимости от вашего определения MOD for x < 0 .
Чтобы понять, почему это работает, рассмотрим, что такое MOD на самом деле — это просто остаток после выполнения целочисленного деления. В случае деления на 2 ^ n мы фактически просто сдвигаем двоичное значение вправо на n бит и отбрасываем любые младшие биты, которые сдвигаются, например, для 8-битного двоичного числа
a b c d e f g h
если мы разделим на 4 = 2 ^ 2, то мы сдвинемся вправо на 2 бита:
0 0 a b c d e f
Остаток ( g h ) был выброшен в результате целочисленного деления.
Если бы мы хотели узнать остаток, то мы могли бы просто извлечь биты g h , применив маску 0 0 0 0 0 0 1 1 :
a b c d e f g h
AND 0 0 0 0 0 0 1 1
= 0 0 0 0 0 0 g h
Обратите внимание, что has имеет значение 3, которое в общем случае равно всего лишь 2 ^ n — 1.
Давайте попробуем это с некоторыми вещественными числами. Предположим, мы хотим вычислить 42/4 и получить как частное, так и остаток:
42 = 0 0 1 0 1 0 1 0
Чтобы получить частное, мы сдвигаем вправо на 2 бита:
42 / 4 (decimal)
= 0 0 1 0 1 0 1 0 >> 2
= 0 0 0 0 1 0 1 0
= 10 (decimal)
42 MOD 4 (decimal)
= 0 0 1 0 1 0 1 0 AND 0 0 0 0 0 0 1 1
= 0 0 0 0 0 0 1 0
= 2 (decimal)
Итак, 42/4 = 10 остаток 2.
Ответ №2:
Ответ довольно простой, попробуйте мыслить двоично.
0000 = 0 AND 11 = 0000 = 0
0001 = 1 AND 11 = 0001 = 1
0010 = 2 AND 11 = 0010 = 2
0011 = 3 AND 11 = 0011 = 3
0100 = 4 AND 11 = 0000 = 0
0101 = 5 AND 11 = 0001 = 1
0110 = 6 AND 11 = 0010 = 2
0111 = 7 AND 11 = 0011 = 3
… и так далее.
Это дает тот же результат, что и напоминание (% — остаток, формально, а не модуль). Он работает только со степенями 2 и только для нулевых и положительных чисел.