Двоично-троичная битовая магия

    Существует классическая задача для собеседований, часто формулируемая следующим образом:


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

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


    Предлагаю поразмыслить над другой вариацией данной задачи. Что, если все элементы, кроме искомого, будут присутствовать в массиве не парами, а тройками? Насколько при этом усложнится решение и останется ли оно линейным?




    Попробуем решать по аналогии. $xor$ подошёл из-за того, что обладает двумя замечательными свойствами (помимо ассоциативности и коммутативности, естественно):


    1. $\forall a: a\oplus 0 = a$
    2. $\forall a: a\oplus a = 0$

    Символ $\oplus$ в данной записи — это математическое обозначение операции $xor$. Предположим на минуту, что существует операция $xor_3$, удовлетворяющая похожим свойствам:


    1. $\forall a: a\oplus_3 0 = a$
    2. $\forall a: a\oplus_3 a\oplus_3 a = 0$

    В этом случае $xor_3$-сумма всех элементов массива дала бы правильный ответ. Поэтому займёмся построением такой функции.


    Все мы привыкли воспринимать $xor$ как "побитовое исключающее или" (тут даже название выбрано подходящее — eXclusive OR), но я предлагаю взглянуть на эту операцию под немного другим углом — как на "поразрядное сложение по модулю 2". Не зря ведь символ $\oplus$ так похож на плюс.


    Вроде бы поменяли только название, а мысли появляются уже совсем другие. Битовое представление целых чисел — это просто представление в двоичной позиционной системе счисления. И если каждый бит воспринимать как число 0 или 1, то их $xor$ — это в точности сложение по модулю два.


    Следуя подобным рассуждениям, в качестве $xor_3$ можно взять поразрядное сложение по модулю 3 в троичной системе счисления. Оно будет удовлетворять всем нужным свойствам, осталось только написать реализацию.




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


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


    $47_{10} = 101111_{2} = 1202_{3} = 01\:10\:00\:10\:_{2/3}$


    Понятное дело, для хранения обычного беззнакового 32-битного целого числа потребуется больший объём данных. А именно, $2\cdot\lceil{\log_3{(2^{32}-1)}}\rceil = 2\cdot\lceil{20{,}189752114}\rceil = 42$ бит информации, что легко войдёт в 64-битный формат типа long.


    Реализация конвертирования из двоичного в двоично-троичный формат довольно топорная — обычный цикл с чтением/записью нужных бит по смещению:


    static long to3(int n) {
        long ln = ((long) n) & 0xFFFFFFFFL;
        long result = 0L;
        for (int offset = 0; ln != 0L; ln /= 3, offset += 2) {
            result |= (ln % 3) << offset;
        }
        return result;
    }

    static int from3(long n) {
        long result = 0L;
        for (int offset = 40; offset >= 0; offset -= 2) {
            result = (result * 3) + ((n >> offset) & 0x3L);
        }
        return (int) result;
    }

    Что же касается операции $xor_3$, то для неё тоже доступна простая реализация:


    static long xor3(long a, long b) {
        long result = 0L;
        for (int offset = 0; offset < 42; offset += 2) {
            long digit = ((a >> offset) & 0x3L) + ((b >> offset) & 0x3L);
            result |= (digit % 3) << offset;
        }
        return result;
    }

    Её уже можно тестировать (и она даже работает!), но я ей не доволен.


    Понимаете, "битовые" функции обычно выглядят так (это метод из класса Long):


    public static long reverse(long i) {
        i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;
        i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
        i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;
        i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
        i = (i << 48) | ((i & 0xffff0000L) << 16) |
            ((i >>> 16) & 0xffff0000L) | (i >>> 48);
        return i;
    }

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


    Именно поэтому я перепишу реализацию xor3, избавившись от циклов и условий:


    static long xor3(long a, long b) {
        long o = a & b & 0xAAAAAAAAAAAAAAAAL;
        long c = (a + b) - (o << 1);
        long m = c & (c >>> 1) & 0x5555555555555555L;
        return (c & ~(m | m << 1)) | (o >>> 1);
    }

    Далее последуют объяснения, что вообще происходит и как люди до такого доходят.




    Итак, стоит задача одновременной обработки 21-й пары бит (можно и больше), руководствуясь следующими правилами:


    $$display$$\begin{array}{|} \hline \oplus_3&00&01&10\\ \hline 00&00&01&10\\ \hline 01&01&10&00\\ \hline 10&10&00&01\\ \hline \end{array}$$display$$


    Пара бит "11" просто не может попасться, поскольку она соответствовала бы разряду со значением 3, которое в троичной системе счисления не встречается.


    Что будет, если просто сложить аргументы a и b? Данная операция сохранит "локальность" пар бит почти для всех вариантов входных данных. Единственное исключение — сумма 10 и 10, которая при переполнении залезет на территорию соседней пары.


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


    long o = a & b & 0xAAAAAAAAAAAAAAAAL;

    Константа, на первый взгляд непонятная, в двоичном представлении выглядит предельно просто: 0b101010...10. В ней единицы стоят через одну, пропуская самый младший бит. Это помогает отрезать от a & b всё то, что нас сейчас не интересует. Сдвинув o на 1 бит влево, мы как раз получим все биты переполнения, появляющиеся при сложении


    long c = (a + b) - (o << 1);

    Переменная c хранит значение, очень близкое к результату, но с ошибками:


    1. В ней есть пары бит 11, которые по модулю 3 должны быть заменены на 00.
    2. Все результаты сложения 10 и 10 равны 00, а должны быть 01.

    Исправим эти ошибки по порядку. Найти пары бит, равные 11, не сложно, мы уже делали что-то очень похожее.


    long m = c & (c >>> 1) & 0x5555555555555555L;

    Магическая константа здесь — это не что иное, как ~0xAAAAAAAAAAAAAAAAL, то есть число, в котором единичные биты стоят через один, начиная с самого младшего. Тем самым в значении m единичные биты будут стоять младшими битами пар, соответствующих парам 11 в значении c.


    Выражение m | m << 1 представляет эти пары целиком. Избавиться от них теперь можно двумя способами. Какой выбирать — дело вкуса:


    • c -= m | m << 1;
    • c &= ~(m | m << 1);

    Разобраться с последней ошибкой проще простого: нужно добавить биты там, где мы складывали 10 и 10. А равны они в точности o >>> 1. Поэтому итоговый код выглядит именно так:


    return (c & ~(m | m << 1)) | (o >>> 1);



    Но это ещё не всё. Избавившись от циклов и условий в одной из функций, я совсем позабыл о циклах и условиях в двух оставшихся — to3 и from3. Можно ли их оптимизировать подобным образом?


    Смотря как посмотреть. Если хочется по-честному переводить в троичную систему счисления, то придётся делить/умножать на 3, тут никуда не деться. НО ведь можно заменить саму операцию на более оптимальную: сопоставлять 32-х разрядному двоичному числу другое 32-х разрядное троичное число так, чтобы разным двоичным числам соответствовали разные троичные (такие отображения называются инъективными), при этом значения двоичного и троичного чисел совпадать не обязаны.


    Например, прямое отображение двоичных разрядов в троичные ($11001_2 \rightarrow 11001_3$). Однако здесь реализация будет всё такой же неудобной. Самый простой вариант, который приходит мне на ум — это поместить чётные биты int в одну половину значения типа long, а нечётные — в другую. Код станет элементарным:


    static long to3(int n) {
        long ln = ((long) n) & 0xFFFFFFFFL;
        return (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32;
    }
    
    static int from3(long n) {
        return (int) (n | n >>> 32);
    }

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


    static int find(int[] v) {
        long res = 0L;
        for (int n : v) {
            long ln = ((long) n) & 0xFFFFFFFFL;
            res = xor3(res, (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32);
        }
        return (int) (res | res >>> 32);
    }

    Как видите, не очень сложно. Я бы даже сказал, что код выглядит красивым (хотя и нуждается в пояснениях). Надеюсь, что вы разделяете моё мнение.


    Спасибо за внимание!

    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну, и что?
    Реклама
    Комментарии 20
    • +5

      Тех, кто предлагает такие задачи на собеседовании надо сразу выгонять.

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

        к примеру, последние пол-года сижу на джине, работу искать — не ищу, есть чем заниматься, но из всей адской массы HR-ов и работодателей, только ОДИН задал технические вопросы, а тестового задания так и вовсе никто не прислал )… в осадок выпал недавно, получив предложение HRа на собеседование к компании в которой работаю много лет )…

        не представляю, с какими сложностями и бредом сталкиваются ребята, которые действительно ищут сегодня хорошую, достойно оплачиваемую работу…
        • 0
          На собеседование-то сходили в итоге?
        • +2

          Вы про какую? Та, классическая, которая с парой — нормальная задача.


          А про xor3 автор и не предлагает (это действительно была бы жесть).

          • +1

            А чего жесть? Задача интересная, если не извращаться как автор а решать в лоб — то решение в десяток строк:


            uint_fast64_t xor3(uint_fast64_t a,  uint_fast64_t b)  {
              uint_fast64_t c=0, m=1;
              while (a>0 && b>0) {
                c += m * ((a%3+b%3) % 3);
                a /= 3;
                b /= 3;
                m *= 3;
              }
              c += m * (a + b);
              return c;
            }

            Хотя бы шанс что собеседуемый такую задачу не видел повыше :)

            • 0
              И вас бы приняли, а автора могут и не взять, поскольку long далеко не всегда 64-х битный.
              • +1
                Позвольте не согласиться =) Я на Java писал, там с этим строго.
                • +1
                  Точно, это у меня уже профдеформация в сторону C++.
              • 0

                Я имел ввиду постановку задачи как классическую, только с заменой пар на тройки, без каких-либо уточнений. В условиях собеседования "с маркером у доски" не так-то просто быстро сообразить.


                Хотя если собеседование в чем-то типа codility, тогда нормально, там хоть обстановка поспокойнее и можно минут 5 подумать. :-)

                • 0

                  Пожалуй с нуля и с наскока на интервью не каждый решит. Если сначала дать с парами, а потом с тройками, то имхо нормально.

            • 0
              Поясните пожалуйста, почему? Мне эта задача показалась очень красивой и вполне подходящей для собеседования.
              • 0
                Никогда не понимал зачем на собеседованиях давать головоломки. Разве что вы нанимаете человека для решениях головомок.

                Лично меня волнует насколько хорошо человек понимает предметную область и общие подходы к разработке. Поэтому я например на собеседованиях задаю вопросы именно такого плана: «А почему в атомарном контексте в ядре нельзя использовать блокирующие вызовы? А что такое вообще блокирующий вызов, кстати? А как можно попасть в атомарный контекст? А как мне синхронизировать в атомарном контексте? У вас был принят code-review на прошлом проекте? А какие инструменты вы использовали? А как решали спорные ситуации?»

                Это намного больше расскажет о том, подходит ли человек, чем умение отмерять время сжигая отрезки веревок разной длины.
                • 0
                  Такой подход оправдан, если Вы нанимаете физика-ядерщика, или иного узкого специалиста, с достаточно статичными компетенциями. Для программистов, на мой взгляд, живость ума и способность решать нетривиальные задачи важнее перманентного удержания в голове кучи справочной информации, которая элементарно гуглится и усваивается за считанные минуты.
                  • 0
                    Так я же не спрашиваю справочную информацию. Я спрашиваю базовые вещи для любого ядерного разработчика. Я как раз пытаюсь увидеть что человек понимает тему, а не просто зазубрил учебник.
                    Как раз понимание того как все работает, зачем было принято то или иное архитектурное решение и позволит решать нетривиальные задачи.
                    Мне не нужен человек, который просто умеет копировать код с SO и вызубрил решение тех двух десятков логических задач, которые спрашивают на каждом втором собеседовании. Мне нужен человек который может пояснить почему написанный код был написан именно так, сможет привести альтернативные решения и объяснить их достоинства и недостатки.
            • 0
              Меня такой код восхищает, потому что он наверняка супер оптимален и с первого взгляда совершенно непонятно, как работает. От подобных алгоритмов я получаю особое удовольствие.

              А я ровно наоборот. Не скажу, что в данном случае это плохо, всё-таки, как я понял, библиотечная реализация, которая, вообще говоря, критична к производительности. Но хотелось бы комментарий «как» и «почему так», хотя бы название алгоритма/приёма, если это какая-то классика. Вот опечатается коллега на один символ в реализации, а мне придёт бага — и как мне понять, есть ли здесь ошибка, где конкретно и как проявляется?
              • +1

                Если посмотреть на подобный код в библиотечных реализациях в том же классе Long, то там каждый такой метод снабжён комментарием вида // HD, Figure 7-1 (согласно документации это ссылка на главу книги с подробным описанием).
                Данный конкретный способ был взят из головы. Если и есть классическое название, то я с ним не знаком.

              • +1
                У исходной задачи есть превосходная вариация:
                Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза, и только ДВА числа не имеют пары. Необходимо предложить алгоритм, который за ФИКСИРОВАННОЕ количество проходов по массиву и используемой памяти определяет оба этих числа, не имеющих пары.
                • +1

                  Вариация действительно превосходная, пришлось хорошо подумать, чтобы решить. Я снова предполагаю, что массив заполнен 32-битными целыми числами, но решение масштабируется на числа любой длины. Исхожу из предположения, что "фиксированное количество памяти" в данном случае можно расценить как "могу позволить себе 33 переменных".
                  Для начала понадобится один проход по массиву:


                  • нужно посчитать xor всего массива;
                  • вместе с ним нужно посчитать xor величин, равных конъюнкции элементов массива с их циклическими сдвигами на 1 (т.е. x & ((x >>> 1) | (x << 31)), где x — элемент массива).

                  Дальше идёт хитрая часть вычислений. Раз неизвестных чисел два и они различны, то есть как минимум один бит, который у данных чисел будет разным (ну это очевидно).
                  Возьмём бит a1 для первого числа и b1 для второго (с той же позиции). Тогда наши два вычисления дают следующие результаты:


                  • c1 = a1 XOR b1;
                  • c2 = a2 XOR b2 (соседние биты для a1 и b1);
                  • d = (a1 & a2) XOR (b1 & b2).

                  Сразу стоит оговориться, что поменяв местами значения a и b, решением эта пара быть не перестанет. Значит в какой-то момент нам просто нужно будет случайным образом решить, что есть a, а что есть b. Так, для порядка.
                  Учитывая данную симметрию, проследим, какими могут быть значения c1, c2 и d:


                  a1 a2 b1 b2 | c1 c2 d
                  0  0  0  0  | 0  0  0
                  0  0  0  1  | 0  1  0
                  0  0  1  0  | 1  0  0
                  0  0  1  1  | 1  1  1
                  0  1  0  1  | 0  0  0
                  0  1  1  0  | 1  1  0
                  0  1  1  1  | 1  0  1
                  1  0  1  0  | 0  0  0
                  1  0  1  1  | 0  1  1
                  1  1  1  1  | 0  0  0

                  В четырёх случаях из данного списка все значения c1, c2 и d оказались нулями — это именно те случаи, где a1 == b1 && a2 == b2, то есть нас они не интересуют. Для остальных случаев тройка {c1, c2, d} однозначно определяет значения {a1, a2, b1, b2}.


                  Дальше дело за малым — пара различных бит — это либо {a1, b1}, либо {a2, b2}. Без ограничения общности будем считать, что это {a1, b1}. Теперь мы в праве вычислить e = (a1 & a3) XOR (b1 & b3) (тут циклическое смещение на два) и т.д. для всех длин циклического смещения, достраивая полноценные значение a и b бит за битом.


                  Конечно, данное решение будет засчитано только если верно моё предположение о том, что разрядность чисел можно считать константой. Если это не так, то варианта получше у меня пока нет.

                  • +2
                    Совершенно верное решение! Есть и такая его вариация:
                    Используем 33 переменных и один проход по массиву.
                    В первую переменную вычисляем XOR элементов, где первый бит равен 1.
                    Во вторую переменную вычисляем XOR элементов, где второй бит равен 1.
                    … и так первые 32 переменные.
                    А в последнюю 33 переменную — общий XOR всех элементов.
                    По крайней мере одна из 32 переменных не будет равна общему XOR или нулю — это и есть одно из двух непарных чисел. Второе вычисляется по их общему XOR.
                    • 0
                      Ваш вариант гораздо проще понять.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое