Bitshift division

Advertisemen

I had the sudden urge to test to see how much quicker dividing an integer n, by 2.

Method 1: half_n = n/2;

Method 2: half_n = (n >> 1);

I expect method 2 to be quicker, though it will only work with integers.

Code for test:

#include <iostream>

#include <ctime>

#include <string>

#include <stdint.h>

using namespace std;

#define __STDC_VERSION__ = 199901L //for int64_t

int main()

{

       clock_t st,et;

       int64_t n;

       //bitshift division

       st = clock();

       for (int64_t i=0;i<1000000000;i++)

              n=i>>1;

       et=clock();

       cout << et-st << endl;

       //operator division

       st = clock();

       for (int64_t i=0;i<1000000000;i++)

              n=i/2;

       et=clock();

       cout << et-st << endl;

       return 0;

}

The normal method, operator division runs in 12159ms, while the bitshift division runs in 3504ms, Bitshift division is nearly four times quicker!

This should also be the same with multiplication (and a left bitshift):

#include <iostream>

#include <ctime>

#include <string>

#include <stdint.h>

using namespace std;

#define __STDC_VERSION__ = 199901L //for int64_t

int main()

{

       clock_t st,et;

       int64_t n;

       //bitshift division

       st = clock();

       for (int64_t i=0;i<1000000000;i++)

              n=i>>1;

       et=clock();

       cout << et-st << endl;

       //operator division

       st = clock();

       for (int64_t i=0;i<1000000000;i++)

              n=i/2;

       et=clock();

       cout << et-st << endl;

       return 0;

}

 

The normal method runs in 4143ms, and the bitshift runs in 3501ms. Still a save of over 10%!

I've also come to wonder if there's anyway to replicate the modulus operator using bitshifts...

From this article it shows modulus operations being done. But they can only be done when you are dividing by a number that belongs to the range

f(x) = 2^x where x is an integer 

i.e. any power of two: 2,4,8,16,...

An example:

#include <iostream>

using namespace std;

int main()

{

       int a = 6;

       int n = 4; // 4 = 2^2, so can be done using bitshifts

       int m = a % n;

       int m_bit = a & (n - 1);

       cout << m << endl << m_bit << endl;

       return 0;

}

 m and m_bit are both displayed as 2 on the screen, I'll now do a speed test:

#include <iostream>

#include <ctime>

#include <string>

#include <stdint.h>

using namespace std;

int main()

{

       int a;

       int n[] = {2,4,8,16};

       clock_t st,et;

       //regular method

       st=clock();

       for (int x = 0; x < 4; x++) //different mod values

              for (int64_t i = 0;i < 2500000000;i++)

                     a = i%n[x];

       et=clock();

       cout << et-st << endl;

       //bitshift method

       st=clock();

       for (int x = 0; x < 4; x++) //different mod values

              for (int64_t i = 0;i < 2500000000;i++)

                     a = i&(n[x]-1);

       et=clock();

       cout << et-st << endl;

       return 0;

}

The regular method takes 114832ms and the bitshift method takes 25912ms, that's a save of over 75%!! It's a shame that the bitshift method only works with mod 2^n values. Actually, maybe it's not, else brute forcing encrypted data might go a little faster and therefore be used by many more people and our data wouldn't be safe.

Advertisemen