еще одна загадка для программистов

[avva]

(эта запись может быть интересна лишь программистам и сочувствующим)

Как и в прошлой загадке, нужно сказать, что делает функция на 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: вот правильный ответ. Раскрываю все комментарии к этой записи. Спасибо всем за попытки и ответы!

Comments

[blueher.livejournal.com]

Я так понимаю что функция не претендует на оптимальность? Любую "чистую" функцию char->int можно выразить через таблицу размером 1Кб. В нынешние времена это копейка даже для самого мелкого процессора.

[blueher.livejournal.com]

Вообще похоже на что-то типа CRC6

[blueher.livejournal.com]

Считает единички в старших 5 разрядах числа?

[ya-doran.livejournal.com]

Количество установленных бит со 2-го по 6-й бит в байте?

[anton tupy (from livejournal.com)]

Количество единиц до первого нуля в двоичном представлении.
Код запускал.

[avva.livejournal.com]

Не претендует.

[r419.livejournal.com]

Прикинул на бумажке,
для бинарного представления числа с
считает количество единиц с начала,
если их не больше шести и не меньше двух.
В общем, делает такое:
111111xx -> 6
111110xx -> 5
11110xxx -> 4
1110xxxx -> 3
110xxxxx -> 2
xxxxxxxx -> 1
Зачем - не могу пока понять.

[unbe.livejournal.com]

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

[gaius-julius.livejournal.com]

В (не таком уж далёком) прошлом, я сдавал экзамен, частью которого была пачка карточек с напечатанными на них C-функциями на четыре-пять строк. Вопрос был тот же - "что делает?"

Тогда на экзамене я чувствовал себя гуру и гением.

Сейчас я чувствую себя дегенератом (-:

[alexey boyko (from livejournal.com)]

предполагаю, что генерирует следующее псевдослучайное число. правда seed всего 8 бит получается.

[fenikso.livejournal.com]

Возвращает длину непрерывной цепочки из единичных битов, считая со старшего? (и не учитывая младшие два бита)

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

А, ещё использовал калькулятор, чтобы перевести константы в двоичное представление. :)

[ilya-dogolazky.livejournal.com]

У меня получилось, что-то такое int cc=c>>2; return 1+(cc+16>=64)+(cc+8>=64)+(cc+4>=64)+(cc+2>=64)+(cc+1>=64). Наверное где-то ошибка, ибо такую формулу наверняка можно и проще вычислить, без длинной арифметики и умножений.

[ilya-dogolazky.livejournal.com]

Мне эта загадка напомнила такую задачу (по арифметике, не по программированию):
Доказать, что нижеследующая знаменитая функция из фортунок действительно вычисляет то, что она вычисляет

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) ;
}

[fourdman.livejournal.com]

Буквально она считает MAX(6, MIN(1, к-во подряд стоящих в начале единиц в двоичном виде с)). Ответ получил на бумажке, запустил только чтобы проверить. Но вот зачем на практике такая функция — ума не приложу пока.

[mgar.livejournal.com]

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

Программу не запускал. Предыдущую задачу понял, что делает, не догадался, зачем.

[dmzlj.livejournal.com]

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

[(Anonymous)]

Вычисляет, сколько единиц идут подряд начиная со седьмого бита вниз до третьего включительно, предполагая, что в восьмом бите стоит 0 и добавляет 1. Может использоваться в алгоритмах компрессии.

[oblomov-jerusal.livejournal.com]

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

[type-o-graph.livejournal.com]

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

Вот только не совсем понятно зачем возвращать int а не uchar и зачем прибавлять единичку а не интерпретировать значение как количество оставшихся байт.

[oblomov-jerusal.livejournal.com]

В ответе выше предполагается, что бит 8 байта равен 0. Если бит 8 равен 1, посчитается 6 минус длина последовательности. Если я неясно выразился, в обеих случаях последовательность должна начинаться с бита 7.

[fenikso.livejournal.com]

Хм, "нужно" это может быть для кучи разных случаев - например для алгоритмов сжатия. domain-specific, имхо.

[avva.livejournal.com]

Есть более специфичная и идеально подходящая функция.

[avva.livejournal.com]

Нет, все верно вышло. Арифметика в основном для прикола и усложнения, я ж не сказал, что это реальный код - это именно загадка.

[(Anonymous)]

что то типа MD5?

[ilya-dogolazky.livejournal.com]

И что дальше, надо теперь угадать зачем это в "реальной жызни"(тм) или это уже и есть правильный ответ ?