rangeAND: bitwise AND of all ints in range

Q: Given a continuous range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

  • the lowest bit will most likely see 0 and 1 so … becomes zero
  • (turns out to be a minor tip) if the range has size > 8 then lowest 3 bits all zeroed out
  • imagine the bit array object incrementing from m to n. We want to find out if there’s a stable higher portion
  • Key technique — look at some examples. We can convert m and n to two bit images. we can look at some examples below.
  • we can compare the two bit images left to right to find the “higher portion”. All lower bits are probably zeroed out in the result

10110101
10110100
10110011
10110010
10110001
—–
10110000

–my solution not tested on Leetcode: https://github.com/tiger40490/repo1/blob/cpp1/cpp/rangeAnd.cpp
* compare m and n left to right. If m is shorter, then return 0.
* if same length, then compare left to right until a difference is found. Until that bit, all left-end bits are “retained”.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s