Количество чисел в диапазоне [L, R] с LSB равным 0 в их двоичном представлении

Даны два целых числа L и R . Задача состоит в том, чтобы найти количество всех чисел в диапазоне [L, R] , у которых младший значащий бит в двоичном представлении равен 0.

Примеры :

Input: L = 10, R = 20  
Output: 6  

Input: L = 7, R = 11  
Output: 2   

Наивный подход . Самый простой способ решить эту проблему — проверить каждое число в диапазоне [L, R], если наименее значимый бит в двоичном представлении равен 0.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(r – l)
Вспомогательное пространство: O(1)

Эффективный подход : эту проблему можно решить, используя свойства битов. Только четные числа имеют самый правый бит как 0 . Счетчик можно найти по этой формуле ((R / 2) — (L — 1) / 2) за время O(1) .

Ниже приведена реализация вышеуказанного подхода:

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