Java bit operation based on positive dividing


  • 0
    S

    The pos_divide is a quite standard way of using bit operation to implement divide. To overcome the corner cases, the implementation is based on 64bit long.

    The main divide function handles the negative cases and corner values

    public class Solution {
        private long pos_divide(long a,long b) {
            long ans = 0,base = 1;
            for (long i = 63; i >= 0; --i) {
                if ((a>>i) >= b) {
                    ans += (base<<i);
                    a -= (b<<i);
                }
            }
            return ans;
        }
        
        public int divide(int dividend, int divisor) {
            if(dividend == 0)
                return 0;
            if(divisor == 0)
                return Integer.MAX_VALUE;
            long ans;
            if(dividend < 0) {
                if (divisor < 0) {
                    ans = pos_divide(-(long)dividend,-(long)divisor);
                }
                else {
                    ans = -pos_divide(-(long)dividend,(long)divisor);
                }
            }
            else {
                if (divisor < 0) {
                    ans = -pos_divide((long)dividend,-(long)divisor);
                }
                else {
                    ans = pos_divide((long)dividend,(long)divisor);
                }
            }
            if (ans >= Integer.MAX_VALUE)
                return Integer.MAX_VALUE;
            if (ans <= Integer.MIN_VALUE)
                return Integer.MIN_VALUE;
            return (int)ans;
        }
    }

Log in to reply
 

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