BitwiseANDOfNumbersRange

Problem

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Solution

Consider 2 binary numbers \(left < right\). Observe that \(left\) and \(left + 1\) differ only in the 1’s bit. Then \(left \land (left + 1)\) is \(left\) with the last bit set to 0. Similarly, \(left + 1\) differ in the 2’s bit, so \(left \land (left + 1) \land (left + 2)\) is \(left\) with the last 2 bits set to 0. The bitwise \(\land\) of all binary numbers in \([left, right]\) is the common prefix of \(left\) and \(right\) with all other bits set to 0, as the subsequent bits will vary in \([left, right]\).

Code

https://github.com/GeorgeRPu/tech-interview-prep/blob/main/solutions/SetMatrixZeroes.py

def rangeBitwiseAnd(left: int, right: int) -> int:
    """Bitwise AND all numbers from ``left`` to ``right``, inclusive.
    """
    bit_and = 0
    for i in range(32, -1, -1):
        leftBit = getBit(left, i)
        if leftBit != getBit(right, i):
            return bit_and
        else:
            bit_and += leftBit << i

    return bit_and


def getBit(num, i):
    """Gets the ``i``-th bit of ``num``.
    """
    return (num >> i) & 1

Test

>>> from BitwiseANDOfNumbersRange import rangeBitwiseAnd
>>> rangeBitwiseAnd(5, 7)
4
>>> rangeBitwiseAnd(0, 1)
0
>>> rangeBitwiseAnd(1, 2)
0

Functions

`getBit`(num, i)	Gets the `i`-th bit of `num`.
`rangeBitwiseAnd`(left, right)	Bitwise AND all numbers from `left` to `right`, inclusive.