I solved a programming question where I had to find the number of 1's in the binary form of the product if 2 numbers A and B. The range of A and B was [0, 10^9] inclusive. Here is the code I wrote.
public class Solution {
public static void main(String[] args) {
// System.out.println(solution(32329,4746475));
System.out.println(solution(3,4));
}
public static int solution(int A, int B) {
// write your code in Java SE 8
long mul=A*B;
int ans=0;
while(mul>0)
{
if((mul%2)!=0)
{
ans ;
}
mul=mul/2;
}
return ans;
}
}
This worked fine for the input (3,4) but, when I tried (32329,4746475) as input instead the code didn't work and it showed 0 as answer. I put in a few output statements at different places to debug and found that with this input, the result of multiplication comes out to be -1170032381 (which is wrong) and therefore, the while loop's condition fails. So, I type-casted both A and B like so
long mul=(long)A*(long)B;
And voila it worked. Now, my question is why? Why did the code work fine for smaller inputs and flop for larger ones and shouldn't 'int to long' be implicit type casting in Java?
(I also tried a few other inputs so not all larger ones give negative as the product but they don't give the correct answer either, smaller ones I've tried till 5-digit A and B give the correct product)
CodePudding user response:
Java has automatic widening from int
to long
, but that happens at assignment, but the multiplication of an int
with another int
produces an int
, so you would get integer overflow first multiplying 32329
with 4746475
, then the widening of the overflowed int
result to long
.
However, if you first cast at least one of the int
to long
, then the multiplication is done using long
and the result is long
, so no integer overflow.
CodePudding user response:
Java int can store from
-2147483648 to 2147483647
32329 X 4746475 =153448790275
as Java does the multiplication before the implicit conversion the result is wrong