Проверить, является ли число четным, взглянув на последний бит, есть ли какие-нибудь другие «хитрости», подобные этой?

Question

Недавно я обнаружил, что если мне нужно посмотреть, является ли переменная четной (или нечетной), я могу просто увидеть, равен ли последний бит переменной 0. Это открытие, когда оно было реализовано, заменило несколько по модулю 2 вычисления и, следовательно, вся функция выполнялась быстрее.

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

Answer 1

Я сомневаюсь, что замена использования вычислений по модулю два эквивалентной побитовой операцией произвела более быстрое время выполнения. Любой компилятор C ++, достойный своей частицы соли, будет компилировать n % 2 и n & 1 в идентичные машинные инструкции.

Остерегайтесь использования взломанных битов в качестве оптимизации. Во-первых, не всегда ясно, что функция, которую вы оптимизируете, является узким местом. Во-вторых, полученный код, как правило, сложнее поддерживать и, скорее всего, он неверен или содержит незначительные ошибки. Это то, что подразумевается в известной цитате Кнута: «Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация - корень всего зла». Экономьте свои усилия.

Если вы действительно хотите продолжить эту тему, Bit Twiddling Hacks содержит хороший список интересных хаков.

Answer 2

Здесь есть большой репозиторий хитов с твилами

Answer 3

Ну, есть отличная книга на эту тему: Восторг Хакера (Google books).

На Amazon.com: Восторг хакера .

Answer 4

Есть много. Одна онлайн-коллекция, с которой вы можете начать, это http://www -graphics.stanford.edu / ~ seander / bithacks.html

Я бы настоятельно рекомендовал снова использовать трюки с битами в коде, если только повышение производительности не является абсолютно необходимым. Эти трюки очень нечитаемы, и для них это чувство «никоим образом не работает», поэтому, когда вы пытаетесь выяснить ошибку, это эффективная трата времени для тех, кто пытается отладить код.

Answer 5

Я думал, что "побитовые флаги" были довольно аккуратны, когда я впервые увидел их: http://www.infernodevelopment.com/bitwise-and-flags

Answer 6

Вот хитрый трюк. При сохранении даты в поле базы данных, которое требует интенсивного поиска, не храните дату в формате даты, вместо этого сохраните ее как целое число в формате ГГГГММДД. Базы данных могут искать целые числа намного быстрее, чем в структурах дат.

Answer 7

Может быть полезно отметить, что когда C ++ видит операцию modulo 2 как %2, он обычно оптимизируется без выполнения побитовых операций.

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

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

---

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

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

Может быть, полезно знать, что вы можете поменять местами две 32-битные переменные без третьей временной переменной - с помощью операций XOR. Но было бы гораздо полезнее знать, как для кросс-компиляции требуется обработка с прямым и обратным порядком байтов для 2/4 байтовых переменных и битовые поля .

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

---

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