Bitwise AND between a range of integers

Problem Statement

You will be given two integers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B, both inclusive.

”’
Since & is only 1 when both are 1 and when calculating in a range if the range ends do not both have 1 the rest of the whole binary is 0

The only bits that will be 1 will be bits that are common to the upper bits of A and B. Everything else will have at least one instance of a 0 in that range. So just start from the high order bit downwards. Output the matching bits. As soon as you hit a disagreement between the binaries of A and B (which will be 0 in A and 1 in B) output zeros until you get to the length of B.

”’
def bitAndWholeArray(arr):
string1 = bin(arr[0])
string2 = bin(arr[1])
index_count = 0
res = ‘0b’
for index,i in enumerate(string1):
if index == 0 or index == 1:
continue
if i == string2[index]:
res = res + i
else:
index_count = index
break

for _ in range(index_count,len(string2)):
res = res + ‘0’

return int(res,2)
n = int(raw_input())
for _ in range(n):
arr = map(int,raw_input().split(‘ ‘))
print bitAndWholeArray(arr)

Advertisements

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