32 times bit shift operation in C with O(1) solution


  • 25
    Z

    we assure the factor ret's binary fomula is

    ret = a0 + a1*2 + a2*2^2 + ...... + a29*2^29 + a30*2^30 + a31*2^31; ai = 0 or 1, i = 0......31

    the dividend B and divisor A is non-negative, then

    A(a0 + a1*2 + a2*2^2 + ...... + a29*2^29 + a30*2^30 + a31*2^31) = B; Eq1

    (1) when Eq1 divided by 2^31, we can get A*a31 = B>>31; then a31 = (B>>31)/A;

    if (B>>31) > A, then a31 = 1; else a31 = 0;

    (2) when Eq1 divided by 2^30, we can get A*a30 + A*a30*2 = B>>30; then a30 = ((B>>30) - a30*A*2)/A; and (B>>30) - a31*A*2 can be rewritten by (B-a31*A<<31)>>30, so we make B' = B-a31*A<<31, the formula simplified to a30 = (B'>>30)/A

    if (B'>>31) > A, then a30 = 1; else a30 = 0;

    (3) in the same reason, we can get a29 = ((B-a31*A<<31-a30*A<<30)>>29)/A, we make B'' = B' - a30*A<<30, the formula simplified to a29 = (B''>>29)/A;

    do the same bit operation 32 times, we can get a31 ..... a0, so we get the ret finally.

    the C solution with constant time complexity

    int divide(int dividend, int divisor) {
        //special cases
        if(divisor == 0 || (dividend == INT_MIN && divisor == -1))
            return INT_MAX;
        
        // transform to unsigned int
        bool sign = (dividend > 0)^(divisor > 0);
        unsigned int A = (divisor < 0) ? -divisor : divisor;
        unsigned int B = (dividend < 0) ? -dividend : dividend;
        int ret = 0;
        
        // shift 32 times
        for(int i = 31; i >= 0; i--)
        {
            if((B>>i) >= A)
            {
                ret = (ret<<1)|0x01;
                B -= (A<<i);   // update B
            }
            else
                ret = ret<<1;
        }
        
        if(sign)
            ret = -ret;
        
        return ret;
    }

  • -1
    U
    This post is deleted!

  • 1
    F

    Fantastic solution, using unsigned int is a great idea. much better then long long.


  • 0
    O

    I like this idea


  • 0
    B

    Elegant solution, although it's difficult to understand at first. Thanks!


  • 0
    W

    Clear explanation´╝îthanks


  • 0
    L
    This post is deleted!

  • 0

    No need to claim this is O(1). (Logn)^2 can be regarded as O(1) as well.


  • 0
    D

    to be pedantic int is only guaranteed to be at least 32 bits. To work around this you can specify int i = sizeof(unsigned int) << 3


Log in to reply
 

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