Насколько хорош должен быть разносторонний программист для побитовых операций? [закрыто]

Недавно я просматривал некоторый код OpenJDK и нашел там несколько интригующих фрагментов кода, связанных с побитовыми операциями . Я даже задал вопрос об этом на StackOverflow.

Еще один пример, который иллюстрирует суть:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Этот код можно найти в классе Integer .

Я не могу не чувствовать себя глупо, когда я смотрю на это. Я пропустил один или два класса в колледже, или это не то, что я должен получить ? Я могу выполнять простые побитовые операции (например, ANDing, ORing, XORing, shift), но давай, как кто-то придумал код, подобный описанному выше?

Насколько хорош должен быть разносторонний программист для побитовых операций?

На стороне записки ... Что меня беспокоит то , что человек , который ответил на мой вопрос на StackOverflow ответил в течение нескольких минут. Если он мог сделать это, почему я просто смотрел как олень в свете фар?

Я бы сказал, что как хорошо развитый разработчик, вы должны понимать операторы и побитовые операции.

Итак, как минимум, вы должны быть в состоянии разобраться в приведенном выше коде, немного подумав.

Побитовые операции имеют тенденцию быть довольно низким уровнем, поэтому, если вы работаете на веб-сайтах и ​​в программном обеспечении LOB, вы вряд ли будете их использовать.

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

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

Если вы понимаете, как решать проблемы, такие как «определить, установлены ли биты 3 и 8», «очистить бит 5» или «найти целочисленное значение, представленное битами 7-12», у вас достаточно понимания побитовых операторов, чтобы проверить Can Ячейка Twiddle Bits в «хорошо округленном» контрольном списке.

То, что в вашем примере исходит от Hacker's Delight , компиляции высокопроизводительных алгоритмов для манипулирования небольшими битами данных, такими как целые числа. Кто бы ни написал этот код изначально, он не выплюнул его за пять минут; история, стоящая за этим, скорее всего, была связана с необходимостью быстрого, не имеющего ветвей способа подсчета битов, и у автора было время потратить время на разглядывание цепочек битов и поиск способа решения проблемы. Никто не поймет, как это работает с первого взгляда, если они не видели это раньше. Имея глубокое понимание побитовых основ и некоторое время, потраченное на эксперименты с кодом, вы, вероятно, сможете понять, как он выполняет то, что делает.

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

Пользователь, который ответил на ваш вопрос SO, возможно, видел проблему раньше или изучал хеширование. Напишите ему и спросите.

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

1143 i = i - ((i >>> 1) и 0x55555555);

Вы должны распознать битовую комбинацию 0x555 ... как чередующуюся битовую комбинацию 0101 0101 0101 и то, что операторы смещают ее на 1 бит (вправо), и это & ​​является операцией маскирования (и что означает маскирование).

1144 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

Снова шаблон, это 0011 0011 0011. Кроме того, на этот раз он сдвигает два и снова маскирует. смещение и маскирование следуют шаблону, который вы должны распознать ...

1145 i = (i + (i >>> 4)) & 0x0f0f0f0f;

картина затвердевает. На этот раз это 00001111 00001111 и, разумеется, на этот раз мы меняем его на 4. каждый раз мы сдвигаемся по размеру маски.

1148 return i & 0x3f;

другой битовый шаблон, 3f - это блок нулей, за которым следует больший блок из единиц.

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

Даже на языке более высокого уровня битовые шаблоны используются для хранения НАМНОГО больших объемов данных в небольших полях. Вот почему вы всегда видите предельные значения 127/8, 63/4 и 255/6 в играх, потому что вам нужно хранить столько вещей, что без упаковки полей вы будете вынуждены использовать целых десять раз количество памяти. (Ну, в конечном итоге, если бы вам нужно было хранить огромное количество логических значений в массиве, вы могли бы сэкономить 32-64-кратный объем памяти, как если бы вы не думали об этом - большинство языков реализуют логические значения как слово, которое часто будет 32-битным. Те, кто не чувствуют себя комфортно на этом уровне, будут сопротивляться возможности хранить подобные данные просто потому, что они боятся неизвестного.

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

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

Вы не должны чувствовать себя плохо, если ваша работа часто не совпадает с этими доменами. Я хорошо знаю побитовые операции, но в тех редких случаях, когда мне нужно написать GUI, я замедляю работу из-за всех причуд с макетами, взвешиванием и расширением, так что я уверен, что это вторая натура для других. Ваши сильные стороны там, где у вас больше всего опыта.

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

основные арифметические операции + - * / %могут быть поняты без необходимости понимать их, хотя это может быть полезно для микрооптимизации (хотя большую часть времени компилятор сможет позаботиться об этом за вас)

набор манипуляций с битами | & ~ ^ << >> >>>требует по крайней мере мимолетного понимания, чтобы их можно было использовать

однако большую часть времени вы будете использовать их только для передачи битовых флагов методу как ORобъединение и передача целого, а затем ANDизвлечение настроек более читабельно, чем передача нескольких (до 32) логических значений в длинном списке параметров и позволяет возможные флаги для изменения без изменения интерфейса

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

что касается фрагмента кода, он выполняет параллельный подсчет битов, что позволяет алгоритму работать O(log(n))там, где n - это число бит вместо наивного цикла, которыйO(n)

первый шаг труднее всего понять, но если вы начнете с установки, она должна заменить последовательности битов 0b00на 0b00, 0b01к 0b01, 0b10к 0b01и 0b11к 0b10ней, становится легче следовать

поэтому для первого шага, i - ((i >>> 1) & 0x55555555)если мы примем iравным, 0b00_01_10_11то результат этого должен быть0b00_01_01_10

(обратите внимание, что 0x5равно 0b0101)

если мы возьмем я = 0b00_01_10_11это означает, что 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01)есть то, 0b00_01_10_11 - 0b00_00_01_01что в свою очередь становится0b00_01_01_10

они могли бы сделать (i & 0x55555555) + ((i >>> 1) & 0x55555555)для того же результата, но это 1 дополнительная операция

следующие шаги в том же духе

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

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

Сколько навыков должен иметь программист, который не выполняет низкоуровневые вещи с помощью побитовой манипуляции? Достаточно, чтобы можно было сесть со строфой, которую вы вставили, и медленно прорабатывать ее, как головоломку или головоломку.

К тому же, я бы сказал, что программист встраиваемых систем должен понимать о http столько же, сколько веб-разработчик знает о побитовых манипуляциях. Другими словами, все в порядке, чтобы не быть умным в манипулировании битами, если вы не используете его все время.

Восторг хакера - это производная работа. Предком всего является HakMem с 1972 года. Http://w3.pppl.gov/~Hammett/work/2009/AIM-239-ocr.pdf

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

Насколько сложно интерпретировать побитовые операторы?

Я программирую встроенные системы. Я много тренировался с этим. Ваш связанный вопрос о хэш-картах с кодом

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

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

Важно проводить различие между чтением и пониманием кода. Я могу интерпретировать bitCountкод и прочитать, что он делает, но доказать, почему он работает или даже работает, потребуется минута. Есть разница между способностью читать код гладко и умением понимать, почему код такой, какой он есть. Некоторые алгоритмы просто сложны. « Что из hashкода» имело смысл, но комментарий объяснил, почему это делается. Не расстраивайтесь, если функцию, использующую побитовые операторы, трудно понять, они часто используются для выполнения сложных математических задач, которые были бы сложными независимо от формата.

Аналогия

Я привык к этому. Одна тема, к которой я не привык, это регулярные выражения. Я имею дело с ними время от времени на сценарии сборки, но никогда в повседневной работе разработчиков.

Я знаю, как использовать следующие элементы регулярного выражения:

• [] классы персонажей
• В *, .и +подстановочные знаки
• Начало строки ^и конец строки$
• Классы символов \ d, \ w и \ s
• Флаг / g

Этого достаточно для создания простых запросов, и многие из запросов, которые я вижу, не уходят далеко от этого.

Что-нибудь не в этом списке, я достаю шпаргалку. Все что угодно, кроме {}и ()- шпаргалки не хватит. Я достаточно знаю об этих парнях, чтобы знать, что мне понадобится доска, справочное руководство и, возможно, коллега. Вы можете упаковать несколько сумасшедших алгоритмов в несколько коротких строк регулярного выражения.

Чтобы разработать регулярное выражение, которое требует или предлагает что-либо, чего нет в моем списке известных элементов, я собираюсь перечислить все классы входных данных, которые я ожидаю распознать, и поместить их в набор тестов. Я собираюсь обработать регулярное выражение медленно и постепенно, с большим количеством прерывистых шагов, и зафиксировать эти шаги для контроля исходного кода и / или оставить их в комментарии, чтобы я мог понять, что должно было случиться позже, когда оно сломается. Если это в рабочем коде, я собираюсь сделать так, чтобы он был проверен кем-то с большим опытом.

Это где вы с побитовыми операторами?

Так ты хочешь быть хорошо округленным?

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

1. Умение легко читать и записывать общие операции.
   Для программиста приложений общие операции с побитовыми операторами включают основные операторы |и &для установки и сброса флагов. Это должно быть легко. Вы должны быть в состоянии читать и писать такие вещи, как

   open('file', O_WRONLY | O_APPEND | O_CREAT );
   // Use an OR operator ^ here and ^ here to set multiple flags
   

   без замедления (при условии, что вы знаете, что означают флаги ).

2. Быть способным читать более сложные операции с некоторой работой.
   Очень быстрый подсчет битов за O (log (n)) времени без веток, обеспечение того, что число коллизий в hashCodes может отличаться на ограниченную величину, и анализ адресов электронной почты , телефонных номеров или HTML с регулярным выражением - сложные проблемы. Для тех, кто не является экспертом в этих областях, имеет смысл обратиться к доске, поэтому неразумно начинать работать, чтобы понять.

3. Уметь писать сложные алгоритмы с большой работой.
   Если вы не эксперт, вы не должны ожидать, что сможете делать сложные и сложные вещи. Тем не менее, хороший программист должен быть в состоянии сделать это, работая над ним постоянно. Сделай этого достаточно, и ты скоро станешь экспертом :)

Если вы поступили в приличный университет, вы должны были пройти курс дискретной математики. Вы бы выучили двоичные, восьмеричные и шестнадцатеричные арифметические и логические элементы.

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

Как программист мобильных телефонов, мне приходилось иметь дело с такими вещами. Это довольно распространенная ситуация, когда на устройстве мало памяти или важна скорость передачи. В обоих случаях вы пытаетесь упаковать как можно больше информации в несколько байтов.

Я не припомню, чтобы побитовые операторы использовались через 5 лет или около того в PHP (может быть, это только я), а не через 10 лет или около того в программировании Windows, хотя некоторые вещи Windows более низкого уровня действительно собирают биты.

Вы говорите: «Я не могу не чувствовать себя глупо, когда смотрю на это». НЕ - злиться.

Вы только что встретили вывод ковбойского программиста.

Он ничего не знает о написании поддерживаемого кода? Я искренне надеюсь, что именно он должен вернуться к этому через год и попытаться вспомнить, что это значит.

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

Вот хорошее эмпирическое правило - в коде допускаются только «голые целые числа» 0 1 и 1. Все остальные числа должны быть #defines, cost, enums и т. Д., В зависимости от вашего языка.

Если бы эти 3 и 0x33333333 сказали что-то вроде NUM_WIDGET_SHIFT_BITS и WIDGET_READ_MASK, код стал бы легче читать.

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

Этот конкретный фрагмент кода взят прямо из книги « Хакерское наслаждение» , рисунок 5.2. Его онлайн в C (функция поп) здесь . Обратите внимание, что автор теперь рекомендует использовать обновленные версии: http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

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

Это также помогает переписать все шестнадцатеричные числа в двоичном виде, чтобы понять алгоритмы такого рода и проработать их в одном или двух тестовых случаях.

Объяснение на примере. Данные представляют собой последовательности битов. Давайте посчитаем биты в байте 01001101, имеющие следующие доступные операции: 1. Мы можем проверить значение последнего бита. 2. Мы можем изменить последовательность.

1. 01001101 -> последний байт равен 1, всего = 1. сдвиги
2. 10100110 -> последний байт равен 0, всего = 1. сдвиги
3. 01010011 -> последний байт равен 1, всего = 2. сдвиги
4. 10101001 -> последний байт равен 1, всего = 3. сдвиги
5. 11010100 -> последний байт равен 0, всего = 3. сдвиги
6. 01101010 -> последний байт равен 0, всего = 3. сдвиги
7. 00110101 -> последний байт равен 1, всего = 4. сдвиги
8. 10011010 -> последний байт равен 0, всего = 4. сдвиги

Наш ответ: 4.

Это было не сложно, не так ли? Большое дело с побитовыми операциями заключается в том, что мы можем делать ограниченные вещи. Мы не можем получить доступ немного напрямую. Но мы можем, например, знать значение последнего бита, сравнивая его с MASK 00000001, и мы можем сделать каждый бит последним с операциями сдвига. Конечно, результирующий алгоритм будет выглядеть страшно для тех, кто не привык. Ничего общего с интеллектом.

Я бы не сказал, что вам это нужно, если только ваша работа не связана с:

• Аудио обработка
• Обработка видео
• Графика
• Сеть (особенно там, где важен размер пакета)
• Огромное количество данных

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

Помимо этих областей, я бы счел это большим плюсом, если бы разработчик / старший разработчик мог продемонстрировать сдвиг битов и использование | & и ^, поскольку это показывает интерес к профессии, которая, как вы могли бы сказать, приводит к более стабильному и надежному коду.

Что касается «не получения» метода с первого взгляда, как уже упоминалось, вам нужно объяснить, что он делает, и некоторые сведения. Я бы не сказал, что это связано с интеллектом, но насколько вы знакомы с повседневной работой с шестнадцатеричной системой и распознаванием проблем, которые могут решить определенные шаблоны.