Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
> Угадайте откуда кандидат 🙂
Да чего тут угадывать, все люди оттуда рождаются, не из пробирки же, право слово.
Или ты до сих пор веришь в сказки про аиста и капусту? 🙂
У кода без цикла этого недостатка нет. Он за фиксированное число тактов отрабатывает для любого N. И вообще у него логарифмическая зависимость от количества битов...
P.S. Ну а если с циклом - согласен, от старших битов выгоднее начинать, т.к. старший бит у половины чисел установлен.
1) Битоёбский вариант со сведением к bit_count один хрен раза в 3 быстрее (на всём диапазоне uint32_t, т.е. фактически по матожиданию).
2) Решает не ту задачу - считает количество ненулевых битов, а не значащих (но можно свести к нужной пачкой сдвигов, как я и поступил выше).
>битоёбский вариант со сведением к bit_count один хрен раза в 3 быстрее
Тут нужно искать бинарным поиском, примерно так:
if (num == 0) return 0;
int n = 14;
if (num >> 8 == 0) { n -= 8; num <<= 8; }
if (num >> 12 == 0) { n -= 4; num <<= 4; }
if (num >> 14 == 0) { n -= 2; num <<= 2; }
n += num >> 15;
return n;
> С правильными - 16 секунд. Все-таки branch'и не рулят ;(
Один можно убрать. Всё же в реальных условиях 0 может приходить чаще всего.
>if (num == 0) return 0;
Без этого должно быть быстрее.
[code language=cpp]
unsigned int v; // 32-bit value to find the log2 of
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;
r = (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);
[/code]
unsigned int count_1bits(unsigned int x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = x + (x >> 4);
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
http://www.cs.utsa.edu/~wagner/knuth/
Скачать бесплатно без регистрации и смс.
Удовлетворит ваши самые грязные битоебские фантазии и хаки. Так же в наличии описание генерации всевозможных извращённых позиций и сочетаний.
>Четвёртый том?
Еще 4-5 лет назад. Я дждесять лет ждал от Кнута именно Bitwise tricks and techniques - тема совсем не была раскрыта.
Но по слухам он насобирал материала как минимум на семь томов (по три книги в томе - A,B,C) - человеческой жизни не хватит. Он в каком-то томе объяснял почему рано ушёл на пенсию - университетская работа отнимала много времени.
Видимо и после его смерти будут издавать новые. Просто лично мне теория языков, компиляторов и лексический анализ не настолько интересны/полезны.
>Кармак нашей вселенной делал плавающую магию через целочисленную.
Тарас тоже много чего делал. Но видать не в ту эпоху родился.
И вообще заебали своим Кармаком. Быстрый квадратный корень и другие хаки придумал не он. Заслуга в другом: он просто ловко воспользовался этими всеми наработками при написании движков для крутых игр и смог поднять на этом кучу денег.
А потом еще выложил движки в опен-сорс.
Дабл состоит из 1 бита знака, 11 бит порядка и 52 бита мантиссы.
После сборки дабла из джвух половинок получаем 43300000 XXXXXXXX, где XXXXXXXX = num. Т.е. положительное число с мантиссой 1.<двадцать ноликов><num> и порядком 0x433 - 1023 = 52 т.е. 1.<двадцать ноликов><num> * pow(2, 52), что составляет... 2^52 + num.
В шестой строке из этого числа вычитается 2^52 и FPU нормализует число так, чтобы старшая единичка стояла перед точкой в мантиссе. Например, из числа 0xFFFFFFF мы получим 2^31 * 1.11111... Порядок получится на единичку меньше, чем нужный нам ответ.
Затем мы снова рассматривает дабл как набор битов, вычленяем из него порядок и добавляем к нему недостающую единичку.
А мне интересно, сколько времени было потрачено на разработку каждого алгоритма подсчета количества значащих бит. Я на цикл потратил около 30 секунд.
К тому же, имеет значение задача, под которую алгоритм можно применить. Предположим, принесли нам гигабайт статистических данных, для которых нужно подсчитать максимальное количество значащих бит. Весь массив можно поразрядным or "запаковать" в одно слово и подсчитать его биты; тут скорость алгоритма уже не имеет такого значения. А если сами данные состоят сплошняком из нулей и единиц, то цикл с линейной сложностью отработает быстрее.
К тому же меня всегда беспокоила адекватность подобных бенчмарков, на которые влияют энергосберегающие состояния процессора, кэш (который, вроде, можно сбросить, поставив полный барьер памяти) и другие факторы.
> А мне интересно, сколько времени было потрачено на разработку каждого алгоритма подсчета количества значащих бит. Я на цикл потратил около 30 секунд.
На 32 - __builtin_clz(num) где-то столько же 😉
>А мне интересно, сколько времени было потрачено на разработку каждого алгоритма подсчета количества
Минут 5 на двоичный поиск. Думаю циклом было бы короче/понятней. А компилер бы уже развернул сам.
>#240308 (двоичный поиск с if'ами) - 0m15.908s
А если 1-й if убрать? //if (num == 0) return 0;
Чёто не верю что ifы сливают. Правда я особо и не старался.
>__builtin_clz
Некросскомпилерно
Большие и непонятные числа - только чтобы нубов пугать - оооо какое хитрое байтоебство.
А всё можно свести к очевидному и интуитивно понятному коду:
unsigned int bits1(unsigned int num) {
union {unsigned int asInt[2];double asDouble;} t;
t.asDouble = (double)num; //+0.5 для коррекции
return (t.asInt[LE] >> 20)-0x400+2;
}
При том что задача стоит "Посчитать количество значащиз битов в 16ти разрядном целом."
Я бы сделал табличку на 64К, или выпилил ifы нахер.
return (x & 0x0000FF00)? first_bit[x >> 8] + 8 : first_bit[x];
Она один раз формируется. Любой из способов с этой страницы проканает. Ну либо можно чуть более оптимальное заполнение замутить. Как-то так например:
first_bit[0] = 0;
for (uint32_t i = 1, m = 0, n = 0; i<65536; ++i) {
if ((i & m) == 0) // битов стало больше
m = (m << 1) | 1, ++n;
first_bit[i] = n;
}
Тэкс. Ну я ж писал это чисто для лулзов. Не люблю я ёбанный fpu, unionы. И __builtin_clz тоже.
Алгоритм должен быть таким чтоб я мог пользоваться им в жабе, жс, питоне и остальных языках.
Хотя машине Борманда верить нельзя - у меня когда-то ifы оказались самым быстрым что я смог придумать, но попробуем без них.
unsigned int bits1(unsigned int x) {
int y, m=0, n=0;
y = x - 0x100; m = (y >> 16) & 8; n += m; x <<= m;
y = x - 0x1000; m = (y >> 16) & 4; n += m; x <<= m;
y = x - 0x4000; m = (y >> 16) & 2; n += m; x <<= m;
y = x >> 14; m = y & ~(y >> 1);
return 14 - n + m;
}
Лично я считаю этот код оптимальным.
Трейдофф между скоростью, читабельностью, краткостью и портабельностью (на другие языки и размеры чисел).
int binarySearch(int x) {
int y=0, n=1, c=8; // поставить sizeof/2 для универсальности
do {
y = x >> c;
if (y != 0) {n += c; x = y;}
c >>= 1;
} while (c != 0);
return n;
}
Ничего не понимаю. Каждый второй на сайте, неибаца хацкелист и теоретик, а это говно приходится постить мне.
int ln(int x, int shift, int n) {
int y = x >> shift;
if (y != 0) {x=y;n += shift;}
return (shift!=0) ? ln(x,shift>>1,n): n;
}
int ln1(int x, int shift, int n) {
int y = x >> shift;
if (y != 0) {x=y;n += shift;}
return (shift!=2) ? ln(x,shift>>1,n): n+(x>>1);
}
Битоебы-битоебики...
> studio.h
> printf(“
> unit16
> enetr
ВОННИ, Т ПРНС?
> uint16 final
fail
Да чего тут угадывать, все люди оттуда рождаются, не из пробирки же, право слово.
Или ты до сих пор веришь в сказки про аиста и капусту? 🙂
так интереснее же
Мы круги рисуем
Оу е!
int count = 0; while(num) num >>=1, ++count; return count;
Я лох и обосрался 😉 Минусуйте коды ниже, они не ту задачу решают.
Пропустил букву прям как в umount.
num >>= 1;
Число Тараса 1<<31 - 32 итерации. А можно за 1.
P.S. Ну а если с циклом - согласен, от старших битов выгоднее начинать, т.к. старший бит у половины чисел установлен.
для всего остального есть национальная платёжная система
она же только в Крыму работает
не на курорты северного кавказа же ехать, право слово
fixed
2) Решает не ту задачу - считает количество ненулевых битов, а не значащих (но можно свести к нужной пачкой сдвигов, как я и поступил выше).
Тут нужно искать бинарным поиском, примерно так:
И, походу, это самый быстрый способ (3 секунды против 14 у <<240298 на всех uint32_t).
Один можно убрать. Всё же в реальных условиях 0 может приходить чаще всего.
>if (num == 0) return 0;
Без этого должно быть быстрее.
Битов с единичкой тут всего 2. А значащих - аж 25 (все, кроме ведущих нулей).
[code language=cpp]
unsigned int v; // 32-bit value to find the log2 of
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;
r = (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);
[/code]
Источник: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
А код годный, спасибо, подрочил. Жаль, что я вчера тесты в /tmp делал и после ребута они стерлись, а заново писать лень...
Если у кого-то есть время и желание - сравните по скорости с другими вариантами из этого треда.
Вроде fixed, проверьте кто-нибудь.
Ты просто раскрыл выражение, или что-то поменял внутри?
Скачать бесплатно без регистрации и смс.
Удовлетворит ваши самые грязные битоебские фантазии и хаки. Так же в наличии описание генерации всевозможных извращённых позиций и сочетаний.
Еще 4-5 лет назад. Я дждесять лет ждал от Кнута именно Bitwise tricks and techniques - тема совсем не была раскрыта.
Но по слухам он насобирал материала как минимум на семь томов (по три книги в томе - A,B,C) - человеческой жизни не хватит. Он в каком-то томе объяснял почему рано ушёл на пенсию - университетская работа отнимала много времени.
Видимо и после его смерти будут издавать новые. Просто лично мне теория языков, компиляторов и лексический анализ не настолько интересны/полезны.
> a = (a & 0x55555555) + ((a & 0xAAAAAAAA) >> 1);
Разобьем на четные и нечетные половинки. Сложим их. Теперь у нас есть 16 джвухбитных чисел.
> a = (a & 0x33333333) + ((a & 0xCCCCCCCC) >> 2);
Опять бьем и складываем, получая 8 четырехбитных.
и т.д.
В итоге получается одно 16 битное число, в котором лежит сумма всех исходных 1 битных (т.е. то самое количество единичек).
4503599627370496.0
Это всего лишь 2 в 52 степени.
Это Кармак из зеркальной вселенной!1адын
Тарас тоже много чего делал. Но видать не в ту эпоху родился.
И вообще заебали своим Кармаком. Быстрый квадратный корень и другие хаки придумал не он. Заслуга в другом: он просто ловко воспользовался этими всеми наработками при написании движков для крутых игр и смог поднять на этом кучу денег.
А потом еще выложил движки в опен-сорс.
После сборки дабла из джвух половинок получаем 43300000 XXXXXXXX, где XXXXXXXX = num. Т.е. положительное число с мантиссой 1.<двадцать ноликов><num> и порядком 0x433 - 1023 = 52 т.е. 1.<двадцать ноликов><num> * pow(2, 52), что составляет... 2^52 + num.
В шестой строке из этого числа вычитается 2^52 и FPU нормализует число так, чтобы старшая единичка стояла перед точкой в мантиссе. Например, из числа 0xFFFFFFF мы получим 2^31 * 1.11111... Порядок получится на единичку меньше, чем нужный нам ответ.
Затем мы снова рассматривает дабл как набор битов, вычленяем из него порядок и добавляем к нему недостающую единичку.
Вот и вся магия 😉
Так вот полагаю передача данных в FPU и обратно будет ооочень медленной.
#240467 (даблоёбство) - 0m21.729s
#240298 (сведение к подсчету ненулевых битов) - 0m14.605s
#240308 (двоичный поиск с if'ами) - 0m15.908s
#240403 (двоичный поиск без if'ов) - 0m27.734s
Прога: http://pastebin.com/mXV6ESvm
А мне интересно, сколько времени было потрачено на разработку каждого алгоритма подсчета количества значащих бит. Я на цикл потратил около 30 секунд.
К тому же, имеет значение задача, под которую алгоритм можно применить. Предположим, принесли нам гигабайт статистических данных, для которых нужно подсчитать максимальное количество значащих бит. Весь массив можно поразрядным or "запаковать" в одно слово и подсчитать его биты; тут скорость алгоритма уже не имеет такого значения. А если сами данные состоят сплошняком из нулей и единиц, то цикл с линейной сложностью отработает быстрее.
К тому же меня всегда беспокоила адекватность подобных бенчмарков, на которые влияют энергосберегающие состояния процессора, кэш (который, вроде, можно сбросить, поставив полный барьер памяти) и другие факторы.
Не вижу смысла в битоёбстве, короче. Вот.
На 32 - __builtin_clz(num) где-то столько же 😉
Минут 5 на двоичный поиск. Думаю циклом было бы короче/понятней. А компилер бы уже развернул сам.
А если 1-й if убрать? //if (num == 0) return 0;
Чёто не верю что ifы сливают. Правда я особо и не старался.
>__builtin_clz
Некросскомпилерно
Ну они всего несколько процентов сливают.
> А если 1-й if убрать?
Где-то полсекунды убавляло.
http://ideone.com/rL1PXA
6.5с без проверки на 0 (иначе при нуле выдает 4) и 7.5с с ней.
Но главное что я убрал загрузку больших констант и FPU-вычитание.
А всё можно свести к очевидному и интуитивно понятному коду:
http://ideone.com/Swd4TW
Авотхуй (благо на x86_64 SSE есть всегда и подразумевается даже без -march/-mtune).
Плохо, негодно задрочили.
Я в принципе так и думал.
Может до ночи чего еще придумаю. Мы ведь еще всякие таблицы не пробовали - а это сильный кандидат.
Начнем:0m10.235s
P.S. Хотя в тех же контроллерах, где 2кб флеша, 128 байт оперативки и 20МГц еще есть шанс поебать байты...
Я бы сделал табличку на 64К, или выпилил ifы нахер.
return (x & 0x0000FF00)? first_bit[x >> 8] + 8 : first_bit[x];
fix
Тогда обсуждение затрагивало бы тему формирования этой таблички 🙂
Алгоритм должен быть таким чтоб я мог пользоваться им в жабе, жс, питоне и остальных языках.
Хотя машине Борманда верить нельзя - у меня когда-то ifы оказались самым быстрым что я смог придумать, но попробуем без них.
http://ideone.com/scwkXl
Трейдофф между скоростью, читабельностью, краткостью и портабельностью (на другие языки и размеры чисел).
http://ideone.com/luUZxM
До 64К - правильный.
http://ideone.com/XsIR3q
а 2 не проще было написать?
return (shift!=2) ? ln1(x,shift>>1,n): n+(x>>1);
fix