Why bitwise division does not work like bitwise multiplication?

user_9931829 0
Viewed 105

Suppose that I want to compute 20*10=200 using only bitwise shifting. This can easily done with

a = 20<<3 // 2^3
b = 20<<1 // 2^1
a + b // Result is 200.

Now, why if I try to do the same thing for division I get a wrong result? For instance if I try to compute 200/10

#include <stdio.h>

int main() {

    int value = 200;
    int a = value >> 3;
    int b = value >> 1;

    printf("200/10 is %d\n", (a+b));

    return 0;
}

I get a 125? What I'm doing wrong?

bit bit-manipulation c
3 Answers

The comments here have done a great job explaining why this doesn't work. Here's an elaboration a bit more on why the multiplication technique does work, and why the division technique doesn't.

Let's begin with multiplication. Suppose you want to compute 200 × 10. You could compute that by evaluating 200 × (9 + 1), or 200 × (8 + 2), etc. Each of those expressions is equivalent to the original one. Using the distributive property, this means we could compute 200 × 9 + 200 × 1 to get 200 × 10, or we could compute 200 × 8 + 200 × 2 to get 200 × 10, etc.

It just so happens that multiplying by powers of two happens to be done more easily by doing bitshifts. So, for example, we could compute 200 × 10 by evaluating

200 x 10 = 200 x (8 + 2)
         = 200 x 8  +  200 x 2
         = (200 << 3) + (200 << 1)

Now, can we do this for division? Well, it is indeed true that 200 / 10 = 200 / (8 + 2), same as before. But unlike multiplication, in the case of 200 / (8 + 2), we don't have a distributive property, so we cannot rewrite

200 / (8 + 2) = (200 / 8) + (200 / 2).

Therefore, we can't use the reverse of the bitshifting technique to quickly do the division.

user_5015570

I assume that efficiency is not a concern here, that it is just for fun (or a homework?).

As explained already, you cannot divide by 10 with bit shifting as easily as you can multiply by 10.

However, It is quite possible to use bit shifting for such a division, except that more shiftings are necessary.

For example, we can use the fact that 1/10 = 1/8 - 1/10 (1/4)

Output:

3/10 = 0
12/10 = 1
128/10 = 13
1465/10 = 147
4566/10 = 457
5674/10 = 567

#include <stdio.h>
int div10 (int n) {
    if (n == 0) return 0;
    return (n >> 3) - div10(n >> 2);
}

int main () {
    int nums[] = {3, 12, 128, 1465, 4566, 5674};
    int n = sizeof(nums)/ sizeof(nums[0]);
    for (int i = 0; i < n; ++i) {
        int num = nums[i];
        int ans = div10(num);
        printf ("%d/10 = %d\n", num, ans);
    }
    return 0;
}
user_105533410

You've gotten good answers, but allow me to offer another view of this that might be simpler. This was the multiplication:

a = 20<<3 
b = 20<<1 
a + b

And you wanted to do division like this:

a = 20>>3 
b = 20>>1 
a + b

The problem here is that you only have reversed the individual parts. You need to reverse the whole process. Let's take a simple example from temperatures. If you have a certain temperature c in Celsius and want to convert it to Fahrenheit, you do it with this formula:

f = 1.8c + 32

What you're trying is to convert back to Celsius with the same formula:

c = f/1.8 - 32

But since the addition was the last step in the original formula, we need to reverse that step before we reverse the multiplication. Here is the correct inversion:

c = (f-32)/1.8
user_66994330
Related