3

Division using bitwise operators

I spotted a post on stackoverflow and saw this bizarre method to divide by 3 (What's the fastest way to divide an integer by 3?).
It says that: n/3 = (n * 0x55555556) >> 32. That is multiply by 0x55555556 and take the most significant 32 bits. This is true for n being a 32 bit number.
As I began digging the logic behind it I realised that this can be generalized. For instance if we consider n < 128; i.e. 7 bit wide then:
n/3 = (n * 0x56) >> 8. So what's happening here ? Well, 0x56 = 86 = (258/3) and 258 is the first number bigger than 256 which is divisible by 3. Now,
2n = 258n - 256n
==> n = 129n - 128n for any n;
But if restrict n < 128; then 129n - 128n is same as quotient of (129n/128).
==> n = 129n/128; n < 128
==> n/3 = 43n/128; for n < 128
==> n/3 = 86n/256; n < 128
==> n/3 = (n * 0x56) >> 8;

It is amazing how this can be generalised to other divisions. For instance consider division by 5:
4n = 260n - 256n ==> n = 65n - 64n for all n
If n < 64; n = 65n/64
==> n/5 = 13n/64; n < 64
==> n/5 = (13 * n) >> 6;
similarly, n/5 = (52 * n) >> 8; n < 64

We can proceed on the same lines and derive that:
n/5 = 205n/1024 = (205*n) >> 10 for n < 1024

So; I tried to find a general rule to find n/a for any a ?
first find some power of two (say 2^m) which is one short of multiple of a (like 1024 in case of a = 5);
i.e. 2^m + 1 = ka; for some k
So the job is to figure out k while keeping m fixed (say 32) from: 2^m + 1 = ka. There can be multiple solutions to this; once m is fixed there will only be one.

Then; n/a = k*n >> m; for all n < 2^m

Now is this the way compiler works ? Using the formula generator provided by kol in one of the comments:
keeping m=32 and n=12; the formula generator gives:
a=3: n/3 = (1431655766 * n) >> 32
a=5: n/5 = (858993460 * n) >> 32
a=7: n/7 = (613566757 * n) >> 32

However, when I see my assembly output I get 1431655766, 1717986919 and -1840700269 respectively for dividing by 3, 5 and 7.
Moreover, if I change the data type to unsigned int then I get -1431655765, -858993459 and 613566757 respectively for 3,5 and 7.

As you can see; my prediction for divide by 3 is bang on but it fails for 5 and 7. it is interesting to see how closely they are related; but I am unable to explain it
Where have I went wrong in analysing what compiler does while dividing ?
The code from formula generator (by kol): 
var $a = $("#a"),
$m = $("#m"),
$generate = $("#generate"),
$formula = $("#formula");

$generate.click(function () {
var a = +$a.val(),
    m = +$m.val(),
    m2 = 0,
    k = 0;

if (isNaN(a) || a !== Math.floor(a) || a < 2 || a > Math.pow(2, 31) - 1) {
    alert("Divisor \"a\" must be an integer between 2 and 2^32-1");
    return;
}
m2 = Math.pow(2, m);
k = Math.ceil(m2 / a);
$formula.html("<i>n</i> / " + a + " = (" + k + " * <i>n</i>) &gt;&gt; " + m + "; for all <i>n</i> &lt; " + m2);
});

$generate.click();
Community
  • 1
  • 1
Nikhil Vidhani
  • 709
  • 5
  • 11
  • 3
    It may well be interesting, but it's not a question, so it doesn't belong here - voting to close. Please see: http://stackoverflow.com/help/on-topic – Paul R Sep 11 '14 at 08:11
  • 3
    Note also that these is a whole section on this topic in the excellent book: [Hacker's Delight](http://www.hackersdelight.org) – Paul R Sep 11 '14 at 08:13
  • Interesting, but neither programming nor a question up there !! – chouaib Sep 11 '14 at 08:17
  • 1
    "So the job is to figure out k and m satisfying: 2^m + 1 = k*a." - I think you meant this: Given a and m, the job is to figure out the smallest k where 2^m < k*a. – kol Sep 11 '14 at 09:38
  • 2
    Here is a formula generator: http://jsfiddle.net/L50pjduk/ – kol Sep 11 '14 at 09:40
  • @PaulR well I thought we can discuss a cool algorithm/approach here as well. Anyways will be more careful about questions next time :). BTW thanks for sharing the book's info. – Nikhil Vidhani Sep 11 '14 at 09:55
  • @kol did u just created that ? its pretty good! And yes, it can be stated like that but as I said there can be many solutions. It makes sense to look for the minimal k. For the example above; both shall work: (n/5) = (205*n) >> 10; n < 2^10 (n/5) = (3277*n) >> 14; n < 2^14 – Nikhil Vidhani Sep 11 '14 at 09:59
  • Yes, I was waiting for someone and had some time... I'd like to use this approach in the future, so the generator will come in handy :) – kol Sep 11 '14 at 10:28
  • @PaulR does this seem a valid question now ? – Nikhil Vidhani Sep 11 '14 at 13:20
  • @NikhilVidhani: well I can see that there is a question now, at least - I'll vote to reopen and we can see if others agree as to whether it's a good question... – Paul R Sep 11 '14 at 13:41
  • 1
    @PaulR thanks a lot for pointing me to that book. There was a question of bit reversing which I have been looking for days and I found it there in ch.7. Very nice book indeed. – Nikhil Vidhani Sep 15 '14 at 15:37
  • 1
    @NikhilVidhani: glad you liked it - I find that it's one of the most useful books on my computer book shelf. If you like this kind of stuff then you probably want to bookmark [this page](http://graphics.stanford.edu/~seander/bithacks.html) too. – Paul R Sep 15 '14 at 15:52

1 Answers1

2

No, the C compiler doesn't do arithemetics with bitwise operations. You don't have to do arithemetics with bitwise operations even in assembly. Sure, it works this way down at the processor, and the processor provides the commands described here: http://en.wikibooks.org/wiki/X86_Assembly/Arithmetic as abstractions for these operations.

  • 1
    Current C compilers don't -- but there was a time `div` was positively *aggressively* avoided, using this and some other methods. – Jongware Sep 11 '14 at 17:32
  • @Jongware: this is very interesting, I never knew this. I wonder why did they ever decide to do so since this arithmetics-via-bitwise-operations are supposed to work significantly faster in the processor where it's "built-in". –  Sep 11 '14 at 18:06
  • Well, precisely for that reason: the built-in `div` was *slow*. You can probably find (old!) datasheets with the timings for, say, an original 8086. On another note: not all CPUs have a `div` instruction. My Sinclair Spectrum (Z80) didn't and neither my Archimedes (RISC ARM2 or 3 or so). – Jongware Sep 11 '14 at 18:11
  • @Jongware: wow! What about other arithmetic operation commands? Did their built-in processor implementation also work more slowly than an emulation? –  Sep 11 '14 at 18:17
  • 1
    Multiplication would also be avoided where possible -- i.e., preferring 2 bit shifts and an addition over a single `mul 320`. `mul` and `div` are the only instructions I can recall of which it was recommended not to use. – Jongware Sep 11 '14 at 20:31