-1

https://leetcode.com/problems/number-complement/

The following are two valid solutions for this problem, why did I run into an integer overflow in the first solution when I had the mask variable to be an int (instead of a long), and why was I able to get away with an int variable type for the mask in the second solution

 public int findComplement(int num) {

    // Make a copy of the number for length estimation purposes , because we will begin mutating it
    // directly
    int input = num;

    // Use a power of two mask to bring 1 at every position and flip in stages using XOR
    for (long mask = 1; mask <= input; mask *= 2) {
      num = (int) (num ^ mask);
    }

    return num;
  }

public int findComplement2(int num) {
        
    int save = num; 
    int mask = 1;
    
    while (save != 0) {
        num = num ^ mask;
        mask = mask << 1;
        save = save >> 1;
    }
    
    
   return num;
    
}
zulu-700
  • 47
  • 5

1 Answers1

1

The way your condition in your for loop is set requires that the value for mask must be greater than the value of input to terminate. However, when you use Integer.MAX_VALUE as the input, there will be no other int value greater than Integer.MAX_VALUE, which would stop the for loop. So your for loop will runs forever because

for(/* */, mask <= Integer.MAX_VALUE, /* */) {
}

will be always true in case the variable mask is of type int (or smaller).

To stop the for loop you have to use the type long for the variable mask so there is a chance that mask <= input will result in false in case the input value Integer.MAX_VALUE is used.

In your second method, you run in an integer overflow as well, as mask will jump from 1073741824 to -2147483648. However, in that case the variable save will be zero, terminating the while loop by the save != 0 check. so the fact that mask is negative from an integer overflow has no consequences.

Progman
  • 16,827
  • 6
  • 33
  • 48