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

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

1. Оператор BITWISE AND (&)

Этот побитовый оператор & принимает два бита / числа в качестве операндов и возвращает 1, если оба бита равны 1, в противном случае возвращает 0.

Пример: 1 и 1 = 1, 1 и 0 = 0, 0 и 0 = 0.

2. Оператор BITWISE OR (|)

Это побитовое | Оператор принимает два бита или числа в качестве операндов и возвращает 0, если оба бита равны 0, в противном случае возвращает 1.

Ex: 1|1 = 1, 1|0 = 1, 0|0 = 0.

3. Оператор BITWISE XOR (^)

Этот побитовый оператор ^ принимает в качестве операндов два бита или числа и возвращает 0, если оба бита одинаковы, в противном случае - 1.

Ex: 1 ^ 1 = 0, 1 ^ 0 =1.

Два наиболее важных свойства побитового оператора XOR:

I. a ^ a = 0 (XOR двух одинаковых чисел равен 0)

II. 0 ^ a = a (XOR любого числа с 0 - это само число)

4. Оператор BITWISE left Shift (‹★)

Этот побитовый оператор принимает два числа в качестве операндов и сдвигает биты первого числа влево на заданное число (второе число) времени. Его выражение - ‹< b.

Ex: 1<<1 = 2.

Здесь a = 1, b = 1. Двоичное число 1 = 01, сдвигая его биты влево на 1 (b), мы получаем 10, что равно 2. Итак, 1 ‹---------------- 1 = 2.

Еще одно полезное наблюдение: сдвиг влево (a, b) равен a * pow (2, b).

a ‹---------------- b = a * pow (2, b). В приведенном выше примере 1 ‹рк 1 = 1 * pow (2,1) = 1 * 2 = 2.

5. Оператор BITWISE Right Shift (››)

Этот побитовый оператор принимает два числа в качестве операндов и сдвигает биты первого числа вправо на заданное число (второе число) времени. Его выражение - ›› b.

Ex: 4>>1 = 2.

a = 4, b = 1. Двоичное значение a = 100, сдвигаясь вправо на 1 раз, получаем 010 = 2. Итак, 4 ›› 1 = 2.

Еще одно полезное наблюдение: сдвиг влево (a, b) равен a / pow (2, b).

a ›› b = a / pow (2, b). В приведенном выше примере 4 ›› 1 = 4 / pow (2,1) = 4/2 = 2.

6. Оператор BITWISE NOT (~)

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

Ex: ~4 = 3.

Как мы знаем, двоичное (4) = 100, используя оператор not, 1 - ›0 и 0-› 1. Итак, ~ 100 = 011, что равно 3.

Теперь давайте зададим несколько основных вопросов, основанных на этих концепциях.

1. Умножение числа на степень двойки.

Предположим, нам нужно умножить число на степень 2, вместо использования оператора умножения и степенной функции, мы можем использовать здесь побитовый оператор сдвига влево. Как я уже упоминал выше, a ‹* b = a * pow (2, b).

Таким образом, Код - это просто ans = a ‹< b.

2. Деление числа на степень двойки.

Предположим, нам нужно разделить число на степень 2, вместо использования оператора Divide и функции мощности, мы можем использовать здесь побитовый оператор сдвига вправо. Как я уже упоминал выше, a ›› b = a / pow (2, b).

Итак, Код - это просто ans = a ›› b.

3. Обмен двух чисел

В этом вопросе мы должны поменять местами элементы двух переменных. Как a = 7, b = 8 после замены a = 8, b = 7.

Наш общий подход состоит в том, чтобы сохранить переменную «a» в другой переменной, такой как temp, и поместить значение «b» в «a», а затем снова поместить значение temp в «b».

int temp = a;
a = b;
b = a;

Но здесь мы можем использовать побитовое XOR. Код показан ниже:

int temp = a ^ b;
a = temp ^ a;
b = temp ^ b;

Как работает приведенный выше код. Как упоминалось ранее, здесь работают побитовые свойства XOR с номерами 1 и 2.

В первой строке temp = a ^ b. мы сохраняем xor a и b.
Во второй строке, что мы делаем a = temp ^ a (a ^ b ^ a), Итак < br /> a ^ a = 0 (номер свойства 1) и 0 ^ b, который равен b, он присваивается a.
В третьей строке то, что мы делаем, b = temp ^ b (a ^ b ^ b), Итак,
b ^ b = 0 (свойство номер 1) и 0 ^ a, который является a, присваивается b.

4. Чтобы проверить, является ли данное число четным или нечетным.

Предположим, нам дана ситуация, когда мы должны проверить, что данное число нечетное или четное.
Итак, что мы делаем?
Мы быстро используем оператор по модулю (%), чтобы проверить это, но что, если говорят, что не используют оператор по модулю. В этой ситуации мы можем использовать оператор побитового И (&).
Как это работает? мы используем приведенное ниже выражение.

Каждое число является нечетным, если его крайний левый бит равен 1, в противном случае - четным.

Пример:
num = 4 (100).
100 & 001 = 0. (Четное число)
num = 7 (111).
111 & 001 = 1 (Нечетное число)

5. Чтобы установить i-й бит данного числа

Предположим, нам дано число 5 (101). мы должны установить второй бит числа и получить результат 111 = 7.

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

Шаг: 1
Сначала нам нужно будет сдвигать влево на 1 бит, который мы должны установить.
Означает, что если нам даны num = 5, bit = 2.
Итак, temp = 1 ‹< (bit-1)
Шаг: 2
На втором шаге мы сделаем or of this temp с заданным числом.
число = число | темп

Итак, программа будет такой:

int num = 5;
int bit = 2;
int temp = 1 ‹< (bit-1);
число = число | temp;

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

Как показано на рисунке выше, мы успешно установили 2-битное число.

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

6. Чтобы отключить i-й бит числа.
7. Чтобы проверить, является ли число степенью двойки или нет.
8. Чтобы найти минимум / максимум двух чисел.
9. Чтобы подсчитать все установленные биты в данном числе.
10. перевернуть i-й бит числа. (означает, что если оно равно 0, преобразовать его в 1, если оно равно 1, то в 0).

Прилагаю еще несколько ссылок на вопросы, которые вы можете попробовать.

  1. Элемент большинства
  2. Обратные биты
  3. Подмножества
  4. Отсутствующий номер
  5. Сила четырех
  6. Найди два пропущенных числа
  7. Сумма двух целых чисел
  8. Найди повторяющееся и недостающее

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

Большое спасибо.