Краткое руководство по обработке битов в Java

Битовая манипуляция – это прямое манипулирование битами данных для выполнения операций и является важным навыком оптимизации, который в настоящее время тестируется рекрутерами FAANG. Однако эта тема в значительной степени математична и редко освещается в рамках неуниверситетских компьютерных наук.

Сегодня мы дадим вам учебное пособие по манипулированию битами и рассмотрим некоторые практические занятия с популярными вопросами для интервью.

Вот что мы рассмотрим сегодня:

• Что такое битовая манипуляция?
• Побитовые операторы
• Побитовые трюки
• Практическая практика с побитовыми операторами
• Чему учиться дальше

Будьте готовы к любой вопрос о манипуляциях с битами

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

Освойте Решение проблем с использованием Битовых Манипуляций

Что такое битовая манипуляция?

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

Большинство языков программирования заставят вас работать с абстракциями, такими как объекты или переменные, а не с битами, которые они представляют. Однако для повышения производительности и уменьшения ошибок в определенных ситуациях необходима прямая обработка битов.

Для работы с битами требуется глубокое знание двоичного кода и двоичного преобразования .

Вот несколько примеров задач, требующих битовых манипуляций:

• Низкоуровневое управление устройством
• Алгоритмы обнаружения и исправления ошибок
• Сжатие данных
• Алгоритмы шифрования
• Оптимизация

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

// arithmetic
(rgb / 256) % 256

// bit
(rgb >> 8) & 0xFF

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

Мы рассмотрим, что делает каждый из этих операторов позже в этой статье ( >> и & ).

Побитовые манипуляции и кодирование.

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

Обладание этими знаниями демонстрирует, что вы всесторонне развитый разработчик, который разбирается как в конкретных инструментах, так и в основах информатики.

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

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

Побитовые операторы

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

В то время как арифметические операции выполняют операции с удобочитаемыми значениями ( 1+2 ), побитовые операторы напрямую управляют низкоуровневыми данными.

Преимущества

• Это быстрые и простые действия.
• Они напрямую поддерживаются процессором.
• Они используются для манипулирования значениями для сравнений и вычислений.
• Побитовые операции невероятно просты и быстрее, чем арифметические операции.

Давайте кратко рассмотрим каждый из основных побитовых операторов и их применение.

и Оператор

AND ( & ) – это двоичный оператор, который сравнивает два операнда одинаковой длины. Операнды преобразуются из их читаемой формы в двоичное представление. Для каждого бита операция проверяет, являются ли оба бита 1 через оба операнда. Если да, то этот бит установлен на 1 в ответе. В противном случае соответствующий бит результата устанавливается равным 0.

По сути, он умножает каждый бит на соответствующий бит в другом операнде. Как умножение чего-либо на 0 приводит к 0 , то И сравнение с любым 0 бит приведет к 0 .

• Если два входных бита равны 1, то выходной сигнал равен 1.
• Во всех остальных случаях его значение равно 0, например:
  • 1 & 0 => приводит к 0.
  • 0 & 1 => приводит к 0.
  • 0 & 0 => приводит к 0.

    0101 (decimal 5)
AND 0011 (decimal 3)

0 *

1 *

0 *

1 *

Следовательно:

= 0001 (десятичный 1)

Операция может быть использована для определения того, установлен ли конкретный бит (1) или очищен (0). Он также используется для очистки выбранных битов регистра, в котором каждый бит представляет отдельное логическое состояние.

class AndOperation {
    public static void main( String args[] ) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise AND of (" + x + " , " + y + ") is: " + (x & y)); // yields to 8
    }
}

операционная Оператор

Оператор OR ( | ) – это двоичный оператор, который принимает два операнда одинаковой длины, но сравнивает их противоположным образом с AND; если любой соответствующий бит равен 1 , ответ таков 1 . В противном случае ответ будет таким 0 . Другими словами, побитовое ИЛИ возвращает ‘1’, если один из заданных входных данных равен 1 .

• Если два входных бита равны 0 , на выходе получается 0 .

• Во всех остальных случаях это 1 . Например:

  • 1 | 0 => дает значение 1.
  • 0 | 1 => дает значение 1.
  • 1 | 1 => дает значение 1.

a = 12
b = 10
---------------------------------
a in Binary : 0000 0000 0000 1100
b in Binary : 0000 0000 0000 1010
---------------------------------
a | b           : 0000 0000 0000 1110
--------------------------------------

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

class OROperation {
    private static int helper(int x, int y) {
        return x | y;
    }
    public static void main(String[] args) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise OR of " + x + ", " + y + " is: " + helper(x, y)); // yields to 14
    }
}

НЕ Оператор

NOT ( ~ ), или иногда называемый оператором побитового дополнения, представляет собой унарную операцию, которая принимает один ввод и меняет местами каждый бит в его двоичном представлении к противоположному значению.

Все экземпляры 0 стать 1 , и все экземпляры 1 стать 0 . Другими словами, НЕ инвертирует каждый входной бит. Эта перевернутая последовательность называется дополнением битового ряда.

Например, рассмотрим x

Двоичное числовое представление x равно:

x 00000000 00000000 00000001

Теперь побитовое НЕ из x будет:

~x 11111111 11111111 11111110

Так:

• x содержит 31 нуль(0) и один 1
• ~x содержит 31 единицу(1) и один 0(ноль)

Это делает число отрицательным, как и любая коллекция битов, начинающаяся с 1 является отрицательным.

NOT полезен для переключения чисел без знака на зеркальное значение на противоположной стороне от их средней точки.

Для 8-разрядных целых чисел без знака, НЕ - x .

Формула: ~x^{32} - x

class NOTOperation {
    public static void main( String args[] ) {
        int a = 1;
        System.out.println("Bitwise NOT of a is : " + ~a);
    }
}

Оператор XOR

Побитовая операция XOR ( ^ ), сокращение от “Exclusive-Or”, представляет собой двоичный оператор, который принимает два входных аргумента и сравнивает каждый соответствующий бит. Если биты противоположны, результат имеет 1 в этом положении бита. Если они совпадают, то 0 возвращается.

• 1 ^ 1 => приводит к 0.
• 0 ^ 0 => приводит к 0.
• 1 ^ 0 => приводит к 1.
• 0 ^ 1 => приводит к 1.

Например:

a = 12
b = 10
--------------------------------------
a in binary : 0000 0000 0000 1100
b in binary : 0000 0000 0000 1010
--------------------------------------
a ^ b       : 0000 0000 0000 0110
--------------------------------------

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

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

class XOROperation {
    public static void main( String args[] ) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise XOR of (x , y) is : " + (x ^ y)); // yields to 6
    }
}

Оператор сдвига влево и вправо

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

Эти операторы могут быть применены к целочисленным типам, таким как int , long , short , byte или char .

Существует три типа сдвига:

• Сдвиг влево: << является оператором сдвига влево и отвечает потребностям как логических, так и арифметических сдвигов.
• Арифметический/знаковый сдвиг вправо: >> – это арифметический (или знаковый) оператор сдвига вправо.
• Логический/беззнаковый сдвиг вправо: >>> является логическим (или беззнаковым) оператором сдвига вправо.

В Java все целочисленные типы данных имеют знак и << и >> являются исключительно арифметическими сдвигами.

Вот пример сдвига влево:

6 00000000 00000000 00000110

Смещение этого битового шаблона влево на одну позицию ( 6 << 1 ) приводит к числу 12:

6 << 00000000 00000000 00001100

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

6 << 1 → 6 * 2^1 → 6 * 2

6 << 3 → 6 * 2^3 → 6 * 8

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

class LeftShift {
    private static int helper(int number, int i) {
        return number << i;// multiplies `number` with 2^i times.
    }
    public static void main(String[] args) {
        int number = 100;
        System.out.println(number + " shifted 1 position left, yields to " + helper(number, 1));
        System.out.println(number + " shifted 2 positions left, yields to " + helper(number, 2));
        System.out.println(number + " shifted 3 positions left, yields to " + helper(number, 3));
        System.out.println(number + " shifted 4 positions left, yields to " + helper(number, 4));
    }
}

С помощью сдвига вправо вы можете выполнить либо арифметический ( >> ), либо логический ( >> ) сдвиг.

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

1011 0101 >> 1 = **1**101 1010

Формула: x >>/(2^y)

С другой стороны, логический сдвиг просто перемещает все вправо и заменяет MSB на 0 .

1011 0101 >>> 1010

Формула: a >>>/(2^b)

Продолжайте изучать манипуляции с битами.

Подготовьтесь к вопросам о манипуляциях с битами ФААНГА в два раза быстрее. Обучающие курсы подготовки к собеседованию позволят вам настроиться на успех с помощью практической практики с наиболее часто задаваемыми вопросами для собеседования.

Освойте Решение проблем с использованием Битовых Манипуляций

Побитовые трюки

Теперь давайте рассмотрим несколько приемов, которые вы можете выполнить с помощью побитовых операторов.

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

Проверьте, является ли число четным

Этот тест проверяет ваши знания о том, как работает и как четные/нечетные числа различаются в двоичном формате. Вы можете просто использовать:

(x & 1 ) == 0
  0110 (6)
& 0001
= 0000 TRUE

Это решение основывается на двух вещах:

• 2 равно 0001
• Крайнее правое число для всех нечетных чисел, больших 2, равно 1

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

Преобразование символов в верхний или нижний регистр

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

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

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

public class Test 
{ 

    static int x=32; 

    // tOGGLE cASE = swaps CAPS to lower 
    // case and lower case to CAPS 
    static String toggleCase(char[] a) 
    { 
        for (int i=0; i

Практическая практика с побитовыми операторами

​ Теперь давайте немного попрактикуемся с этими операторами.

И Вызов: Количество установленных битов

Напишите Java-программу для подсчета количества битов, установленных в 1 (set bits) целого числа.

Решение и объяснение

class CountSetBit {
    private static int helper(int n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}

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

• Если число имеет 2 заданных бита, то цикл while выполняется два раза.
• Если число имеет 4 заданных бита, то цикл while выполняется четыре раза.

Наш цикл while повторяется до n , каждый раз делясь на 2 с помощью оператора AND. На проходе 1, 125 становится 62 , и количество увеличивается на 1. На втором проходе, 62 становится 31 , и количество увеличивается до 2. Это продолжается до тех пор, пока n становится 0, и затем возвращается количество.

Побитовое ИЛИ: Количество переворотов

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

Переворот – это изменение одного бита на противоположное значение, то есть. 1 --> 0 или 0 --> 1 .

Ввод: a , b , c

Результат: 3

Решение и объяснение

class MinFlips {
    private static int helper(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int bitC = ((c >> i) & 1);
            int bitA = ((a >> i) & 1);
            int bitB = ((b >> i) & 1);

            if ((bitA | bitB) != bitC) {
                ans += (bitC == 0) ? (bitA == 1 && bitB == 1) ? 2 : 1 : 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int a = 2;
        int b = 6;
        int c = 5;
        System.out.println("Min Flips required to make two numbers equal to third is : " + helper(a, b, c));
    }
}

Сначала мы инициализируем ans к 0 . Затем мы выполняем цикл из диапазона от 0 до 31. Мы инициализируем битА , BitB и bitC , чтобы равняться нашей формуле сдвига вправо и равняться 1:

(a/(2^i) & 1

Затем мы проверяем, является ли Бит | битБ равен сука . Если да, то мы переходим к проверке, является ли bitC . Оттуда, если битА и битБ затем мы увеличиваем ans на 2. В противном случае мы увеличиваем ans на 1.

Наконец, мы возвращаем ans , который увеличивался на единицу при каждой операции.

Побитовое XOR: Единственное число

Найдите элемент в массиве, который не повторяется.

Ввод: числа = { 4, 1, 2, 9, 1, 4, 2 }

Результат: 9

Решение и объяснение

class SingleNumber {
    private static int singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        return xor;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 9, 1, 4, 2};
        System.out.println("Element appearing one time is " + singleNumber(nums));
    }
}

Это решение основано на следующей логике:

• Если мы возьмем XOR из нуля и некоторого бита, он вернет этот бит: a ^
• Если мы возьмем XOR из двух одинаковых битов, он вернет 0: a ^
• Для n чисел можно применить приведенную ниже математику: a ^ b ^ a = (a ^ a) ^ ^

Например,

1 ^ 5 ^ 1 =

(1 ^ 1) ^ 5 =

0 ^

Следовательно, мы можем XOR все биты вместе, чтобы найти уникальный номер.

Побитовый Сдвиг Влево: Получить Первый Установленный Бит

Учитывая целое число, найдите позицию первого заданного бита ( 1 ) справа.

Ввод: n

18 в двоичном коде = 0b10010

Результат: 2

Решение и объяснение

class FirstSetBitPosition {
    private static int helper(int n) {
        if (n == 0) {
            return 0;
        }

        int k = 1;

        while (true) {
            if ((n & (1 << (k - 1))) == 0) {
                k++;
            } else {
                return k;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("First setbit position for number: 18 is -> " + helper(18));
        System.out.println("First setbit position for number: 5 is -> " + helper(5));
        System.out.println("First setbit position for number: 32 is -> " + helper(32));
    }
}

Логика этого решения основана на комбинации сдвига влево и операции AND.

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

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

Чему учиться дальше

Поздравляем с завершением нашего краткого руководства по манипуляциям с битами! Манипулирование битами может быть сложной темой для изучения, но практическая практика – лучший способ совершенствоваться.

Поскольку вы ищете больше практики, ознакомьтесь с этими практическими проблемами:

• Найдите недостающий номер
• Найдите первый установленный бит, используя сдвиг вправо
• Подсчитайте количество цифр в целом числе
• Проверьте, является ли число степенью 2

Чтобы помочь вам попрактиковаться в этих и других вопросах интервью с битами, Education создала Мастер Решения задач с использованием Битовых манипуляций . Этот курс поможет вам освежить свои знания о двоичных преобразованиях, а также множество практических вопросов на собеседовании.

К концу курса вы будете знать эффективные решения всех основных вопросов, связанных с манипуляцией на собеседовании, которые задают рекрутеры FAANG.

Счастливого обучения!

Продолжайте читать о системах счисления

• Шпаргалка по нотации Big-O: быстрые ответы на вопросы Big-O
• Компьютерные системы счисления 101: Двоичные и шестнадцатеричные преобразования
• Лучшие структуры данных и алгоритмы, которые должен знать каждый разработчик

Оригинал: “https://dev.to/educative/a-quick-guide-to-bit-manipulation-in-java-3533”