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

[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

[spamsink.livejournal.com]

Из общих сображений: полезная функция, которая игнорирует два младших бита в байте и возвращает от 1 до не очень много...

Оно, конечно, забавно, но return 1 + (c >= 0xc0) + (c >= 0xe0) + (c >= 0xf0) + (c >= 0xf8) + (c >= 0xfc); компилируется в basic block из 18 параллелизуемых однотактных команд (cmp-seta-add ...), а два зависимых imul в загадке - это уже как минимум 20 тактов.

[spamsink.livejournal.com]

Если бы при этом он еще и правильный был...

[akuklev.livejournal.com]

Ошибку со сдвигом я комментом ниже уже починил. Я ещё где-то стормозил?

[spamsink.livejournal.com]

И этот тоже неправильный.

[spamsink.livejournal.com]

1. Если переменная меньше 128, вернуть 1
2. Если переменная меньше 64, вернуть 2

Что, простите?

[spamsink.livejournal.com]

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

[akuklev.livejournal.com]

В самом деле стормозил.

[amarao-san.livejournal.com]

Э... Оно понимает только двухбайтные последовательности в UTF-8? Я думал, что там бывают и более длинные... (правда, не знаю, как они кодируются).

[jerom.livejournal.com]

Длина задаётся первыми битами первого байта, эта функция детектит вплоть до 4 байт utf8. Пяти и 6-ти байтовые не ловит.

[oblomov-jerusal.livejournal.com]

Ловит.

[ilya-dogolazky.livejournal.com]

решили мою задачку по арифметике (там где-то в каментах) ?

[avva.livejournal.com]

А, я не понял, что вы предлагаете решить :) я ее знал.

[ilya-dogolazky.livejournal.com]

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

[avva.livejournal.com]

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

[(Anonymous)]

unsigned char __fastcall skip_len(unsigned char c) {
	__asm {
		not cl
		or cl, 1
		bsr al, cl
		mov cl, al
		inc cl
		shr cl, 3
		sub al, cl
		sub al, 7
		neg al
	}
}

[blacklion.livejournal.com]

Что на спарке и арме делать будем? А на MIPS'е? А на PowerPC?

ага, ошибся

[jerom.livejournal.com]

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

[(Anonymous)]

Так и знал, что кто-нибудь сумничает про переносимость.

Ничего, что из трех компиляторов, которыми я пользуюсь постоянно, два просто отказываются компилировать код из поста avva, поскольку для него требуется 64-битная арифметика? А тот компилятор, который соглашается, все равно генерит 32-битный код (потому что целевая архитектура такая - как и упомянутый вами ARM, кстати), и умножение 64-битных целых там делается так, что "наивное" решение с циклом и то работало бы быстрее?

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

[vodz.livejournal.com]

Это совершенно необходимая функция для работы с юникодным текстом в UTF-8

Вот только заюзать сложно. Ибо первым делом обычно переводим в wchar_t с проверкой на валидность входной последовательности, а потом уже работаем не с исходной строкой. Особенно, если надо двигаться и назад.

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

[(Anonymous)]

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

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

[mkal.livejournal.com]

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

[(Anonymous)]

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

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

[(Anonymous)]

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

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

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

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

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

[(Anonymous)]

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

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

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

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

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

[(Anonymous)]

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

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