Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 25 comments