еще одна разгадка

[avva]

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

Итак, ответ на загадку: что делает функция

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

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

Многие заметили, что по сути дела функция считает число единиц в двоичном представлении, слева и до первого нуля; но не заметили, что когда старший бит 0, она возвращает вопреки этому описанию 1, а не 0. Это именно то, что нужно для UTF-8. Другие комментаторы заметили это и правильно описали, но не догадались (или не знали) про UTF-8. Наконец, немало было и правильных ответов.

Для того, чтобы понять, "как это работает", вам нужно выразить две большие константы из функции в двоичной системе, и посмотреть, что происходит во время умножений. Если вкратце, то внутри 64 бит у нас есть достаточно места, чтобы построить пять "полигонов" из шести бит каждый, разделенных между собой разрядами-ноликами. Первое умножение помещает в каждый "полигон" копию верхних шести бит исходного байта. Затем константа для сложения подобрана так, что она добавляет всего одну единицу в каждом "полигоне", в разных разрядах; и таким образом по тому, выведет ли это сложение единицу в разделяющий разряд перед этим "полигоном", можно судить, начинается ли данный "полигон" с цепочки единиц такой-то длины. Наконец, третья строка удаляет из результата все, кроме этих разделяющих разрядов, в некоторых из которых теперь есть единицы, и сдвигает/умножает их так, что старший "полигон" накапливает их количество... дальше просто.

Мне понравилась эта задача как раз тем, что она требует одновременно и математического подхода, и определенных практических знаний.

Comments

Оффтоп-задача

[(Anonymous)]

Кстати, есть вот такая задачка (кажется, интервьюшная), которую я не знаю, как решать. Может, вы её знаете или сможете решить.
Имеется связный список, каждый элемент которого снабжён дополнительным указателем на произвольный элемент этого же списка. Требуется всю эту структуру скопировать в любое другое место.
Ограничения, кажется, такие: время – O(n), доп. память (сверх тех областей, откуда и куда копируем) – O(1). Операция new выполняется за константное время. Исходный список в процессе можно менять (скорее всего, в решении это придётся делать), но в конце он должен быть в первоначальном виде.
Я тривиально могу решить эту задачу при одном дополнительном ограничении на вход. Каком – пока не сообщаю, чтобы вы не застряли на нём так же, как я. А вот в общем виде – не получается. Если и у вас не получится при таких ограничениях, то интересны также решения при более слабых ограничениях – например, линейная память или сверхлинейное время (но не квадратичное, поскольку так можно и в лоб решить).

Re: Оффтоп-задача

[mkal.livejournal.com]

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

[(Anonymous)]

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

Re: Оффтоп-задача

[(Anonymous)]

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

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

Второй проход. Идем по списку-копии и заполняем поле доп. указателя: из поля данных берем оригинальный доп. указатель, по этому указателю находим элмент исходного списка, его доп. указатель указывает на соответсвующий ему элемент списка-копии.

Третий проход. Идем по исходному списку, по доп. указателю находим копию данного элемента, из него забираем (и восстанавливаем) оригинальный доп. указатель, в него копируем данные.

Re: Оффтоп-задача

[(Anonymous)]

А, можно и "чисто", без использования поля данных сделать.

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

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

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

P.S. Надеюсь, я понятно излагаю свои мысли.

[(Anonymous)]

Спасибо большое, я всё понял!

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