Комментарии 101
Сразу подумал о том что будет бинпоиск. Угадал =). Но в общем то странно, зачем нужно решать именно такую задачку. Время работы в обоих случаях очень малы и чтобы почувствовать разницу, нужны очень большие ограничения. Да и вообще, за всё время ни разу не приходилось использовать побитовые операции, и хитрым образом хранить много данных в одной переменной.
0
Очень большие ограничения — это вряд ли, Вы правы, зато может понадобиться делать это много раз. Я делал миллирд раз (1000 раз на миллионе рандомных чисел), и времена получались для первого метода порядка 0.8 секунды, для следующих двух — порядка 3 секунд.
Я согласен, в работе это может пригодиться, если только очень повезёт. Не могу сказать, что я в работе не использовал битовые операции и не хранил сразу много данных в одном числе, но у меня работа в данный момент спецэфическая, надо чтобы сложный алгоритм распознавания образов работал очень-очень быстро, вот и оптимизирую, как только могу.
Это, скорее, может быть интересно олимпиадным программистам. Мне на олимпиадах, по-моему, один раз приходилось это делать.
Но суть-то не в этом — просто задачка интересная, и методы решения тоже)
Я согласен, в работе это может пригодиться, если только очень повезёт. Не могу сказать, что я в работе не использовал битовые операции и не хранил сразу много данных в одном числе, но у меня работа в данный момент спецэфическая, надо чтобы сложный алгоритм распознавания образов работал очень-очень быстро, вот и оптимизирую, как только могу.
Это, скорее, может быть интересно олимпиадным программистам. Мне на олимпиадах, по-моему, один раз приходилось это делать.
Но суть-то не в этом — просто задачка интересная, и методы решения тоже)
+1
Я занимаюсь олимпиадным программированием, но что то не впечатлила меня задачка. Может быть я просто ещё не дорос до того уровня чтобы оптимизировать каждый малейший кусочек кода.
Рассказали бы про распознавание образов, гораздо более интересная тема.
Рассказали бы про распознавание образов, гораздо более интересная тема.
-1
Может, когда-нибудь и расскажу.
Да этим в основном марафонцы занимаются, оптимизированием каждого кусочка кода.
Да этим в основном марафонцы занимаются, оптимизированием каждого кусочка кода.
+1
Ну, например, для реализации binary indexed tree нужно решить противоположную задачу — найти последний единичный бит числа. Редко звучит на соревнованиях, но бывает.
Вполне возможно, что где-то и старший может пригодиться. :-)
Вполне возможно, что где-то и старший может пригодиться. :-)
0
А что, никто из порицающих статью, не сталкивался с «длинной арифметикой»?
Алгоритмы RSA, DH, ElGamal, когда числа длиной по 2048 бит.
Нужен поиск старшего значащего бита, объективно нужен.
И если удастся его оптимизировать — это тоже хорошо и значимо.
Алгоритмы RSA, DH, ElGamal, когда числа длиной по 2048 бит.
Нужен поиск старшего значащего бита, объективно нужен.
И если удастся его оптимизировать — это тоже хорошо и значимо.
0
Второй алгоритм хорош тем, что в нём нет условных переходов. Соответственно, блок предсказания переходов не сможет ошибиться никогда.
Ссылки по теме:
graphics.stanford.edu/~seander/bithacks.html
www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
aggregate.org/MAGIC/
Ссылки по теме:
graphics.stanford.edu/~seander/bithacks.html
www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
aggregate.org/MAGIC/
+6
Это в принипе, конечно, верно, но, как показывает практика (то бишь, эксперименты), третий алгоритм в среднем даже немного быстрее. Кроме того, не думаю, что на пяти условных переходах можно опрелённо сказать, была ли работа предсказателя положительной или отрицательной — это слишком мало, здесь он не совершает никакой осмысленной работы.
За ссылки спасибо)
За ссылки спасибо)
0
Только что проверил. CPU: i5-750. 100 запусков по 10 миллионам вызовов, среднее время:
bit2: 193 мс
bit3: 227 мс
bit2: 193 мс
bit3: 227 мс
0
Хм. Ну, возможно, мои измерения были не совсем точны, и второй алгоритм действительно немного быстрее. Может быть, дело в том, что у Вас многоядерный процессор, а у меня одноядерный? Я, если честно, не очень хорошо в этом разбираюсь, но, может быть, это могло как-то повлиять.
-2
Думаю, язык программирования и компилятор всё же важнее количества ядер при выяснении оптимального алгоритма.
+1
g++ (Debian 4.4.2-9) 4.4.3 20100108 (prerelease)
0
java 1.6.0_18
Да, может быть, особенности языка.
Да, может быть, особенности языка.
+1
даже в одноядерном проце действия распараллеливаются http://en.wikipedia.org/wiki/Pipeline_(computing)
0
Если измеряете на Java, учитывайте, какой компилятор работает: C1 или C2. Разница существенна, как видно из комментариев выше.
java -client всегда будет использовать C1 java -server всегда будет использовать С2
0
Почему выбирается среднее время, а не минимальное?
0
Мне лично минимальное время считать сложнее, поскольку java не очень точна, когда меряешь маленькое время, значит, нужно делать много раз каждый тест, и, желательно, много тестов, по секунде на тест — это долго.
0
Вы бредете?
фраза — «поскольку java не очень точна», убила наповал.
фраза — «поскольку java не очень точна», убила наповал.
0
Читайте полностью: «java не очень точна, когда меряешь маленькое время». Имеется в виду, что System.nanoTime(), который я использовал, выдаёт неточный результат. И чем меньше время, которое пытаешься с его помощью померять, тем больше относительная погрешность.
0
Неточный для чего? для запуска баллистических ракет?
Можно увеличить кол-во вызовов, например, и будет вам ещё большее время. Причём тут наносекунды вообще? %)
Можно увеличить кол-во вызовов, например, и будет вам ещё большее время. Причём тут наносекунды вообще? %)
0
Что значит, для чего? Он просто не точный. Прогрешность хуже, чем одна наносекунда.
вы вообще читать умеете? Цитата из моего коммента:
«значит, нужно делать много раз каждый тест, и, желательно, много тестов»
Чтобы была нормальная точность, надо делать каждый тест много раз — по моему опыту, миллион даже будет маловато, 10 млн минимум. А то я уже получал какие-то фантастические результаты замеров времени, когда делал 1 000 000 тестов, и время измерялось в милисекундах. А потом всё становилось на свои места, когда я увеличивал количество тестов до миллиарда.
А для репрезентативности выборки надо делать много разных тестов. Вот и получается, что надо делать много раз по секунде.
вы вообще читать умеете? Цитата из моего коммента:
«значит, нужно делать много раз каждый тест, и, желательно, много тестов»
Чтобы была нормальная точность, надо делать каждый тест много раз — по моему опыту, миллион даже будет маловато, 10 млн минимум. А то я уже получал какие-то фантастические результаты замеров времени, когда делал 1 000 000 тестов, и время измерялось в милисекундах. А потом всё становилось на свои места, когда я увеличивал количество тестов до миллиарда.
А для репрезентативности выборки надо делать много разных тестов. Вот и получается, что надо делать много раз по секунде.
0
На самом деле кроме среднего ещё считалась дисперсия. Дисперсия с первого раза вышла небольшая (и оставалась небольшой при повторных запусках), поэтому я считаю, что среднему доверять можно.
0
Выполнение кода, это не физический процесс. Другими словами, истинное время выполнения кода, без побочных эффектов, будет ближе именно к минимальному времени выполнения, т.к. все программы и процессы, выполняемые на компьютере, только добавляют погрешность, а нам важно чистое время выполнения кода без влияние внешних факторов.
0
по-моему, задача слишком мелкая, чтоб уделять ей столько внимания
-1
Только что наткнулся на еще одну реализацию, но на ассемблере :)
mov bx, 41h
bsr cx, bx ;cx=06h
mov bx, 41h
bsr cx, bx ;cx=06h
+4
Сбросить флаг переноса
Сдвигать через перенос по счетчику, проверяя на JNC условие.
В три четыре команды процессора бы уложился. Не оно?
Сдвигать через перенос по счетчику, проверяя на JNC условие.
В три четыре команды процессора бы уложился. Не оно?
+1
О, я так не понимаю. Буду рад, если Вы поясните) Особенно фраза «три-четыре команды» звучит заманчиво — ведь это противоречиит моим представлениям о некоторых теоретических результатах в этой области. Буду рад узнать, что я ошибался.
Но вообще, конечно, обсуждаются реалзации на языке высокого уровня.
Но вообще, конечно, обсуждаются реалзации на языке высокого уровня.
+1
Перенос — это флаг С есть по моему во всех процессорах без исключения. Особый флаг состояния процессора, сигнализирующий обычно о заеме или переполнении байта при выполнении предыдущей операции.
Сдвиг через перенос — обычно каждый процессор имеет специфичную команду, позволяющую вращать байт(слово, два слова или более, в зависимости от разрядности) через перенос. Т.е. бит переноса как бы пристраивается к вращемой величине самым младшим или самым старшим битом (в зависимости от направления вращения) и все что вылазит из этого байта при сдвиге вылезате в бит переноса.
А все ветвление в процессоре построено на флагах. Т.е. наличие или отсутствие флага это повод выполнить или игнорировать команду перехода. Флаг переноса это один из таких флагов (есть еще флаг нуля, переполнения, полупереносов, и еще с пол десятка разных)
Таким образом, проверкой флага переноса при вращении байта (слова) влево мы узнаем когда туда вылезет самый старший бит. Останется только подсчитывать итерации цикла, для этого мы щелкаем счетчиком.
Как только флаг показался. выходим из цикла и число в нашем счетном регистре даст номер первого старшего бита.
Ну и некоторые архитектуры вроде х86 имеют циклические префиксы команд, позволяющие любую команду выполнять много раз, в качестве счетчика цикла использующие один из регистров.
Вообще советую побаловаться ассемблером, прикольный язык. На х86 смотреть смысла особого уже нет, а вот всякие микроконтроллеры вроде AVR или PIC это то что доктор прописал. Заодно научитесь немного рулить железом. Если заинтересовало, то велкам ко мне на сайт :)
Сдвиг через перенос — обычно каждый процессор имеет специфичную команду, позволяющую вращать байт(слово, два слова или более, в зависимости от разрядности) через перенос. Т.е. бит переноса как бы пристраивается к вращемой величине самым младшим или самым старшим битом (в зависимости от направления вращения) и все что вылазит из этого байта при сдвиге вылезате в бит переноса.
А все ветвление в процессоре построено на флагах. Т.е. наличие или отсутствие флага это повод выполнить или игнорировать команду перехода. Флаг переноса это один из таких флагов (есть еще флаг нуля, переполнения, полупереносов, и еще с пол десятка разных)
Таким образом, проверкой флага переноса при вращении байта (слова) влево мы узнаем когда туда вылезет самый старший бит. Останется только подсчитывать итерации цикла, для этого мы щелкаем счетчиком.
Как только флаг показался. выходим из цикла и число в нашем счетном регистре даст номер первого старшего бита.
Ну и некоторые архитектуры вроде х86 имеют циклические префиксы команд, позволяющие любую команду выполнять много раз, в качестве счетчика цикла использующие один из регистров.
Вообще советую побаловаться ассемблером, прикольный язык. На х86 смотреть смысла особого уже нет, а вот всякие микроконтроллеры вроде AVR или PIC это то что доктор прописал. Заодно научитесь немного рулить железом. Если заинтересовало, то велкам ко мне на сайт :)
+4
У вас получился первый алгоритм с циклом, только самым лучшим образом портированный (если можно так сказать) на ассемблер. С такими же сравнительными характеристиками времени работы.
+2
Круто, спасибо за такой подробный комментарий, было интересно.
Правда, как уже заметили ruguevara и mephisto, сточки зрения алгоритма — этот, по сути, такой же, как первый.
Правда, как уже заметили ruguevara и mephisto, сточки зрения алгоритма — этот, по сути, такой же, как первый.
0
с точки зрения алгоритма — первый вариант, немного измененный.
0
Во, мне так и показалось. Возможно, слово «сдвигать» на это указывает.
0
в данном случае флаг переноса — как бы 33ий бит, добавляемый к регистру, и устанавливается при сдвиге влево операнда, у которого установлен старший бит.
0
Ну а JNC — условный переход при установленном флаге переноса. Используются особенности архитектуры процессора для оптимизации.
0
Впрочем, если подумать, по сути это абсолютно аналогично варианту
while (t) t>>=1;
только в обратную сторону.
вместо флага переноса тут используется флаг zero
while (t) t>>=1;
только в обратную сторону.
вместо флага переноса тут используется флаг zero
0
bsfl на x86 (находит первый установленный бит в машинном слове)
+3
Какая прелесть. В одну команду прям?
+1
Ага, но этот, хм.., алгоритм ограничен аппаратным машинным словом и на многоразрядную арифметику не масштабируется. Но это можно использовать эту команду скрестив с бинпоиском:
1. делим длинное число на машинные слова (int)
2. берем серединное слово из числа, вычисляем одной машинной командой его старший бит.
3. Если он есть, запоминаем, берем слово из середины второй половины числа, если его нет, берем слово из середины первой половины числа.
1. делим длинное число на машинные слова (int)
2. берем серединное слово из числа, вычисляем одной машинной командой его старший бит.
3. Если он есть, запоминаем, берем слово из середины второй половины числа, если его нет, берем слово из середины первой половины числа.
0
Неееет, не годится. Даже если серединное слово полностью нулевое — в более старших словах могут, тем не менее, быть ненулевые биты.
0
Правильно, поэтому надо продолжать бинпоиск в правой части, как я и написал
0
Вы написали — из первой части, то есть, из младшей. У нас с Вами конфликт обозначений) Поэтому предлагаю употреблять термины «старший» и «младший», как не подлежащие сомнению.
Но если серединное слово ненулевое — то тоже надо продолжать поиск в старшей части. Перейти к младшей можно, только проверив всю старшую половину.
Но если серединное слово ненулевое — то тоже надо продолжать поиск в старшей части. Перейти к младшей можно, только проверив всю старшую половину.
0
… в смысле в старшей
0
НЛО прилетело и опубликовало эту надпись здесь
пффф)) Ну да, Вы, безусловно правы) Этот алгоритм тоже имеет право на существование, и у него есть свои спецИфические плюсы и минусы =)
0
а не великовата ли таблица будет))
как вариант, можно немного усложнить, и сделать таблицу для байта, а потом искать старший байт с единичным битом, и высчитывать результат.
как вариант, можно немного усложнить, и сделать таблицу для байта, а потом искать старший байт с единичным битом, и высчитывать результат.
+1
Что-то я туплю, видимо.
Чем x & (2^32) не подходит?
Чем x & (2^32) не подходит?
-2
Ну, пусть мы будем рассматривать long (или long long в С++, короче, 64-битный тип. Иначе 2^32 == 0).
Тогда ваше выражение выдаёт два возможных ответа: 0 или 2^32. Очевидно, что возможных ответов в этой задаче гораздо больше.
& — это побитовое логическое И, не так ли?
Тогда ваше выражение выдаёт два возможных ответа: 0 или 2^32. Очевидно, что возможных ответов в этой задаче гораздо больше.
& — это побитовое логическое И, не так ли?
+1
& — битовая операция. То есть размер типа мы не знаем, так что ли?
-2
Знаем, конечно.
Так, ещё раз. В статье шла речь о числах от 1 до 2^31-1. То есть, о тех, у кого единичными могут быть только биты от 0-го до 30-го. В упомянутом Вами числе единственный ненулевой бит — 32-ой. Значит, не будет ни одного бита, который был бы единичным и в х, и в 2^32. Значит, все биты выражения x & (2^32) будут нулевыми. То есть, результат этого выражения будет равен нулю.
Так, ещё раз. В статье шла речь о числах от 1 до 2^31-1. То есть, о тех, у кого единичными могут быть только биты от 0-го до 30-го. В упомянутом Вами числе единственный ненулевой бит — 32-ой. Значит, не будет ни одного бита, который был бы единичным и в х, и в 2^32. Значит, все биты выражения x & (2^32) будут нулевыми. То есть, результат этого выражения будет равен нулю.
0
Если размер числа мы знаем, то значение старшего бита находится вот так: x & (2^sizeof(type)), нет?
0
Цитата из поста:
«На всякий случай, поясню: старшим битов называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа.»
Здесь, разумеется, имеется в виду само по себе натуральное число, а не то, сколько места оно занимает в памяти.
«На всякий случай, поясню: старшим битов называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа.»
Здесь, разумеется, имеется в виду само по себе натуральное число, а не то, сколько места оно занимает в памяти.
0
Может быть кому-нибудь понадобится. Куча битхаков: graphics.stanford.edu/~seander/bithacks.html
+2
Последние два алгоритма имхо — методы половинного деления.
0
Потестите, кто конечный автомат на базе лукап-таблицы. Сам использую несколько модифицированный вариант — в моем применении оказался наиболее быстрым.
0
Java использует в Integer.highestOneBit() в точности второй способ.
Так что скорее всего это один из наиболее оптимальных.
Интересно, что младший бит можно найти за одну инструкцию:
x & -x;
Так что скорее всего это один из наиболее оптимальных.
Интересно, что младший бит можно найти за одну инструкцию:
x & -x;
+4
Да) Я, когда об этом задумался, сначала понял, что все три алгоритма с успехом модифицируются для поиска младшего бита, а потом сообразил, что с младшим всё гораздо проще)
0
Почему ява не использует native-код в виде пары команд ассемблера?
0
Вопрос скорее к создателям java, но, думаю, это и так очевидно. Чего ради им жертвовать высокоуровневостью и безопасностью?
0
В Джаве, как языке, не может быть ассемблерных инструкций. По возможности код, в том числе системных классов, пишется кросплатформенным образом. Однако для некоторых методов, особенно критичных к производительности, Just-in-Time компилятор может обходить (игнорировать) написанный Java-код, подменяя его асcемблерными инструкциями (так называемые Intrinsic methods). Например, так делается для всяких там String.indexOf, Integer.bitCount, System.arraycopy и т.п.
Очевидно, Long.highestOneBit не является критичным для типичных Java-приложений, и для него нет VM Intrinsics.
Очевидно, Long.highestOneBit не является критичным для типичных Java-приложений, и для него нет VM Intrinsics.
0
глупо тратить время на подобные алгоритмы, когда логарифм с основанием 2 выполняется аппаратно
-4
я уже проверил, работает медленнее.
поправка на цикл и вызов функции: 12.71
алгоритм | на случайных данных | на 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
+2
В книги Генри Уоррена «Hacker's Delight» таких алгоритмов масса. Рекомендую к прочтению.
+2
А оптимальным таки будет таблица на 32/64/128 элементов и поиск диапазон сдвигом на 5/6/7 бит — т.е. размен память-быстродействие. Особенно полезно для всякого рода микроконтроллеров, где быстродействие ограничено, а память программ, как правило есть с некоторым запасом.
0
Эх спектрум спектрум, как много в этом слове…
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
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
+1
А еще есть ffs в С. Алгоритмы знать полезно, но лучше использовать стандартную функцию, если это возможно.
0
Замечание в целом верное (когда речь касается промышленного программирования, а не олимпиадного), но сразу замечу, что вопрос исследовался скорее из интереса, нежели для пользы дела.
Если же говорить о деле, то изредка всё же лучше писать своё, даже если возможно использовать стандартный метод — и для этой цели в статье в некоторой степени исследован вопрос о том, в каких случаях какой метод лучше применить.
Если же говорить о деле, то изредка всё же лучше писать своё, даже если возможно использовать стандартный метод — и для этой цели в статье в некоторой степени исследован вопрос о том, в каких случаях какой метод лучше применить.
0
ffs ищет первый младший бит. Так что это другое.
0
два вопроса:
1. зачем нужно вычислять номер самого старшего бита?
2. в процессоре есть команда для этого вычисления. вторая ссылка яндекса: computers.plib.ru/programming/Assembler/Pr/Index4.htm. зачем писать код на ЯВУ для этого?
1. зачем нужно вычислять номер самого старшего бита?
2. в процессоре есть команда для этого вычисления. вторая ссылка яндекса: computers.plib.ru/programming/Assembler/Pr/Index4.htm. зачем писать код на ЯВУ для этого?
0
Табличный алгоритм уже упоминали, а я, ради интереса, реализовал и проверил следующий вариант (оптимальный, на мой взгляд, по соотношению скорость-память). Таблицы большего размера хуже еще тем, что они не всегда будут полностью умещаться в кэше процессора.
В Джаве этот работает чуть быстрее, чем первые три, на C же данный метод оказывается лучше в 3-5 раз!
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 раз!
+1
Надо же. Язык реализации, стало быть, и впрямь очень важен.
А стоит ли создавать 4 таблицы? По скорости выигрываем всего лишь одно сложение, это не скажется сколь-нибудь существенно на скорости работы, а по памяти проигрываем в 4 раза!
А стоит ли создавать 4 таблицы? По скорости выигрываем всего лишь одно сложение, это не скажется сколь-нибудь существенно на скорости работы, а по памяти проигрываем в 4 раза!
0
Исходное число держим в EAX…
труЪ чистый ассемблер рулит!
P.S. Может, на MMX, SSE1/2/3… задача вообще 1 командой решается?
xor ecx, ecx
@@:
shr eax,1
loopnz @@
neg ecx
труЪ чистый ассемблер рулит!
P.S. Может, на MMX, SSE1/2/3… задача вообще 1 командой решается?
0
Самый быстрый алгоритм, работает даже на i386 :)
Итак: всего 3(!) машинных команды, i386+
Мораль подтверждается в очередной раз: при прочих равных одна и та же задача решается программным кодом разной тяжести, а скрытые издержки рождаются и устраняются на низком уровне
Если переписывать на ассемблере софт наших информационных систем конечно же нерационально, то надо хотя бы быть разборчивыми к тому, какой груз лишнего кода мы скармливаем процессорам рабочих станций и продакшн-серверов — это есть необходимое условие для того чтобы IT было Lean = без скрытых потерь.
; аргумент - в EAX
bsr ecx, eax
; если хотим получить не номер бита (в жизни бывает надо чаще), а соответствующее ему число
mov eax, 1
shl eax, cl
; результат получаем туда же - в EAX
Итак: всего 3(!) машинных команды, i386+
Мораль подтверждается в очередной раз: при прочих равных одна и та же задача решается программным кодом разной тяжести, а скрытые издержки рождаются и устраняются на низком уровне
Если переписывать на ассемблере софт наших информационных систем конечно же нерационально, то надо хотя бы быть разборчивыми к тому, какой груз лишнего кода мы скармливаем процессорам рабочих станций и продакшн-серверов — это есть необходимое условие для того чтобы IT было Lean = без скрытых потерь.
+1
Вот это даже быстрее, чем все ваши 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])
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмы поиска старшего бита