sharpc (sharpc) wrote,
sharpc
sharpc

Categories:
  • Music:

Битхак

Что это?
(u ^ (u | (u-1))) + 1


UPD: renatm первым указал, что этот код (4 команды) оставляет в числе установленным только младший единичный бит, dfyz вспомнил более короткий (3 команды) вариант:
u & ~(u-1)
а arti_kz еще более короткий (тоже 3 команды):
u & -u

Интересно сравнить их ассемблерный код и скорость выполнения 1730000000 итераций в цикле (примерно такова тактовая частота моего процессора):

(u ^ (u | (u-1))) + 1lea edx, [eax-1]
or edx, eax
xor edx, eax
inc edx
2953ms
u ^ (u | (u-1))lea edx, [eax-1]
or edx, eax
xor edx, eax
2263ms
u & ~(u-1)lea edx, [eax-1]
not edx
and edx, eax
1965ms
u & -umov edx, eax
neg edx
and edx, eax
1916ms


До чего техника дошла! ©

На самом деле, конечно, компилятор частично раскрывает циклы, что позволяет процессору эффективно параллелить вычисления.
Tags: головоломки, программирование
Subscribe

  • Инфраструктура Python

    В ноябре 2017 я начал собирать в виде IPython Notebook сниппеты работы с разными полезными для исследовательского программирования библиотеками…

  • Теормин по STL для СП, часть 2/2

    Это продолжение части 1. <algorithm>В STL реализованы некоторые простые и часто используемые обобщенные алгоритмы. Обобщенные они потому,…

  • Теормин по STL для СП, часть 1/2

    Это теоретический минимум по STL для занимающихся спортивным программированием, подмножество возможностей стандартной библиотеки C++, полезных для…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments

  • Инфраструктура Python

    В ноябре 2017 я начал собирать в виде IPython Notebook сниппеты работы с разными полезными для исследовательского программирования библиотеками…

  • Теормин по STL для СП, часть 2/2

    Это продолжение части 1. <algorithm>В STL реализованы некоторые простые и часто используемые обобщенные алгоритмы. Обобщенные они потому,…

  • Теормин по STL для СП, часть 1/2

    Это теоретический минимум по STL для занимающихся спортивным программированием, подмножество возможностей стандартной библиотеки C++, полезных для…