Home

Реклама

Настроить

Битхак

music: Amberian Dawn — [River Of Tuoni CD01 #04] Valkyries
Что это?
(u ^ (u | (u-1))) + 1


UPD: [info]renatm первым указал, что этот код (4 команды) оставляет в числе установленным только младший единичный бит, [info]dfyz вспомнил более короткий (3 команды) вариант:
u & ~(u-1)
а [info]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


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

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

Posted on 24 Фев, 2009 at 18:38 | | Комментарий | в избранное | рассказать другу

Comments

[info]renatm

младший бит?
Posted on 24 Фев, 2009 16:45 (UTC) | | Ветвь дискуссии | Ответить

[info]ivan_ghandhi

Это младший бит. Не знаю, зачем нужны такие задачки, но определённого сорта люди очень их любят. Мне кажется, это те же самые люди, которые считают что джава тормозит, а комментарии и юниттесты - для тупых.
Posted on 24 Фев, 2009 16:49 (UTC) | | Ветвь дискуссии | Ответить

[info]sharpc

Тожп не знаю — случайно придумалось. «Жава не тормозит». Юнит-тесты — для неуверенных :)
Posted on 24 Фев, 2009 16:53 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]arti_kz

не проще u & -u ?
Posted on 24 Фев, 2009 17:17 (UTC) | | Ветвь дискуссии | Ответить

[info]sharpc

Проще.
Posted on 24 Фев, 2009 18:47 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]ivan_ghandhi

~(n-1) и -n - одно и то же.
Posted on 24 Фев, 2009 18:51 (UTC) | | Ветвь дискуссии | Ответить

[info]sharpc

Конечно.
Posted on 24 Фев, 2009 19:18 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]nusut

А почему не просто u&1 ? Простые пути не для умных?
Posted on 24 Фев, 2009 18:59 (UTC) | | Ветвь дискуссии | Ответить

[info]nusut

Нелюбовь к непосредственным операндам?
Posted on 24 Фев, 2009 19:05 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]sharpc

Поправил: младший единичный бит.
Posted on 24 Фев, 2009 19:17 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]nusut

а разница?

Мнэ... И что?
Posted on 24 Фев, 2009 20:02 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]sharpc

Re: а разница?

110100 - (u & -u) -> 000100
110100 - (u & 1) -> 000000
Posted on 24 Фев, 2009 20:25 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]nusut

Re: а разница?

Понял :)
Лучше тогда писать "младший ненулевой бит"
Posted on 24 Фев, 2009 21:33 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]zhengxi

кстати, а u&1 процессор быстрее выполнит ?
мне кажется, что да, но об`яснить не могу :)
Posted on 24 Фев, 2009 19:18 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

[info]nusut

Вообще, не факт. На многих машинах загрузка непосредственного операнда выполняется медленно (скажем, два такта против одного в случае загрузки с указанного адреса). Так, простое присваивание x = 0 выполняется дольше, чем XOR с самим собой x ^= x. Но в программах такие ухищрения обычно не используются, поскольку понятность кода всё же снижается, а эффективность... Вне цикла не важно, а внутри цикла легко лечится выделением временной регистровой переменной. Причём, лечением занимается сам компилятор. :)
Posted on 24 Фев, 2009 20:02 (UTC) | | Уровень выше | Ветвь дискуссии | Ответить

Реклама

Настроить