bitwise division by multiples of 2

Question

I found many posts about bitwise division and I completely understand most bitwise usage but I can't think of a specific division. I want to divide a given number (lets say 100) with all the multiples of 2 possible (ATTENTION: I don't want to divide with powers of 2 bit multiples!)
For example: 100/2, 100/4, 100/6, 100/8, 100/10...100/100
Also I know that because of using unsigned int the answers will be rounded for example 100/52=0 but it doesn't really matter, because I can both skip those answers or print them, no problem. My concern is mostly how I can divide with 6 or 10, etc. (multiples of 2). There is need for it to be done in C, because I can manage to transform any code you give me from Java to C.

Answer 1

Following the math shown for the accepted solution to the division by 3 question, you can derive a recurrence for the division algorithm:

To compute (int)(X / Y)

• Let k be such that 2^k &geq; Y and 2^k-1 < Y
  (note, 2^k = (1 << k))
• Let d = 2^k - Y

• Then, if A = (int)(X / 2^k) and B = X % 2^k,

  X = (1 << k) * A + B
    = (1 << k) * A - Y * A + Y * A + B
    = d * A + Y * A + B
    = Y * A + (d * A + B)
  

• Thus,

  X/Y = A + (d * A + B)/Y
  

In otherwords,

If S(X, Y) := X/Y, then S(X, Y) := A + S(d * A + B, Y).

This recurrence can be implemented with a simple loop. The stopping condition for the loop is when the numerator falls below 2^k. The function divu implements the recurrence, using only bitwise operators and using unsigned types. Helper functions for the math operations are left unimplemented, but shouldn't be too hard (the linked answer provides a full add implementation already). The rs() function is for "right-shift", which does sign extension on the unsigned input. The function div is the actual API for int, and checks for divide by zero and negative y before delegating to divu. negate does 2's complement negation.

static unsigned divu (unsigned x, unsigned y) {
    unsigned k = 0;
    unsigned pow2 = 0;
    unsigned mask = 0;
    unsigned diff = 0;
    unsigned sum = 0;
    while ((1 << k) < y) k = add(k, 1);
    pow2 = (1 << k);
    mask = sub(pow2, 1);
    diff = sub(pow2, y);
    while (x >= pow2) {
        sum = add(sum, rs(x, k));
        x = add(mul(diff, rs(x, k)), (x & mask));
    }
    if (x >= y) sum = add(sum, 1);
    return sum;
}

int div (int x, int y) {
    assert(y);
    if (y > 0) return divu(x, y);
    return negate(divu(x, negate(y)));
}

This implementation depends on signed int using 2's complement. For maximal portability, div should convert negative arguments to 2's complement before calling divu. Then, it should convert the result from divu back from 2's complement to the native signed representation.

Answer 2

The following code works for positive numbers. When the dividend or the divisor or both are negative, have flags to change the sign of the answer appropriately.

int divi(long long m, long long n)
{
    if(m==0 || n==0 || m<n)
        return 0;
    long long  a,b;
    int f=0;
    a=n;b=1;

    while(a<=m)
    {
        b = b<<1;
        a = a<<1;
        f=1;
    }

    if(f)
    {
        b = b>>1;
        a = a>>1;
    }

    b = b + divi(m-a,n);
    return b;
}

Answer 3

Use the operator / for integer division as much as you can.

For instance, when you want to divide 100 by 6 or 10 you should write 100/6 or 100/10. When you mention bit wise division do you (1) mean an implementation of operator / or (2) you are referring to the division by a power of two number.

For (1) a processor should have an integer division unit. If not the compiler should provide a good implementation.

For (2) you can use 100>>2 instead of 100/4. If the numerator is known at compile time then a good compiler should automatically use the shift instruction.