еще одна загадка для программистов
Mar. 7th, 2011 11:10 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(эта запись может быть интересна лишь программистам и сочувствующим)
Как и в прошлой загадке, нужно сказать, что делает функция на C. На мой взгляд, она заметно сложнее предыдущей.
Эта функция выполняет некую полезную работу, которую нередко приходится выполнять в настоящих программах или библиотеках. Если вы разобрались в том, что фунцкия делает "буквально", но не понимаете, зачем это нужно, то это не полный ответ на вопрос (хотя тоже можете написать, конечно). Желательно ответить на вопрос, не запуская код; если вы запустили все же, укажите это в своем ответе, пожалуйста.
Комментарии скрываются. Автор этой загадки - мой коллега Дэвид Тернер (David Turner), которого я уже упоминал в записи про предыдущую загадку.
Update (6 часов спустя): только что пришел первый полный ответ, от![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
type_o_graph. Есть также несколько ответов, которые правильно описывают, что функция делает "буквально", но не объясняют или неправильно объясняют, зачем это нужно.
Update: вот правильный ответ. Раскрываю все комментарии к этой записи. Спасибо всем за попытки и ответы!
Как и в прошлой загадке, нужно сказать, что делает функция на C. На мой взгляд, она заметно сложнее предыдущей.
Эта функция выполняет некую полезную работу, которую нередко приходится выполнять в настоящих программах или библиотеках. Если вы разобрались в том, что фунцкия делает "буквально", но не понимаете, зачем это нужно, то это не полный ответ на вопрос (хотя тоже можете написать, конечно). Желательно ответить на вопрос, не запуская код; если вы запустили все же, укажите это в своем ответе, пожалуйста.
Комментарии скрываются. Автор этой загадки - мой коллега Дэвид Тернер (David Turner), которого я уже упоминал в записи про предыдущую загадку.
int func(unsigned char c)
{
const uint64_t MULT= 270549121;
uint64_t magic = (c >> 2) * MULT + 272696336;
magic = (((magic >> 6) & MULT)*MULT) >> 28;
return 1 + (magic & 7);
}
Update (6 часов спустя): только что пришел первый полный ответ, от
type_o_graph. Есть также несколько ответов, которые правильно описывают, что функция делает "буквально", но не объясняют или неправильно объясняют, зачем это нужно.Update: вот правильный ответ. Раскрываю все комментарии к этой записи. Спасибо всем за попытки и ответы!
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-03-07 09:23 am (UTC)no subject
Date: 2011-03-07 10:11 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2011-03-07 09:38 am (UTC)no subject
Date: 2011-03-07 09:49 am (UTC)no subject
Date: 2011-03-07 09:50 am (UTC)no subject
Date: 2011-03-07 09:59 am (UTC)Код запускал.
no subject
Date: 2011-03-07 10:52 am (UTC)для бинарного представления числа с
считает количество единиц с начала,
если их не больше шести и не меньше двух.
В общем, делает такое:
111111xx -> 6
111110xx -> 5
11110xxx -> 4
1110xxxx -> 3
110xxxxx -> 2
xxxxxxxx -> 1
Зачем - не могу пока понять.
no subject
Date: 2011-03-07 10:56 am (UTC)зачем нужно - фиг знает, немного похоже на выбор уровня в скип-листе, но эти два старших бита портят картину. Наверное, что-то другое, где нужно похожее распределение.
no subject
Date: 2011-03-07 11:12 am (UTC)Тогда на экзамене я чувствовал себя гуру и гением.
Сейчас я чувствую себя дегенератом (-:
no subject
Date: 2011-03-07 11:30 am (UTC)no subject
Date: 2011-03-07 11:51 am (UTC)Программу не запускал - считал в общем виде на бумажке, пару раз прогнал тестовые примеры на калькуляторе, нашел косяк в своих расчетах.
А, ещё использовал калькулятор, чтобы перевести константы в двоичное представление. :)
no subject
Date: 2011-03-07 12:23 pm (UTC)Доказать, что нижеследующая знаменитая функция из фортунок действительно вычисляет то, что она вычисляет
inline int n_bits_64(uint64_t x)
{
x = (x&0x5555555555555555LL) + (((x&0xAAAAAAAAAAAAAAAALL)>>1)) ;
x = (x&0x3333333333333333LL) + (((x&0xCCCCCCCCCCCCCCCCLL)>>2)) ;
x = (x&0x0F0F0F0F0F0F0F0FLL) + (((x&0xF0F0F0F0F0F0F0F0LL)>>4)) ;
x = (x&0x00FF00FF00FF00FFLL) + (((x&0xFF00FF00FF00FF00LL)>>8)) ;
return (int)(x%255) ;
}
no subject
Date: 2011-03-09 06:34 am (UTC)clz(~x)(только константы ещё на пол-байта длиннее наверно были).no subject
Date: 2011-03-07 12:29 pm (UTC)no subject
Date: 2011-03-07 12:34 pm (UTC)Программу не запускал. Предыдущую задачу понял, что делает, не догадался, зачем.
no subject
Date: 2011-03-07 01:51 pm (UTC)no subject
Date: 2011-03-07 02:13 pm (UTC)no subject
Date: 2011-03-07 02:22 pm (UTC)Вот только не совсем понятно зачем возвращать int а не uchar и зачем прибавлять единичку а не интерпретировать значение как количество оставшихся байт.
no subject
Date: 2011-03-07 02:43 pm (UTC)no subject
Date: 2011-03-07 03:05 pm (UTC)no subject
Date: 2011-03-07 03:30 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2011-03-07 03:32 pm (UTC)no subject
Date: 2011-03-07 03:33 pm (UTC)no subject
Date: 2011-03-07 03:58 pm (UTC)no subject
Date: 2011-03-07 04:56 pm (UTC)no subject
Date: 2011-03-07 06:06 pm (UTC)Без компилятора приходится вручную...
Date: 2011-03-07 06:10 pm (UTC)По-моему, код делает примерно следующее:
return (C >= 0xF8) + (C >= 0xF0) + (C >= 0xE0) + (C >= 0xC0) + 1;
Зачем, сказать труднее... Считает сколько верхних битов, от одного до шести...
Ой, погодите, а это не длина Юникодового символа? Очень похоже. Сейчас посмотрю... Ага, вроде да. UTF-8 Bit Distribution.
С другой стороны, если я правильно разобрал код, шестибайтовые последовательности он будет считать пятибайтовыми. И те и другие запрещены, но всё-таки... Так что может, я и не угадал.
Злой ваш коллега! Не добрый!
no subject
Date: 2011-03-07 07:27 pm (UTC):)