Bitwise and (or &) of a range - GeeksforGeeks
Given two non-negative long integers, x and y given x <= y, the task is to find bit-wise and of all integers from x and y, i.e., we need to compute value of x & (x+1) & … & (y-1) & y.7
Read full article from Bitwise and (or &) of a range - GeeksforGeeks
Given two non-negative long integers, x and y given x <= y, the task is to find bit-wise and of all integers from x and y, i.e., we need to compute value of x & (x+1) & … & (y-1) & y.7
An efficient solution is to follow following steps.
1) Find position of Most Significant Bit (MSB) in both numbers.
2) If positions of MSB are different, then result is 0.
3) If positions are same. Let positions be msb_p.
……a) We add 2msb_p to result.
……b) We subtract 2msb_p from x and y,
……c) Repeat steps 1, 2 and 3 for new values of x and y.
1) Find position of Most Significant Bit (MSB) in both numbers.
2) If positions of MSB are different, then result is 0.
3) If positions are same. Let positions be msb_p.
……a) We add 2msb_p to result.
……b) We subtract 2msb_p from x and y,
……c) Repeat steps 1, 2 and 3 for new values of x and y.
// Find position of MSB in n. For example if n = 17,
// then position of MSB is 4. If n = 7, value of MSB
// is 3
int
msbPos(ll n)
{
int
msb_p = -1;
while
(n)
{
n = n>>1;
msb_p++;
}
return
msb_p;
}
// Function to find Bit-wise & of all numbers from x
// to y.
ll andOperator(ll x, ll y)
{
ll res = 0;
// Initialize result
while
(x && y)
{
// Find positions of MSB in x and y
int
msb_p1 = msbPos(x);
int
msb_p2 = msbPos(y);
// If positions are not same, return
if
(msb_p1 != msb_p2)
break
;
// Add 2^msb_p1 to result
ll msb_val = (1 << msb_p1);
res = res + msb_val;
// subtract 2^msb_p1 from x and y.
x = x - msb_val;
y = y - msb_val;
}
return
res;
}
Read full article from Bitwise and (or &) of a range - GeeksforGeeks