31 lines
1.1 KiB
Rust
31 lines
1.1 KiB
Rust
|
// Assume shift operators are allowed
|
||
|
|
impl Solution {
|
||
|
|
#[inline]
|
||
|
|
pub fn negative(n: i32) -> i32 {
|
||
|
|
if n.is_positive() {
|
||
|
|
return !(n - 1);
|
||
|
|
}
|
||
|
|
n
|
||
|
|
}
|
||
|
|
pub fn divide(dividend: i32, divisor: i32) -> i32 {
|
||
|
|
let positive = dividend ^ divisor >= 0;
|
||
|
|
let negative_divisor = Solution::negative(divisor);
|
||
|
|
let negative_answer = (0..negative_divisor.leading_ones()) // Preform all arithmetic in negative because of larger available range of numbers
|
||
|
|
.rev() // Reverse to get most extreme subdivisor first
|
||
|
|
.map(|n| negative_divisor << n) // Generate subdivisors
|
||
|
|
.fold((0, Solution::negative(dividend)), |(quotient, carry), subdivisor| {
|
||
|
|
if subdivisor >= carry {
|
||
|
|
return ((quotient << 1) - 1, carry - subdivisor);
|
||
|
|
}
|
||
|
|
return (quotient << 1, carry);
|
||
|
|
}).0;
|
||
|
|
if positive {
|
||
|
|
let answer = !negative_answer;
|
||
|
|
if answer != std::i32::MAX {
|
||
|
|
return answer + 1;
|
||
|
|
}
|
||
|
|
return answer;
|
||
|
|
}
|
||
|
|
negative_answer
|
||
|
|
}
|
||
|
|
}
|