Code for Factorial, without Recursion

After having been declared to be an impregnable procrastinator by all my close-circle friends, after being connoted to update it by those who I didn't even know were reading my blog and after being told "Enough is enough, now update it buddy" by a few friends, I am in the same situation as the Indian government after the Mumbai attacks. I have no other go than updating it, at least for the sake of hushing them up till the next terror attack near my house. So here I go...

As you might already be knowing, I prefer calling programming an art to calling it a process. That's the reason I enjoy it.

Coming to the point, my friend cum colleague was trying to write a program for generating Pascal Triangle. I decided to play along and wrote a code. In the process, I wrote a function to calculate factorial for a number in an unusual way, without recursion.

Generally an incremental loop is used from 2 to N. But I used decrementing loop and here is the outcome (Code written in C programming language):

unsigned int fact(unsigned int n)
{

unsigned int f=n;

while(n---2)

f*=n;

return f;

}

Main thing I wanted to convey in this code is the while loop, which uses the unusual "--" & "-" operator pair.

It works similar to this loop:

for(f=n;n>=2;n--)

f=f*n;

Not a great piece of code, but I found it to be a little interesting. Hence the post.

One-liner ABS Function using Binary Operators

A few days ago, my friend TJ, who always keeps finding innovative programming challenges, asked a question: "Can you implement abs() function without using any relational operators in C?". But he also insisted to do it without using if, for, while etc., any control and loop structures for that matter.

I immediately came up with this:

abs_x = sqrt(x*x);

But he is not a guy to get contented with such an answer. He told that sqrt() internally uses relational operators in its implementation. Well, true. The sqrt() function that is included in math.h uses series expansion methods, which use if() statement in one or the other way. So I had no choice but to find some other way. After struggling a lot, I came up with this which uses only binary operators and arithmetic operators:

abs_x = (x^((((x&(1 << (sizeof(int)*8-1))) >> (sizeof(int)*8-1)&1)*-1)) + (((x&(1 << (sizeof(int)*8-1))) >> (sizeof(int)*8-1))&1);

The sizeof() opeator is necessary only to generalize the expression for any size (16 bit or 32 bit) of the integers. Otherwise a smaller version of the same would suffice.

For 32 bit integers:

abs_x = (x^((((x&(1<<31))>>31)&1)*-1))+(((x&(1<<31))>>31)&1);

or

abs_x = (x^((((x&0x10000000)>>31)&1)*-1))+(((x&0x10000000)>>31)&1);

For 16 bit integers:

abs_x = (x^((((x&(1<<15))>>15)&1)*-1))+(((x&(1<<15))>>15)&1);

or

abs_x = (x^((((x&0x1000)>>15)&1)*-1))+(((x&0x1000)>>15)&1);

Does it seem complicated? As we know, in C, numbers are represented in Two's Complement method. In 2's complement method of representation, the most significant bit represents the sign of the number. This bit will be 0 if the number is positive and 1 if it is negative.

The idea is to first check the most significant bit of the number. If it is 1 we need to negate the number. To negate a number, we should find the one's complement the number and add 1. That is what is done in the above expression!!

Do you think it's a great piece of one-liner code? It would have been, if it was impossible to simplify it further like swapping code posted before. Yes! It can further be reduced! Look at this code:

abs_x = x*(-2*(((x&(1<<(sizeof(int)*8-1)))>>(sizeof(int)*8-1))&1)+1);

For specific length, it looks like (for 32 bit integer):

abs_x = x*(-2*(((x&(1<<31))>>31)&1)+1);

All this code does is to multiply the original number with -1 if it is negative and with 1 if it is positive! Short and sweet one-liner, isn't it? But I can't say it's the shortest like I did in my earlier post. Feel free to express your opinions!

UPDATE
I guess thinking a lot certainly helps! I was able to find a still shorter one-liner!!

abs_x = x+2*x*(x>>(sizeof(int)*8-1));

Can I say this is the shortest? I still doubt!!

Exploring new ways

If you have ever been to programming, you will surely have been asked to write a program to swap two numbers (If you haven't bothered about this simple program, you need not have to continue reading this article). Even if you are not well versed with the concept of programming, you will be able to solve this problem in one or the other way. Well, that's good. But I am trying to do much more than that, something that involves the combination of knowledge, thinking and understanding. I will go on describing about it in C language, since that's the language I like and that's the language I speak!!

Let's get down to the business here. If you ask anyone to swap two numbers, he might do it in this way:

temp = a;
a = b;
b = temp;

That's right. But it needs one more variable, temp. So, let us think and find some other way that needs no extra variable. If you know simple arithmetic, you might come up with this way:

a = a + b;
b = a - b;
a = a - b;

Let us see how the above code works.. For example, if a = 5, b = 7 then a = a + b; makes a = 12. The next statement b = a - b; makes b = 5 and the final statement a = a - b; makes a = 7. As we see, the values of a and b are interchanged. Our goal is achieved. Wow, the extra variable is eliminated! But there is one more concern here. It uses addition operations instead of mere assignments as in the previous case. Yeah, but what's the problem with that? you might ask. Well, there is, and you will notice it if you know how the microprocessors calculate. Addition is not a logical operation. It is an arithmetic operation. It is a combination of Exclusive OR (XOR) operation and AND operation. (Although ALUs of modern processors take care of this and do the operation in same amount of time as that needed for individual XOR or AND operations, I am not going to stop here, I'm here to explore new ways!). So, is there any way of still improving this? Yes, there is...

Now, if we can somehow eliminate this combinational operation of XOR and AND, we can achieve some more efficiency. For that one needs the knowledge of bitwise operations and obviously needs to know binary arithmetic. Assuming that you know it, here is the way:

a = a ^ b;
b = a ^ b;
a = a ^ b;

Going back to the same previous example of a = 5 (0101b), b = 7 (0111b) we get a = 2 (0010b) after the execution of the first statement. And after the second statement gets executed, we will have b = 5 (0101b) and after the execution of the third statement, we will finally have a = 7 (0111b) which is what we need.

Hmm, think it is the optimum, don't you? But I don't think so... If you know C, you will know that C provides shorthand operators. So, how about this:

a ^= b;
b ^= a;
a ^= b;

Well, now no one can further compress it. Eh, you think that? Remember, C provides the provision to put multiple assignments in a single statement and the operations are carried out from right to left. So, I come up with this, which is nothing but the merging of the above three statements, which I think, is the optimized one.

a ^= b ^= a ^= b;

If you find any piece of code that beats it, let me and the rest of the world know...