Bitwise AND and OR of numbers in a given range

Given two numbers L & R , Find Bitwise AND and OR of all numbers lying between L and R inclusive.

Let L and R are not equal means we will find at least one 0 (zero) in LSB (least significant bit) of numbers from L to R. The idea is:

• Last bit of (odd number & even number) is 0. Because we are trying to find bitwise AND, so if any bit there are at least one 0, AND of that bit will be zero.
• when L != R, there is at least an odd number and an even number, so the last bit position result is 0.
• Move L and R right a position.

// Program to find Bitwise AND of all numbers lying between L and R inclusive.
public int rangeBitwiseAnd(int L, int R) {

  if (L == 0){
    return 0;
  }

  // Number of bits which are 0 on the right
  int shift = 0;

  while(L != R){
    L >>= 1;
    R >>= 1;
    shift++;
  }

  return L << shift;
}

In above code shift variable is storing how many of bits from LSB are zero until L!=R. So lets iterate with L = 110010110 and R = 110011101. In first iteration L and R are not equal means there is at least one zero in LSB of L to R, and multiply shift by two so that shift = 10 means last bit is off (zero) and now right shift both (L,R) to remove LSB because we have done with LSB. In second iteration (same as above) we have at least one zero from L to R so multiply step by two step = 100 second bit is also off, and right shift both. After fourth bit we have L==R means non of bit differ from each other so multiply ( L or R ) with shift to get answer or left shift L << 4 to get answer.

Bitwise OR of range of number can be found using below steps:

1. Find the position of MSB in both the numbers (L and R)
2. If the position of both MSBs are different, set all the bits from the max(MSB1, MSB2) including this different bit upto 0^th (Zero) bit i.e. add the value (1 << i) for all 0 ≤ i ≤ max(MSB1, MSB2) in the answer.
3. If the position of both MSBs are same, then set this bit corresponding to MSB or add the value (1 << MSB) in the answer. Subtract the value (1 << MSB) from both the numbers (L and R).
4. Repeat step ‘3’, until MSB are same, then do the step ‘2’ to get the final answer.

// Returns MSB position
int msbPosition(long num) 
{
  int msb_p = -1; 

  while (num > 0) 
  {
    num = num >> 1; 
    msb_p++; 
  }

  return msb_p; 
} 
  
// Bitwise OR of all integers between L and R 
int rangeBitwiseOr(int L, int R) 
{
  int res = 0; 
  int msbL = msbPosition(L); 
  int msbR = msbPosition(R); 

  while (msbL == msbR) 
  {
    long res_val = (1 << msbL); 

    // Add this value until msbL and msbR are same; 
    res += res_val; 

    L >>= 1; 
    R >>= 1; 

    msbL = msbPosition(L); 
    msbR = msbPosition(R); 
  }

  // Find the max of msbL and msbR 
  msbL = Math.max(msbL, msbR); 

  // Set all the bits from msbL upto 0th bit in the result 
  for (int i = msbL; i >= 0; i--)  
  {
    long res_val = (1 << i); 
    res += res_val; 
  }

  return res; 
}