Sammarize May 10 2010 at 13:44

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

3 min

39K

Algorithms*

+37

101

Comments 101

StopKran May 10 2010 at 14:16

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

Sammarize May 10 2010 at 14:27

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

Sammarize May 10 2010 at 14:27

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

StopKran May 10 2010 at 14:34

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

-1

Sammarize May 10 2010 at 21:49

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

metar May 11 2010 at 00:43

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

Mrrl Jan 2 2013 at 23:50

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

OLS May 11 2010 at 06:01

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

vitpetrov Jun 21 2010 at 01:21

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

gribozavr May 10 2010 at 15:17

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

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

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

Sammarize May 10 2010 at 21:59

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

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

gribozavr May 10 2010 at 22:32

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

bit2: 193 мс
bit3: 227 мс

Sammarize May 10 2010 at 23:01

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

-2

mkal May 10 2010 at 23:10

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

gribozavr May 10 2010 at 23:45

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

Sammarize May 10 2010 at 23:51

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

gepeBo May 11 2010 at 11:30

в 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 May 11 2010 at 00:20

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

SergeyOrlov May 20 2010 at 00:39

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

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

u_story May 11 2010 at 10:46

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

Sammarize May 11 2010 at 13:57

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

u_story May 12 2010 at 09:43

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

Sammarize May 12 2010 at 10:02

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

u_story May 12 2010 at 13:23

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

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

Sammarize May 12 2010 at 19:37

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

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

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

gribozavr May 11 2010 at 20:19

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

u_story May 12 2010 at 09:41

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

gribozavr May 12 2010 at 10:00

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

z123 May 10 2010 at 18:50

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

-1

Sammarize May 10 2010 at 21:50

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

theRavel May 10 2010 at 23:58

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

-8

hr0nix May 11 2010 at 00:06

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

+12

z123 May 11 2010 at 10:17

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

mgn May 10 2010 at 19:02

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

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

UFO just landed and posted this here

freeOne May 10 2010 at 22:47

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

DIHALT May 10 2010 at 22:47

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

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

Sammarize May 10 2010 at 23:12

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

DIHALT May 11 2010 at 08:07

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

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

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

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

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

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

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

ruguevara May 11 2010 at 10:25

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

Sammarize May 11 2010 at 14:03

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

mephisto May 10 2010 at 23:28

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

Sammarize May 10 2010 at 23:30

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

mephisto May 10 2010 at 23:34

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

Sammarize May 10 2010 at 23:41

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

mephisto May 10 2010 at 23:43

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

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

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

mephisto May 10 2010 at 23:43

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

mephisto May 10 2010 at 23:39

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

mephisto May 10 2010 at 23:41

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

while (t) t>>=1;

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

bl4de May 11 2010 at 00:03

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

DIHALT May 11 2010 at 08:12

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

ruguevara May 11 2010 at 10:32

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

Sammarize May 11 2010 at 14:51

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

ruguevara May 11 2010 at 16:26

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

Sammarize May 11 2010 at 16:39

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

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

ruguevara May 11 2010 at 21:20

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

ruguevara May 11 2010 at 16:27

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

UFO just landed and posted this here

Sammarize May 10 2010 at 23:44

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

bbbb May 11 2010 at 01:42

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

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

Sammarize May 11 2010 at 14:08

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

bolk May 10 2010 at 23:15

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

-2

Sammarize May 10 2010 at 23:26

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

bolk May 11 2010 at 01:43

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

-2

Sammarize May 11 2010 at 14:15

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

bolk May 11 2010 at 14:19

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

Sammarize May 11 2010 at 14:35

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

bolk May 11 2010 at 14:36

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

Sammarize May 11 2010 at 14:43

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

Quetzal May 10 2010 at 23:23

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

Thomas May 10 2010 at 23:28

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

Sammarize May 10 2010 at 23:32

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

Thomas May 10 2010 at 23:37

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

happybyte May 11 2010 at 00:08

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

Joshik May 11 2010 at 02:05

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

Sammarize May 11 2010 at 14:18

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

stas_agarkov May 12 2010 at 23:28

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

Sammarize May 13 2010 at 09:28

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

stas_agarkov May 13 2010 at 10:07

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

stas_agarkov May 14 2010 at 19:33

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

Sammarize May 15 2010 at 01:14

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

SergeyOrlov May 20 2010 at 00:59

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

me76 May 11 2010 at 06:06

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

-4

TeAnton May 11 2010 at 06:43

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

алгоритм | на случайных данных | на 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 May 11 2010 at 06:51

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

BugEater May 11 2010 at 11:56

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

Sap_ru May 11 2010 at 13:18

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

Vladson May 11 2010 at 17:59

Эх спектрум спектрум, как много в этом слове…
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 May 12 2010 at 10:53

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

Sammarize May 12 2010 at 11:20

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

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

gribozavr May 13 2010 at 01:09

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

stas_agarkov May 12 2010 at 20:43

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

Sammarize May 12 2010 at 22:35

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

SergeyOrlov May 20 2010 at 00:35

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

  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 May 20 2010 at 02:47

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

SergeyOrlov May 20 2010 at 04:28

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

noldo32 Jan 2 2013 at 23:11

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

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

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

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

Mrrl Jan 2 2013 at 23:44

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

noldo32 Jan 3 2013 at 00:06

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

stc
rcl eax, cl

noldo32 Jan 3 2013 at 01:46

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

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

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

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

BOOTLOADER Aug 24 2019 at 01:38

Вот это даже быстрее, чем все ваши 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])

Show the best of all time