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 бит у нас есть достаточно места, чтобы построить пять "полигонов" из шести бит каждый, разделенных между собой разрядами-ноликами. Первое умножение помещает в каждый "полигон" копию верхних шести бит исходного байта. Затем константа для сложения подобрана так, что она добавляет всего одну единицу в каждом "полигоне", в разных разрядах; и таким образом по тому, выведет ли это сложение единицу в разделяющий разряд перед этим "полигоном", можно судить, начинается ли данный "полигон" с цепочки единиц такой-то длины. Наконец, третья строка удаляет из результата все, кроме этих разделяющих разрядов, в некоторых из которых теперь есть единицы, и сдвигает/умножает их так, что старший "полигон" накапливает их количество... дальше просто.

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