Different Division approach – Bit Wise

Welcome to my very 1st experiment. In this post i am about to explain why making use of BIT-WISE operators is much more useful in programming rather than using basic arithmetic operators for basic Multiplication , division or Module operator for the number “2”

Pre-requisites

Calculating run time : https://seriesofexp.wordpress.com/2012/04/06/runtime-calculation/
Bit Wise Operators : http://en.wikipedia.org/wiki/Bitwise_operation (In general)
http://en.wikipedia.org/wiki/Bitwise_operations_in_C (specifically for C/C++)

It has been seen that in competition , sometimes we have to divide or do basic operations on each element of HUGE arrays, and every-time applying arithmetic approach could be time consuming. So better to use Bit Wise operators, it uses less amount of clock cycles (1 or sometimes 2) rather than using arithmetic symbols (* , / , % etc) which consume 32 or 64 clock cycles. It could reduce your run-time by at most 3-4 times (Huge difference, isn’t it??)

Algorithm

• Division by 2 (Bitwise approach)
  1. X := Random_number
  2. Y := Right shift X by 1

  Now Y = X/2;

• Modulo (%) 2 (Bitwise approach)
  1. X := Random_number
  2. Y := X BITWISE AND 0001

  Now Y = X%2;

Now lets give it a try in C

y = x%2;   /*  Our basic approach  */
y = x & 0x01;   /*  Masking approach  */
y = x/2;   /*  Our basic approach  */
y = x >> 1;    /*  Shift Right Logical  */
y = x * 2;   /*  Our basic approach  */
y = x << 2;   /*  Shift Left Logical  */

Now here is an interesting property of Bitwise operations.

Let a number X = 2^n (P.S. its 2 power n NOT 2 XOR n)
So we can do almost all the basic arithmetic operations  (* , / , % ONLY) by using bitwise operators
Example :

1. A := Random_Number
2. B := Left shift A by n
3. C := Right Shift A by n

Now B contains (A*X) and C contains (A/X)
i am leaving upto you to figure how can you find A%X using masking

Lets move to our code and very 1st experiment

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
#define LIM 1000000
void mod_2(int * arr)
{
	int i , ans;
	for(i = 0 ; i < LIM ; i++)
	{
		ans = arr[i]%2;
	}
}
void mask_2(int * arr)
{
	int i , ans;
	for(i = 0 ; i < LIM ; i++)
	{
		ans = arr[i]&0x01;
	}
}
void div_2(int * arr)
{
	int i , ans;
	for(i = 0 ; i < LIM ; i++)
	{
		ans = arr[i]/2;
	}
}
void shift_2(int * arr)
{
	int i , ans;
	for(i = 0 ; i < LIM ; i++)
	{
		ans = arr[i] >> 1;
	}
}

int main(int argc , char **argv)
{
	struct timeval st , et;
	int i;
	int arr[LIM];
	for(i = 0 ; i < LIM ; i++)
	{
		arr[i] = rand()%100000;
	}
	gettimeofday(&st , NULL);
	mod_2(arr);
	gettimeofday(&et , NULL);
	printf("\nTotal time taken by function \"mod_2\" is : %lu seconds and %lu microseconds\n" ,  (et.tv_sec - st.tv_sec) , (et.tv_usec - st.tv_usec));
	gettimeofday(&st , NULL);
	mask_2(arr);
	gettimeofday(&et , NULL);
	printf("\nTotal time taken by function \"mask_2\" is : %lu seconds and %lu microseconds\n" ,  (et.tv_sec - st.tv_sec) , (et.tv_usec - st.tv_usec));
	gettimeofday(&st , NULL);
	div_2(arr);
	gettimeofday(&et , NULL);
	printf("\nTotal time taken by function \"div_2\" is : %lu seconds and %lu microseconds\n" ,  (et.tv_sec - st.tv_sec) , (et.tv_usec - st.tv_usec));
	gettimeofday(&st , NULL);
	shift_2(arr);
	gettimeofday(&et , NULL);
	printf("\nTotal time taken by function \"shift_2\" is : %lu seconds and %lu microseconds\n" ,  (et.tv_sec - st.tv_sec) , (et.tv_usec - st.tv_usec));
	return 0;
}

And the Output of above code is

Total time taken by function “mod_2” is : 0 seconds and 10435 microseconds
Total time taken by function “mask_2” is : 0 seconds and 9012 microseconds
Total time taken by function “div_2” is : 0 seconds and 24219 microseconds
Total time taken by function “shift_2” is : 0 seconds and 15340 microseconds

Well as you can see the difference and let us consider 5000 microseconds taken by for loop in each function. Thus the final values we will get are

Total time taken by function “mod_2” is : 0 seconds and 5435 microseconds
Total time taken by function “mask_2” is : 0 seconds and 4012 microseconds
Total time taken by function “div_2” is : 0 seconds and 19219 microseconds
Total time taken by function “shift_2” is : 0 seconds and 10340 microseconds

Hence the final conclusion is bitwise operators can decrease your runtime by at max 2 times

Thats all for today. Please don’t kill me if its freaking huge 😛