Отключите крайний правый установленный бит, используя 2s дополнение

Опубликовано: 27 Февраля, 2023

Дан номер N . Задача состоит в том, чтобы сбросить самый правый установленный бит N.
Примеры:

Input: N = 5 
Output: 4
Explanation:
101(5) -> 100(4)

Input : N = 78
Output : 76
Explanation:
1001110(78) -> 1001100(76)

Наивный подход:

  • Простой подход к переворачиванию самого правого установленного бита состоит в том, чтобы найти положение самого правого установленного бита в числе с помощью побитовой операции сдвига вправо, чтобы проверить первое вхождение 1.
  • Затем переверните биту в этом положении. Переворот можно выполнить, применив XOR к заданному числу и числу с установленным битом в этой позиции.
    Важное свойство для флип-битов:
0 ^ 1 = 1
1 ^ 1 = 0

Xor with 1 flips the bit.
  • Установка только данного бита может быть выполнена путем возведения 2 в степень позиции, чтобы установить конкретный бит.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(32)

Вспомогательное пространство: O(1)

Эффективный подход:
Мы можем перевернуть младший бит за O(1). Хотя наивный подход тоже работает нормально, существует и однострочное решение проблемы. Мы можем сделать следующее:

  1. Получить дополнение до 2 числа (просто -n дает дополнение до 2)
  2. Выполните побитовую операцию И между числом и его дополнением до 2.
  3. Вычтите вышеуказанный результат из заданного числа.
  4. В конечном результате LSB перевернут.

Объяснение

             N = 1001110 (78)
2"s compliment = 0110010
      N & (-N) = 0000010
N - (N & (-N)) = 1001100 (76)

Временная сложность: O(1)

Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ