Saturday, December 30, 2006

Calculate n-1

Well the problem is : your input in 'n' and you have to calculate n-1 without using the '-' opertaor... simple one I guess

The solution I thought was:
/*
sum=0;
while(i < a="~0;" b="n+a;">

Quine

Have u ever come across a code that prints its own code as an output....

these type of codes are calle Quines... and here is a link containg many single liners .

but the most simple one in linux would be
int main()
{
system("cat filename.c");
}
I tried this code.. it compiled with a warning but executed...

Aneways there is in iterestiing link which gives the world's shortest quine... if u have two spare minutes, go throught it.. it would be interesting...

Scanf

very often we have encountered problems where a code fragment like
for(i=0;i<3;i++)> simple... the stray '/n' escape sequence remains in the input stream and is taken by the second scanf. One of the ways is to use a getc() function before second scanf, but not really good one other solution is to use fgets from stdin ... this is a nice solution as it takes the whole string from the input stream including '\n' note that we can't simply flush the input stream by fflush(stdin) as its behaviour on input stream is undefined... we can use it to flush the output stream..

Increment Operators

is the C statement /*printf("%d, %d, %d\n", i,i++,++i)*/ a valid statement?
Think hard before arriving to any conclusions....

Well its not!!

firstly ehat do u expect the evalution order of functions a(), b() and c() in the following statement
printf("%d,%d,%d",a(),b(),c());

well by the C standards the behaviour is *unspecified* i.e. the arguments of a function may be evaluated in any order that may also be interleaved.... now this unspecified behaviour of evalution of the arguments may lead to undefined behaviour and hence the ambiguous result.

Secondly there is no sequence point between the different expressions(i, ++i, i++) and according to C standards modifying the value of an expression more than once between two sequence points leads to undefined behaviour and hence explains the ambiguous result.

try printf("%d", (i++,++i)); note: there is a sequence point in the expression.

sizeof()

Well found something new about the sizeof()

firstly it is an unary operator and shouldn't be mistaken for a function

secondaly, what do you expect the output of
int i=10;
j=sizeof(i++);
printf("%d, %d",i,j);

well the value of i doesn't get incremented as sizeof is a compile time operator and produces a compile-time integer constant value. The expession inside sizeof() is only expected to deduce its type and is not fully evaluated.... should have known this though!!!!

also found a new thing today.... sizeof('x') returns 2 or 4 but not 1. This is because by definition, in C, character constants are integers and not characters!!!! I also found this somewhere that sizeof("") will give the size of char in both C and C++, but haven't tried it yet.

Also,
char chr[1000];
sizeof(chr) will give 1000 and not 4.

gets()

Well we all know that whenever we compile a file containing a refference to gets() function, the compiler gives a warning that using gets() might be dangerous.....

The reason is very simple... gets simply copies the input string on to the program stack without inpecting its size... for example the code...
void enterstring()
{
char string[FIXEDLENTH];
gets(string);
}
now when the function is called then the space for the local variable string gets allocated in the program stack. If the length of the input is now greater than the FIXEDSIZE then the stack gets over written... but how this is dangerous???

Well one can very easily modify the flow of control in a program by just buffer overflow... consider for example... when the function enterstring was called then the stack contains the return address in to the main function.. now I could input the buffer in such way such that my buffer contains a malicious machine code and also changes the return address in the stack to a position in the buffer from where my malicious code starts... bas ho gaya kam.... or even if you cant write a machine language code in the buffer than also you could change the return address and thereby modifying the program execution...

I have a very interesting link which gives the above task as an lab assignment!!!!! Its really COOL have a look.... and for those who really wanna hack theres an another link .

string inside scanf()

what will the following statement do???

scanf( " %d %d" + scanf("%d %d",&i,&amp;j) ,&a);

the inner scanf will take two integers as input and storing them in i and j respectively and returning 2.

the outer scanf's expression will now become "%d %d"+2 which will become " %d".... how??? now the expression inside the " " in scanf in considered as a string and is stored in some part of the memory and when we call the scanf function then a pointer to this memory location is passed on to scanf... but in this case the pointer gets incremented by two and thus points to the string " %d" rather than "%d %d", and since the former one is a legitimate expression for scanf the function takes one input in a.

not a big deal

what would be the output of the following code statement

main(_){for(--_;putchar(_++["J!Mpwf!Zpv\1"]-1););}

think, think.....

Well the output is "I Love You" :-)

How?? It goes as follows: firstly the underscore in the main is a variable equivalent to argc but I cant understand thet why the code doesn't give warning in the main, beacuse either ir should have both the arguments of main in it or none of them....anyways since we run the program by the command ./a.out the argc value is 1 and hence '_' is initialized to 1
going further in the for loop the variable _ gets its inital value 0. Now there is something important to understand... a[i]=*(a+i)=*(i+a)=i[a] thus in C it doesn't matter that what is the base and waht is the subscript.... thus the *thing* inside the putchar can be understood as arbitString[_++]-1 which goes on printing the the elements of the string -1 which comes out to I Love You and stops when the string ends.... simple... isn't it.

P NP

Well I have always been consufed with NP, P CO-NP and all such funda.... so today decided to get the basic funda clear about this:

NP: It is the class of problems that can be solved by non deterministic finite automata by making a polynomial number of guesses and the solution can be verified in polynomial time.

P: is a set of problems that can be solved in an polynomial time thus concluding that if a problem is P then it is NP

now the question comes that whether NP=P.... the answer to this is uncertain as P is the class of problems that can be solved "easily" in polynomial time while NP is a class of problems that can be varified in a polynomial time and hence they are considered to be different.

NP - complete: a problem is said to be NP - Complete if it is NP and every other NP problem can be reduced to it in polynomial time.... now its significance is that to show how hard a particular problem is: i.e. we can prove that for a particular problem no polynomial time algorithm exsists by contradiction if we reduce a problem for which no polynomial time solution exsists to it in polynomial time.... and finally if for any NP complete problem we find a polynomial time algorithm then since all the NP problems are reducible to it, all of them will have a polynomial time solution and hence NP class will now become equivalent to P and thus existance of NP complete problems is a factor which makes people believe that NP != P....

finally if a problem is not NP but all the NP problems are reducible to it in polynomial time then it is known as NP- hard.... which implies that a NP hard problem is atleast as hard as any other NP problem, infact it might be harder.



Memory Leak

In simple terms memory leaks may be defined as the loss of any memory allocated during the program... for a more precise and informative defineation refer here.

A very simple code exhibting memory leak:

int main()
{
int *p,q;
p=(int*)malloc(sizeof(int));
q=10;
p=&q;
printf("the value of p=%d",*p);
}

in the above case the memory allocated to p is lost in line number 6 and may be considered as a memory leak.

Goto

It has always been suugested to not use Goto in our programs, instead use for while and other stuff like it. why??

firstly, using goto may insert labels into the program and when we encounter a label at a particular place in the program, it becomes very difficult to say from where might have the control landed up there. It makes the understanding of the difficult and hence the debugging gets even tougher.

secondly, using constructs like for, while makes the program somewhat structured and its easy to trace the flow of control withinn the code... also using these constructs maps the code to real world scenario where a conditional statement may be represented as an decision and a for while may be regarded as repeating sometimes over and over.... but what does Goto represent in real world scenario??

Thirdly, making use of too much Goto may result in speghetti code . There is also a story associated with goto. have a look.

Twelve days of Christmas

This is my fisrt post about obfuscated programming and this stuff seems to be amazing...... at first when I saw this code , I was amazed to see its output ..... kaise ho sakta hain yaar... Then finally found the solution to it... and it was really nicely explained and dealt with... and about the author of the code... he might be a real genius I might say....

During the study of how the program works, I learned about listed expressions and how the value of the whole expression becomes that of the last expression. Aneways the links are nice going through if you have some time.

Puzzle

consider the following code fragment:

void fun()
{
}

int main()
{
int i=10;
fun();
printf("%d\n",i);
}

Now the task is to write something in function fun() such that main prints any other value than 10.... note that the value is to be printed in main()
think.....

Well the answer is as follows:
void fun()
{
#define printf(a,b) printf("20\n")
}
simple... isn't it :-)

To find the greater of two number

Yes, but without using comparison operators!!!!

the first solution came from Mayank... which was:

int max(a,b)
{
if(a/b)
return a;
else return b;
}

The above would not work if b=0... now the second one came from Muneish which was:

x=(a-b)/|a-b|

if(x+|x|)
return a;
else return b;

Now this one is also wrong since a-b could cause overflow...
Well the correct solution goes as follows:

void compare (int a, int b)
{
int diff, msb;

msb = 1 << (sizeof(int)*8 - 1);

if ((a & msb) &amp;& !(b &msb)) /* a is negative and not b */ return b; else if ((b & msb) &amp;amp;amp;amp;amp;& !(a &msb)) /* b is negative and not a */ return a; /* a and b are of same sign */ diff = a-b; if (!diff || !(diff & msb)) /* a==b and a > b */
return a;
return b;
}

I have shamelessly copied this code from Joju John, but was worth the search... A point to be noticed is that msb and diif variables are taken as int but you have to make there types as same as that of a and b.

Puzzle

You are given an array with n elements { x1, x2 ... xk ... xn }. You are also given an array location k. Using constant space and O(n) time, rotate the array such that it contains { xk, xk+1 ... xn, x1, x2 ... xk-1 }.

Well the first thoughts which came to my mind were those involving swapping the elements and one can also achieve the solution this way, but its not the best way. The best way out is as follows:

We know that reversing of a list can be done in constant time. Thus do as follows:
1.reverse the list from x1 to xk-1 {xk-1, xk-2, ....., x1, xk, ...... , xn}
2.reverse the list from xk to xn {xk-1, xk-2, ....., x1, xn, ......., xk}
3.reverse the whole list {xk, xk+1, ..... xn, x1, x2, ......., xk-1}

Nice na!!!!

Simple One

Consider the following program
#include
void main()
{
if(.....)
printf("AB");
else
printf("C");
}
Q: fill in the blank within if condition so that o/p is ABC

here is ans

if(!printf("AB"))
------
else
----


:)

Pointers and Reference

Although they look the same but have major differences. These are said to be valid in C++. I don't know about C. The info can be found here.
Also we may say that pointers consume memory but references may be thought of as alias for an object and thus having no memory consumption butI not 100% sure on this point.

String Constants

char *a = "abc";
a = "def";

The above is correct but the code crashes when we do a[1] = 'd';

This may be because actually when we say char * a ="abc"; then it means a is pointing to a const memory location which contains "abc" and when we say a= "def"; its again modifying pointer's value to be now pointing to some other constant location; but when u\we say a[1]= 'd' then we are modyfying a const so it crashes!
C doesnot defines behaviour when you chnage a string literal that is why it is crashing.You will end up getting different results with different compilers or on diff machines too.

Padding

static struct
{
unsigned char **segment;
unsigned int *reg1;
unsigned int *reg2;
int offset;
int offset16;
int pad[3]; /* Make structure power of 2 bytes wide for speed */
} ModRMRM[256];

wat is d significant of pad[3]????
how it become fast if structure is of power 2???



ou are taking array of structures...
so for that say u have to access jth element of array ..u do it by array[j] ...how does ur compiler do it is array+j*size of (that is *array) right!!
so if sizefo struct if power of 2 then the multiplication can be speed up by just doing shifting of bits ..accessing array elements by subscript is quite frequent...thats why this practice gives a lot of performance speedup

Size of a Datatype

how to find the size of any datatype in c ,without using sizeof operator and also without using the technique of bitwise operator?

U can use this technique

#define MY_SIZE(p) ((char *)((&p)+1)) - ((char *)&p)

The problem with this is u have to pass the variable and can't directly use as sizeof(int).

Reverse an Array

An array of size N has distinct values 1…N in random order. You have only operator called rev(X) (where X is any value from 0 to N-1) which reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets you 1,3,2,4). Our objective is to sort the array using minimum number of Rev(X) functions. How many permutations of N size array require exactly N number of rev(X) operators to get sorted?

My answer is,
1) find out max num. in an array say position i, use rev(i) and after use rev(N).
2) repeat above step by decreasing N by one each time

More Efficient

which is more efficient of these two
FOR LOOPS

for(int i=0;i<10;i++);
for(int i=0;i<10;++i);

Post increment is less efficient that Pre because in former the value is first updated and then a temporary variable having the previous value is returned. See this.

Anyways for(int i=10; i>0; --i) is the most efficient this is more efficient bcoz in this case ur comparing i with 0 rather than pre stored value(10) which takes some more operations wher as comparision with 0 can be easily done by comparing with a logical value 0.

without "" in printf

can u print any string wthout using " " in printf function?

without using " " anywhere in the program

#define str(a) #a

printf(str(Hi there));

I haven't figured out how this happens , but happens for sure!

without main

Although its not possible to write a program without main() but still it may be possible that main() is not present explicitly... as follows:

#include
#define decode(s,t,u,m,p,e,d) m##s##u##t
#define begin decode(a,n,i,m,a,t,e)
begin()
{
printf("Stumped??\n");
}


But main() is indirectly present.

Integer Limits

Any way to get the limits of an integer using a code?

There are two ways:

1.Simpler one

#include
#include
int main()
{
printf("Range of int: %d to %d\n", INT_MIN, INT_MAX);
}

2. Another One

upper_limit=(~(0u)>>1);
0u
fill in all 0s in the register so it looks like 000...000 (represented as MSB...LSB)
~(0u)
Now, flip all bits so it looks like 111...111
~(0u)>>1
Shift right one bit so that MSB is zero
011...111 which is maximum positive number that you can represent.

for lower range:
lower_limit=( (~0)^(~0u>>1)) (or lower_limit = ~upper_limit) logic flips 011...111 to 100...000 which is the lowest number presentable.

Maximal Munch

How is the expression x+++y parsed? As x++ + y or x + ++y ? Why?

The issue is with tokenization. The ANSI C standard requires that the longest possible sequence of characters be considered as a token. + and ++ are both valid tokens. When a +++ is encountered , the longest possible token is the ++. So, +++ is tokenized into ++ +.

On a similar note, x+++++y is always tokenized as x ++ ++ + y, and gives a syntax error. This is inspite of the fact that the tokenization x ++ + ++ y would not have an error.

This 'oddity' is known as the "maximal munch" principle.