2 Java solutions to deal with overflowed input integer (>2147483647)


  • 2

    In Java, Integer.MAX_VALUE = 2147483647,
    Integer.MIN_VALUE = -2147483648

    When int overflowed, it counts from -2147483648, e.g. unsigned int: 2147483648 -> int: -2147483648.

    1. Use long to represent the big int but needs to add those overflowed part

      public int hammingWeight(int n) {
      //convert n to long
      long n1 = (long)n;
      if(n<0) // meaning n is overflowed!, Integer.MAX_VALUE+1 == Integer.MIN_VALUE
      n1 = (long)Integer.MAX_VALUE + ((long)Integer.MAX_VALUE+2+n);
      int count = 0;
      while(n1>0) {
      if(n1%2!=0)
      count++;
      n1 /= 2;
      }
      return count;
      }

    2. Don't use long, but needs to shift the bit of overflowed int to make it valid int.
      Overflowed int will always starts with '1' in its bit representation. So & with MAX_VALUE can make off this leading '1'

      public int hammingWeight(int n) {
      int count = 0;
      if(n<0) { // meaning n is overflowed!
      count++; //leading bit must be 1 for negative value
      n = n & Integer.MAX_VALUE; // and this value -> 01111111111111111111111111111111, to mask off the leading 1
      }
      while(n>0) {
      if(n%2!=0)
      count++;
      n /= 2;
      }
      return count;
      }


  • 0
    Y

    public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
    int i=0;
    long n1=n & 0x0ffffffffL;
    while(n1!=0){
    i+=n1%2;
    n1=n1/2;
    }
    return i;
    }
    }


  • 0
    S

    Would you please explain this line more?
    n1 = (long)Integer.MAX_VALUE + ((long)Integer.MAX_VALUE+2+n);

    I understand that n<0 means overflowed. Explanation of this line would be really helpful.
    Thank you in advance.


  • 0

    In short, this line is to just add the "overflowed part" to the MAXVALUE and represent the result number using LONG. But how to get the "overflowed part?", remember Integer.MAXVALUE = 2147483647, Integer.MINVALUE = -2147483648, when int is 1 larger than MAXVALUE, it will become -2147483648, when int is 2 larger than MAXVALUE, it will become -2147483647. So you may get the pattern, (long)Integer.MAXVALUE+2+n (where n is overflowed and obvious negative) will give you the overflowed part.


  • 0
    S

    hmmm...now I got it. from what i understood is that (long)Integer.MAXVALUE+2+n part is giving back the overflown part in positive and then adding with Integer.MAX_VALUE. Please correct me if I am wrong. Thanks once again.


  • 0

    yes, correct


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.