Saturday, October 10, 2009

Using Bit Shifting to Divide / Multiply

To think of it, I rarely use bitwise operators in my coding - especially with all the convenience of other operators (can you imagine calculating bits whole day?).

But seriously when I was reading on Bitwise operators, I realised that ($n / 2) == ($n >> 1). So i tested out and...

By shifting bits, we can actually do multiplication and division. But however, this is only true when ($n / $x) is still a integer.


$n = 1600;

var_dump(($n / 2) == ($n >> 1));
var_dump(($n / 4) == ($n >> 2));
var_dump(($n / 8) == ($n >> 3));
var_dump(($n / 16) == ($n >> 4));

var_dump(($n * 2) == ($n << 1));
var_dump(($n * 4) == ($n << 2));
var_dump(($n * 8) == ($n << 3));
var_dump(($n * 16) == ($n << 4));


I ran some tests on which one is faster, and found that bitshifting is actually much faster.

Here are the results:
 Normal (seconds)Bitshift (seconds)
Mean0.124070.10461
Min0.1229791641240.104335069656
Max0.1260280609130.105180025101
Post to the testing script: http://thephpcode.pastebin.com/f1f6ec979

So when you do some simple math in programming, you know ways to speed things up.

3 comments:

Hongster said...

Hi, I think is it amazing for a 17 year old teenage to write technical blog. Keep it up!

Have you learn assembly programming? It is usually taught in 1 of the 1st year modules at University level. A normal multiplication and division may translate to more than 1 instruction for processor. For most processor, operations like XOR, left-shift, right-shift, rotation, take only 1 clock cycle. That makes it pretty fast.

I guess you have learn things like binary and hexadecimal representation in poly. Many students learn this, but they never get to use them often. I once wrote a Sudoku solver. An empty cell may have a maximum of 9 possible candidates (1 ~ 9). If I use an int[] array on each cell, it is going to consume a lot of memory for a 9x9 Sudoku game. I decided to use a 9-bits integer for each cell. Each bit indicates if a candidate is possible in this particular cell. Adding/removing possible candidates in each cell can be done using AND and OR operations.

thephpdeveloper said...

Hi Hongster

Thank you very much. Will continue to do so.

Nope I haven't learn Assembly Programming. I'm still in polytechnic and yep I've just learned about binary and hexadecimal representation last semester.

It's good practice to use them, sometimes they are much faster because the interpreter do not need to parse.

Hariharan s said...

Hi,I have studied about how bit shifting is used to divide/multiply in php.Thanks..

Theosoft