21.02.2024
201. Bitwise AND of Numbers Range medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/514
Problem TLDR
Bitwise AND for [left…right].
Intuition
To understand the problem, let’s observe how this works:
// 0 0000
// 1 0001 2^0
// 2 0010
// 3 0011
// 4 0100 3..4 = 0 2^2
// 5 0101 3..5 = 0
// 6 0110
// 7 0111 6..7
// 8 1000 2^3
// 9 1001 7..9 = 0
Some observations:
When interval intersects
4
,8
and so on, itAND
operation becomes0
.Otherwise, we take the common prefix:
6: 0110 & 7: 0111 = 0110
.
Approach
We can take the most significant bit
and compare it.
In another way, we can just find the common prefix trimming the bits from the right side.
Complexity
Time complexity:
O(1), at most 32 calls happensSpace complexity:
O(1)
Code
fun rangeBitwiseAnd(left: Int, right: Int): Int {
if (left == right) return left
val l = left.takeHighestOneBit()
val r = right.takeHighestOneBit()
return if (l != r) 0 else
l or rangeBitwiseAnd(left xor l, right xor r)
}
pub fn range_bitwise_and(left: i32, right: i32) -> i32 {
if left == right { left }
else { Self::range_bitwise_and(left / 2, right / 2) * 2 }
}