- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
#include studio.h
main()
{
uint16 final,num;
printf(“enetr the unsigned integer 16bit number “);
scanf(“%d”, &num);
final= numbitset(num);
printf(“%d”, final);
}
unit16 numbitset( unit16 x)
{
int i, j,result, total=0;
uint16 no,modify
for(i=1;i<=4;i++)
{
j=pow(10,i);
no= (x%(j))>>(i-1)*4;
if(no==0)
{
result=0;
}
else if(no==1)
{
result=1;
}
else if(no==2)
{
result=1;
}
else if(no==3)
{
result=2;
}
else
{
result = othernum(no/4)+othernum(no%4);
}
total = total+result;
}
}
uint16 othernum( uint16 y)
{
switch(y)
{
case 0:
return(0);
break;
case 1:
return(1);
break;
case 2:
return(1);
break;
case 3:
return(2);
break;
default:
return;
break;
}
}
Посчитать количество значащиз битов в 16ти разрядном целом. Реальный тест на собеседовании дал такой вот результат. Угадайте откуда кандидат :)
Follow us!
Битоебы-битоебики...
> 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