Алгоритмы поиска старшего бита

[StopKran]

Сразу подумал о том что будет бинпоиск. Угадал =). Но в общем то странно, зачем нужно решать именно такую задачку. Время работы в обоих случаях очень малы и чтобы почувствовать разницу, нужны очень большие ограничения. Да и вообще, за всё время ни разу не приходилось использовать побитовые операции, и хитрым образом хранить много данных в одной переменной.

[Sammarize]

Ответ ниже, промахнулся ссылкой.

[Sammarize]

Очень большие ограничения — это вряд ли, Вы правы, зато может понадобиться делать это много раз. Я делал миллирд раз (1000 раз на миллионе рандомных чисел), и времена получались для первого метода порядка 0.8 секунды, для следующих двух — порядка 3 секунд.
Я согласен, в работе это может пригодиться, если только очень повезёт. Не могу сказать, что я в работе не использовал битовые операции и не хранил сразу много данных в одном числе, но у меня работа в данный момент спецэфическая, надо чтобы сложный алгоритм распознавания образов работал очень-очень быстро, вот и оптимизирую, как только могу.
Это, скорее, может быть интересно олимпиадным программистам. Мне на олимпиадах, по-моему, один раз приходилось это делать.
Но суть-то не в этом — просто задачка интересная, и методы решения тоже)

[StopKran]

Я занимаюсь олимпиадным программированием, но что то не впечатлила меня задачка. Может быть я просто ещё не дорос до того уровня чтобы оптимизировать каждый малейший кусочек кода.
Рассказали бы про распознавание образов, гораздо более интересная тема.

[Sammarize]

Может, когда-нибудь и расскажу.
Да этим в основном марафонцы занимаются, оптимизированием каждого кусочка кода.

[metar]

Ну, например, для реализации binary indexed tree нужно решить противоположную задачу — найти последний единичный бит числа. Редко звучит на соревнованиях, но бывает.
Вполне возможно, что где-то и старший может пригодиться. :-)

[Mrrl]

Младший единичный — в одну команду: return a&-a;

[OLS]

А что, никто из порицающих статью, не сталкивался с «длинной арифметикой»?
Алгоритмы RSA, DH, ElGamal, когда числа длиной по 2048 бит.
Нужен поиск старшего значащего бита, объективно нужен.
И если удастся его оптимизировать — это тоже хорошо и значимо.

[vitpetrov]

Согласен, однако методы, предложенные в статье, при использовании длинной арифметики не подходят

[gribozavr]

Второй алгоритм хорош тем, что в нём нет условных переходов. Соответственно, блок предсказания переходов не сможет ошибиться никогда.

Ссылки по теме:

graphics.stanford.edu/~seander/bithacks.html
www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
aggregate.org/MAGIC/

[Sammarize]

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

За ссылки спасибо)

[gribozavr]

Только что проверил. CPU: i5-750. 100 запусков по 10 миллионам вызовов, среднее время:

bit2: 193 мс
bit3: 227 мс

[Sammarize]

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

[mkal]

Думаю, язык программирования и компилятор всё же важнее количества ядер при выяснении оптимального алгоритма.

[gribozavr]

g++ (Debian 4.4.2-9) 4.4.3 20100108 (prerelease)

[Sammarize]

java 1.6.0_18
Да, может быть, особенности языка.

[gepeBo]

в java кстати используется именно второй алгоритм:

java.lang.Long
@since 1.5
public static long highestOneBit(long i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
i |= (i >> 32);
return i — (i >>> 1);
}

[Irokez]

даже в одноядерном проце действия распараллеливаются http://en.wikipedia.org/wiki/Pipeline_(computing)

[SergeyOrlov]

Если измеряете на Java, учитывайте, какой компилятор работает: C1 или C2. Разница существенна, как видно из комментариев выше.

  java -client всегда будет использовать C1
  java -server всегда будет использовать С2

[u_story]

Почему выбирается среднее время, а не минимальное?

[Sammarize]

Мне лично минимальное время считать сложнее, поскольку java не очень точна, когда меряешь маленькое время, значит, нужно делать много раз каждый тест, и, желательно, много тестов, по секунде на тест — это долго.

[u_story]

Вы бредете?
фраза — «поскольку java не очень точна», убила наповал.

[Sammarize]

Читайте полностью: «java не очень точна, когда меряешь маленькое время». Имеется в виду, что System.nanoTime(), который я использовал, выдаёт неточный результат. И чем меньше время, которое пытаешься с его помощью померять, тем больше относительная погрешность.

[u_story]

Неточный для чего? для запуска баллистических ракет?

Можно увеличить кол-во вызовов, например, и будет вам ещё большее время. Причём тут наносекунды вообще? %)

[Sammarize]

Что значит, для чего? Он просто не точный. Прогрешность хуже, чем одна наносекунда.

вы вообще читать умеете? Цитата из моего коммента:
«значит, нужно делать много раз каждый тест, и, желательно, много тестов»

Чтобы была нормальная точность, надо делать каждый тест много раз — по моему опыту, миллион даже будет маловато, 10 млн минимум. А то я уже получал какие-то фантастические результаты замеров времени, когда делал 1 000 000 тестов, и время измерялось в милисекундах. А потом всё становилось на свои места, когда я увеличивал количество тестов до миллиарда.
А для репрезентативности выборки надо делать много разных тестов. Вот и получается, что надо делать много раз по секунде.

[gribozavr]

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

[u_story]

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

[gribozavr]

Время выполнения третьего алгоритма зависит от данных.

[z123]

по-моему, задача слишком мелкая, чтоб уделять ей столько внимания

[Sammarize]

Да блин, неужели задача должна быть полезной, чтобы быть интересной?

[theRavel]

Вы можете не согласиться… но как бы да

[hr0nix]

Вы заставляете математиков плакать.

[z123]

вобщем-то нет

[mgn]

Только что наткнулся на еще одну реализацию, но на ассемблере :)

mov bx, 41h
bsr cx, bx ;cx=06h

[freeOne]

Вроде как, надо еще проверить ZF, если в вашем примере bx == 0, то содержимое cx не определено.

[DIHALT]

Сбросить флаг переноса
Сдвигать через перенос по счетчику, проверяя на JNC условие.

В три четыре команды процессора бы уложился. Не оно?

[Sammarize]

О, я так не понимаю. Буду рад, если Вы поясните) Особенно фраза «три-четыре команды» звучит заманчиво — ведь это противоречиит моим представлениям о некоторых теоретических результатах в этой области. Буду рад узнать, что я ошибался.
Но вообще, конечно, обсуждаются реалзации на языке высокого уровня.

[DIHALT]

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

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

А все ветвление в процессоре построено на флагах. Т.е. наличие или отсутствие флага это повод выполнить или игнорировать команду перехода. Флаг переноса это один из таких флагов (есть еще флаг нуля, переполнения, полупереносов, и еще с пол десятка разных)

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

Как только флаг показался. выходим из цикла и число в нашем счетном регистре даст номер первого старшего бита.

Ну и некоторые архитектуры вроде х86 имеют циклические префиксы команд, позволяющие любую команду выполнять много раз, в качестве счетчика цикла использующие один из регистров.

Вообще советую побаловаться ассемблером, прикольный язык. На х86 смотреть смысла особого уже нет, а вот всякие микроконтроллеры вроде AVR или PIC это то что доктор прописал. Заодно научитесь немного рулить железом. Если заинтересовало, то велкам ко мне на сайт :)

[ruguevara]

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

[Sammarize]

Круто, спасибо за такой подробный комментарий, было интересно.
Правда, как уже заметили ruguevara и mephisto, сточки зрения алгоритма — этот, по сути, такой же, как первый.

[mephisto]

с точки зрения алгоритма — первый вариант, немного измененный.

[Sammarize]

Во, мне так и показалось. Возможно, слово «сдвигать» на это указывает.

[mephisto]

в данном случае флаг переноса — как бы 33ий бит, добавляемый к регистру, и устанавливается при сдвиге влево операнда, у которого установлен старший бит.

[Sammarize]

о, спасибо. А сдвигать через перенос по счётчику — это как расшифровывается?

[mephisto]

Это что то вроде…

while (t<(1<<32)) t<<=1;

для 64битного t и при условии что t не может быть >= (1<<32)

[mephisto]

Я во всех примерах счетчики опускаю для простоты)

[mephisto]

Ну а JNC — условный переход при установленном флаге переноса. Используются особенности архитектуры процессора для оптимизации.

[mephisto]

Впрочем, если подумать, по сути это абсолютно аналогично варианту

while (t) t>>=1;

только в обратную сторону.
вместо флага переноса тут используется флаг zero

[bl4de]

bsfl на x86 (находит первый установленный бит в машинном слове)

[DIHALT]

Какая прелесть. В одну команду прям?

[ruguevara]

Ага, но этот, хм.., алгоритм ограничен аппаратным машинным словом и на многоразрядную арифметику не масштабируется. Но это можно использовать эту команду скрестив с бинпоиском:
1. делим длинное число на машинные слова (int)
2. берем серединное слово из числа, вычисляем одной машинной командой его старший бит.
3. Если он есть, запоминаем, берем слово из середины второй половины числа, если его нет, берем слово из середины первой половины числа.

[Sammarize]

Неееет, не годится. Даже если серединное слово полностью нулевое — в более старших словах могут, тем не менее, быть ненулевые биты.

[ruguevara]

Правильно, поэтому надо продолжать бинпоиск в правой части, как я и написал

[Sammarize]

Вы написали — из первой части, то есть, из младшей. У нас с Вами конфликт обозначений) Поэтому предлагаю употреблять термины «старший» и «младший», как не подлежащие сомнению.

Но если серединное слово ненулевое — то тоже надо продолжать поиск в старшей части. Перейти к младшей можно, только проверив всю старшую половину.

[ruguevara]

да, я не прав, такой алгоритм не сработает. Метод «разделяй на слова и оптимизируй поиск старших битов» надо применять по-другому.

[ruguevara]

… в смысле в старшей

[Sammarize]

пффф)) Ну да, Вы, безусловно правы) Этот алгоритм тоже имеет право на существование, и у него есть свои спецИфические плюсы и минусы =)

[bbbb]

а не великовата ли таблица будет))

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

[Sammarize]

Ну да) Для слишком больших типов (уже для 32-х битных) табличка будет уже слишком большой — это и есть специфический минус =)
Но и Вы правы, да. В зависимости от ситуации, возможно, можно сделать и для двух байтов табличку.

[bolk]

Что-то я туплю, видимо.
Чем x & (2^32) не подходит?

[Sammarize]

Ну, пусть мы будем рассматривать long (или long long в С++, короче, 64-битный тип. Иначе 2^32 == 0).
Тогда ваше выражение выдаёт два возможных ответа: 0 или 2^32. Очевидно, что возможных ответов в этой задаче гораздо больше.
& — это побитовое логическое И, не так ли?

[bolk]

& — битовая операция. То есть размер типа мы не знаем, так что ли?

[Sammarize]

Знаем, конечно.
Так, ещё раз. В статье шла речь о числах от 1 до 2^31-1. То есть, о тех, у кого единичными могут быть только биты от 0-го до 30-го. В упомянутом Вами числе единственный ненулевой бит — 32-ой. Значит, не будет ни одного бита, который был бы единичным и в х, и в 2^32. Значит, все биты выражения x & (2^32) будут нулевыми. То есть, результат этого выражения будет равен нулю.

[bolk]

Если размер числа мы знаем, то значение старшего бита находится вот так: x & (2^sizeof(type)), нет?

[Sammarize]

Цитата из поста:
«На всякий случай, поясню: старшим битов называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа.»
Здесь, разумеется, имеется в виду само по себе натуральное число, а не то, сколько места оно занимает в памяти.

[bolk]

Ффух, вот теперь понял, спасибо за терпение :)

[Sammarize]

В следующий раз читайте внимательней.

[Quetzal]

Может быть кому-нибудь понадобится. Куча битхаков: graphics.stanford.edu/~seander/bithacks.html

[Thomas]

Последние два алгоритма имхо — методы половинного деления.

[Sammarize]

Ну, в третьем так и написано, а про второй — я не согласен. Там ничего не делится пополам.

[Thomas]

Сорри туплю. Пойду просплюсь ;)

[happybyte]

Потестите, кто конечный автомат на базе лукап-таблицы. Сам использую несколько модифицированный вариант — в моем применении оказался наиболее быстрым.

[Joshik]

Java использует в Integer.highestOneBit() в точности второй способ.
Так что скорее всего это один из наиболее оптимальных.
Интересно, что младший бит можно найти за одну инструкцию:
x & -x;

[Sammarize]

Да) Я, когда об этом задумался, сначала понял, что все три алгоритма с успехом модифицируются для поиска младшего бита, а потом сообразил, что с младшим всё гораздо проще)

[stas_agarkov]

Почему ява не использует native-код в виде пары команд ассемблера?

[Sammarize]

Вопрос скорее к создателям java, но, думаю, это и так очевидно. Чего ради им жертвовать высокоуровневостью и безопасностью?

[stas_agarkov]

с каких пор арифметические команды x86 стали небезопасными?

[stas_agarkov]

с того же самого, с чего и половина jvm описана как native

[Sammarize]

Так или иначе, вопрос не ко мне)

[SergeyOrlov]

В Джаве, как языке, не может быть ассемблерных инструкций. По возможности код, в том числе системных классов, пишется кросплатформенным образом. Однако для некоторых методов, особенно критичных к производительности, Just-in-Time компилятор может обходить (игнорировать) написанный Java-код, подменяя его асcемблерными инструкциями (так называемые Intrinsic methods). Например, так делается для всяких там String.indexOf, Integer.bitCount, System.arraycopy и т.п.
Очевидно, Long.highestOneBit не является критичным для типичных Java-приложений, и для него нет VM Intrinsics.

[me76]

глупо тратить время на подобные алгоритмы, когда логарифм с основанием 2 выполняется аппаратно

[TeAnton]

я уже проверил, работает медленнее.

алгоритм | на случайных данных | на 1  | на 0x7fffffff | на 0x3fffffff 
bit1     | 25.06               | 255.93| 17.59         | 23.10
bit2     | 40.51               |  39.27| 39.90         | 38.91
bit3     | 40.15               |  26.64| 40.94         | 39.41
log2     | 62.88               |  62.65| 62.75         | 62.63

поправка на цикл и вызов функции: 12.71

[TeAnton]

конечно я использовал frexp он значительно быстрее log2

[BugEater]

В книги Генри Уоррена «Hacker's Delight» таких алгоритмов масса. Рекомендую к прочтению.

[Sap_ru]

А оптимальным таки будет таблица на 32/64/128 элементов и поиск диапазон сдвигом на 5/6/7 бит — т.е. размен память-быстродействие. Особенно полезно для всякого рода микроконтроллеров, где быстродействие ограничено, а память программ, как правило есть с некоторым запасом.

[Vladson]

Эх спектрум спектрум, как много в этом слове…
START LD A,[input]
PUSH BC
LD B,128
LOOP RL A
JR C,EXIT
RR B
JR NC,LOOP
EXIT LD A,B
POP BC
RET

[billyevans]

А еще есть ffs в С. Алгоритмы знать полезно, но лучше использовать стандартную функцию, если это возможно.

[Sammarize]

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

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

[gribozavr]

ffs ищет первый младший бит. Так что это другое.

[stas_agarkov]

два вопроса:
1. зачем нужно вычислять номер самого старшего бита?
2. в процессоре есть команда для этого вычисления. вторая ссылка яндекса: computers.plib.ru/programming/Assembler/Pr/Index4.htm. зачем писать код на ЯВУ для этого?

[Sammarize]

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

[SergeyOrlov]

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

  int bit4(int x) {
     if ((x >>> 24) != 0) { return table24[x >>> 24]; }
     if ((x >>> 16) != 0) { return table16[x >>> 16]; }
     if ((x >>> 8)  != 0) { return table8 [x >>> 8];  }
     return table0[x];
  }

В Джаве этот работает чуть быстрее, чем первые три, на C же данный метод оказывается лучше в 3-5 раз!

[Sammarize]

Надо же. Язык реализации, стало быть, и впрямь очень важен.
А стоит ли создавать 4 таблицы? По скорости выигрываем всего лишь одно сложение, это не скажется сколь-нибудь существенно на скорости работы, а по памяти проигрываем в 4 раза!

[SergeyOrlov]

Пожалуй, да — такая «оптимизация» уже излишняя, одной таблицы достаточно. На C разница в производительности 4%.

[noldo32]

Исходное число держим в EAX…

xor ecx, ecx
@@:
shr eax,1
loopnz @@
neg ecx

труЪ чистый ассемблер рулит!

P.S. Может, на MMX, SSE1/2/3… задача вообще 1 командой решается?

[Mrrl]

Не, в исходной статье не номер бита ищут, а сам бит.
А так, во многих процессорах есть команда clz (или nlz?) — число ведущих нулей.

[noldo32]

тогда добавляем

stc
rcl eax, cl

[noldo32]

Самый быстрый алгоритм, работает даже на i386 :)

; аргумент - в EAX
bsr ecx, eax
; если хотим получить не номер бита (в жизни бывает надо чаще), а соответствующее ему число
mov eax, 1
shl eax, cl
; результат получаем туда же - в EAX

Итак: всего 3(!) машинных команды, i386+

Мораль подтверждается в очередной раз: при прочих равных одна и та же задача решается программным кодом разной тяжести, а скрытые издержки рождаются и устраняются на низком уровне
Если переписывать на ассемблере софт наших информационных систем конечно же нерационально, то надо хотя бы быть разборчивыми к тому, какой груз лишнего кода мы скармливаем процессорам рабочих станций и продакшн-серверов — это есть необходимое условие для того чтобы IT было Lean = без скрытых потерь.

[BOOTLOADER]

Вот это даже быстрее, чем все ваши 3 алгоритма. Находит позицию старшего бита.

var len8tab = [256]uint8{
	0x00, 0x01, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
}

if x >= 1<<16 {
		x >>= 16
		n = 16
	}
	if x >= 1<<8 {
		x >>= 8
		n += 8
	}
	return n + int(len8tab[x])