Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 33

Часть VIII. Вопросы собеседования
Концепции и алгоритмы. Вопросы и советы
5. Поразрядная обработка

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

Расчеты на бумаге

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

Не забудьте некоторые обозначения: ^ соответствует операции XOR, а ~ – операции NOT. Предположим, что мы работаем с четырехбитными числами. Задания из третьей колонки можно решить или использовать некоторые приведенные ниже «хитрости».

Решение: строка 1 (1θθθ, 1111, 11θθ); строка 2 (θ1θ1, 1θθ1, 11θθ); строка 3 (θθ11, θθ11, 1111); строка 4 (θθ1θ, 1θθθ, 1θθθ).

Трюки для третьей колонки:

• 0110+0110 = 0110*2, что эквивалентно смешению 0110 влево на 1.

• Поскольку 0100=4, можно умножить θθ11 на 4. Умножение на 2ⁿ сдвигает разряды числа на n. Мы смещаем θθ11 влево на 2 и получаем 11θθ.

• Взгляните на эту операцию с точки зрения битов. Операция XOR для бита и его инверсии всегда дает 1. Поэтому a^(~a) всегда дает последовательность единиц.

• Операция вида x && (~θ << n) очищает n правых битов числа x. Значение ~θ – это последовательность единиц. При сдвиге числа влево на n позиций мы получаем последовательность единиц, за которыми следуют n нулей. Операция AND полученного числа с числом x очищает правые n битов числа x.

Чтобы решить остальные задачи, воспользуйтесь калькулятором Windows в режиме Вид ▸ Программист. Так вам будет проще выполнять бинарные операции, включая AND, XOR и сдвиги.

Биты: трюки и факты

При решении задач на битовые операции полезно знать некоторые факты. Их нужно не запомнить, а понять. Записи 1sи 0sиспользуются для обозначения последовательностей единиц или нулей соответственно.

Основные задачи: получение, установка, очистка и обновление бита

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

Извлечение бита

Метод getBit сдвигает 1 на i битов, создавая значение, например 00010000. Операция AND над числом num очищает все биты, кроме бита i. Затем этот бит сравнивается с 0. Если результат не равен 0, значит, бит i равен 1, иначе бит i равен 0.

1 boolean getBit(int num, int i) {

2 return ((num & (1 << i))!= 0);

3 }

Установка бита

Метод setBit сдвигает 1 на i бит, создавая значение, например 00010000. Операция OR над числом num изменяет только значение бита i. Все остальные биты остаются неизменными.

1 int setBit(int num, int i) {

2 return num | (1 << i);

3 }

Очистка бита

Этот метод – противоположность метода setBit. Сначала создается число 11101111 (инверсия числа 00010000). Затем производится операция ANDс числом num. Таким образом, очищается только i-й бит, а все остальные биты не изменяются.

1 int clearBit(int num, int i) {

2 int mask = ~(1 << i); 3 return num & mask;

4 }

Для очистки всех битов до бита i (включительно):

1 int clearBitsMSBthroughI(int num, int i) { 2 int mask = (1 << (i+1)) – 1;

3 return num & mask;

4 }

Для очистки всех битов от i до 0 (включительно):

1 public static int clearBitsIthrough0(int num, int i) {

2 int mask = ~((1 << (i+1)) – 1);

3 return num & mask;

4 }

Обновление бита

Этот метод является объединением методов setBit и clearBit. Сначала с помощью маски, например 11101111, очищается бит на позиции i. Затем значение v сдвигается вправо на i битов. В результате создается число, у которого i-й бит равен v, а все остальные биты нулевые. Операция OR для этих двух чисел обновляет i-й бит, если бит v равен 1, и оставляет его нулевым в противном случае.

1 int updateBit(int num, int i, int v) {

2 int mask = ~(1 << i);

3 return (num & mask) | (v << i);

4 }

Вопросы собеседования

5.1. Дано: два 32-битных числа Nи Mи две позиции битов iи j. Напишите метод для вставки M в N так, чтобы число M занимало позицию с бита j по бит i. Можно считать, что j и i имеют такие значения, что число M обязательно поместится в этот промежуток. Если M = 10011, для его размещения понадобится 5 битов между j и i. Если j=3 и i=2, число M не поместится в указанный промежуток.

Пример

Ввод: N = 10000000000, M = 10011, i = 2, j = 6

Вывод: N = 10001001100

5.2. Дано: вещественное число в интервале между 0 и 1 (например, 0,72), которое было передано как double. Запишите его двоичное представление. Если для представления числа не хватает 32 разрядов, выведите сообщение об ошибке.

5.3. Дано: положительное число. Выведите ближайшие наименьшее и наибольшее числа, которые имеют такое же количество единичных битов в двоичном представлении.

5.4. Объясните, что делает код: ((n& (n-1)) ==0).

5.5. Напишите функцию, определяющую количество битов, которые необходимо изменить, чтобы из целого числа A получить целое число B.

Пример

Ввод: 31, 14 Вывод: 2

5.6. Напишите программу, меняющую местами четные и нечетные биты числа. Количество инструкций должно быть наименьшим (нужно поменять местами биты 0 и 1, 2 и 3 и т. д.).

5.7. Массив A[1…n] содержит целые числа от 0 до n, но одно число отсутствует. В этой задаче мы не можем получить доступ к любому числу в массиве A с помощью одной операции. Элементы массива A хранятся в двоичном виде, а доступ к ним осуществляется только при помощи команды извлечь j-й бит из A[i], имеющей фиксированное время выполнения. Напишите код, обнаруживающий отсутствующее целое число. Можно ли выполнить эту задачу за время O(n)?

5.8. Изображение с монохромного экрана сохранено как одномерный массив байтов, так что в одном байте хранится информация о восьми соседних пикселах. Ширина изображения w кратна 8 (байты соответствуют столбцам). Высоту экрана можно рассчитать, зная длину массива и ширину экрана. Реализуйте функцию drawHorizontalLine(byte[]screen, intwidth, intx1, intx2, inty), которая рисует горизонтальную линию из точки (x1, y) в точку (x2, y).

Дополнительные вопросы: массивы и строки (1.1, 1.7), рекурсия (8.4, 8.11), масштабируемость и лимиты памяти (11.3, 11.4), C++ (13.9), модерирование (17.1, 17.4), задачи повышенной сложности (#18.1).

Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию

Подняться наверх