XOR Properties

XOR also known as Exclusive OR  is a logical operation operates on two operands which results in true only if one of the operand has a value true .

In Java,C++,C,C#  it is represented by ^.

In computer Science it is often used for bitwise operations.

               010  XOR 110 =100

               001 XOR 000=001

               111 XOR 111=000

               1010 XOR 1111 = 0101 

There are certain properties of XOR which accounts for its numerous uses.  ( I came to know some of them when I was trying to solve a problem in codechef. )

  • XOR operation is Commutative . A^B=B^A
  • XOR operation is Associative . (A^B)^C=A^(B^C)
  • XOR ing of same number is zero. A^A=0
  • XOR has zero(0) as the identity element. A^0=A

Here are some of the problems where XOR minimizes our effort.

  1. Swapping the numbers.
  2. Finding the number in the list which has odd parity.

1. Swapping

Swapping the numbers is very easy . There are many ways to do this

Method 1: 

int x=10,y=5,temp;
temp=x; // temp=10
x=y; // x=5
y=temp;  // y=10

Method 2:

int x=10,y=5;
x=x+y;   // x=15
y=x-y;   // y=10
x=x-y;  // x=5;

Method 3( Using XOR):

int x=10,y=5;
y=x^y; // 15
x=x^y; // 5(=y)
y=y^x;  // 10(=x)

How is it happening? and Why?

Recall the properties of XOR-

Merge  steps : y=y^x and x=x^y  as x=x^(y^x)

OR


x=x^(x^y) ; // ( As XOR is commutative)

OR


x=(x^x)^y; //( As XOR is associative)

OR


x=0^y=y; //(As A XOR 0=A)

Similarly


y=0^x=x;

2.  Finding the numbers having odd parity.

Example:

There is an array which contains 2n+1 elements in which there are n numbers having duplicates. Only one element is there which which is not paired. How we can find  that element ?

Method 1:

Count the occurrence of every (distinct ) element . If for any element count is 1 ,that is the required element.

Time Complexity- O(n^2);

Can we do better?

Ya, of course.

Method 2:


int result=array[1];  //assuming  array is 1 based

for(int i=2;i<=array.length;i++)

result=result^array[i];

result contains the required element.

If you follow the Use of XOR in Swapping  numbers  then you can easily understand why it is happening that result contains the required element.

Happy Coding!!! ūüôā

Something about Java

Introduction

With the advent of technical Civilization, where competition is the only survival maxim, JAVA is much ahead than its counterpart technologies.¬†Its flexibility is its power and ‘inheritance of legacy’ is buzzword among techno-savvy.

JAVA and C++ have much in common and indirectly depends on C.Java is a hot property of Sun Microsystem, thanks to its godfathers such as James Gosling,Patrick Naughton, Chris Warth, Ed Frank and Mike Sheridan.?

Advantages of JAVA

JAVA offers a number of advantages to developers.

  • Java is simple: Java was designed to be easy to use and is therefore easy to write, compile, debug, and learn than other programming languages.The reason that why Java is much simpler than C++ is because Java uses automatic memory allocation and garbage collection where else C++ requires¬†the programmer to allocate memory and to collect garbage.
  • Java is object-oriented: Java is object-oriented because programming in Java is centered on creating objects, manipulating objects,and making objects work together. This allows you to create modular programs and reusable code.
  • Java is platform-independent: One of the most significant advantages of Java is its ability to move easily from one computer system to another.The ability to run the same program on many different systems is crucial to World Wide Web software, and Java succeeds at this by¬†being platform-independent at both the source and binary levels.
  • Java is distributed: Distributed computing involves several computers on a network working together. Java is designed to make¬†distributed computing easy with the networking capability that is inherently integrated into it.¬†Writing network programs in Java is like sending and receiving data to and from a file.
  • Java is interpreted: An interpreter is needed in order to run Java programs. The programs are compiled into Java Virtual Machine code called bytecode.¬†The bytecode is machine independent and is able to run on any machine that has a Java interpreter. With Java, the program need only be compiled once,¬†and the bytecode generated by the Java compiler can run on any platform.
  • Java is secure: Java is one of the first programming languages to consider security as part of its design. The Java language, compiler, interpreter,¬†and runtime environment were each developed with security in mind.
  • Java is robust: Robust means reliable and no programming language can really assure reliability. Java puts a lot of emphasis on early¬†checking for possible errors, as Java compilers are able to detect many problems that would first show up during execution time in other languages.
  • Java is multithreaded: Multithreaded is the capability for a program to perform several tasks simultaneously within a program. In Java,¬†multithreaded programming has been smoothly integrated into it, while in other languages, operating system-specific procedures¬†have to be called in order to enable multithreading. Multithreading is a necessity in visual and network programming.

Disadvantages of JAVA

  • Performance: Java can be perceived as significantly slower and more memory-consuming than natively compiled languages such as C or C++.
  • Look and feel: The default look and feel of GUI applications written in Java using the Swing toolkit is very different from native applications.¬†It is possible to specify a different look and feel through the pluggable look and feel system of Swing.
  • Single-paradigm language: Java is predominantly a single-paradigm language. However, with the addition of static imports in Java 5.0¬†the procedural paradigm is better accommodated than in earlier versions of Java.


Difference between Java And C++

Why java is slow

The Real World

The moment you start using objects in your program, Java looses the potential
for optimization. This section lists some of the reasons why.

1. All Objects are Allocated on the Heap

Java only allocates primitive data types like int and double and object
references on the stack. All objects are allocated on the heap.

For large objects which usually have identity semantics, this is not a handicap.
C++ programmers will also allocate these objects on the heap.
However, for small objects with value semantics, this is a major performance killer.

What small objects? For me these are iterators. I use a lot of them in my designs.
Someone else may use complex numbers. A 3D programmer may use a
vector or a point class. People dealing with time series data will use a time class.
Anybody using these will definitely hate trading a zero-time stack
allocation for a constant-time heap allocation. Put that in a loop and that becomes
O (n) vs. zero. Add another loop and you get O (n^2) vs. again, zero.

2. Lots of Casts

With the advent of templates, good C++ programmers have been able to avoid casts
almost completely in high-level programs. Unfortunately, Java doesn’t have templates,
so Java code is typically full of casts.

What does that mean for performance? Well, all casts in Java are dynamic casts,
which are expensive. How expensive? Consider how you would implement a dynamic cast:

The fastest thing you could do is assign a number to each class and then have a
matrix that tells if any two classes are related, and if they are, what is the
offset that needs to be added to the pointer in order to make the cast.
In that case, the pseudo-code for the cast would look something like this:

DestinationClass makeCast (Object o, Class destinationClass) {
Class sourceClass = o.getClass (); // JIT compile-time
int sourceClassId = sourceClass.getId (); // JIT compile-time

int destinationId = destinationClass.getId ();

int offset = ourTable [sourceClassId][destinationClassId];

if (offset != ILLEGAL_OFFSET_VALUE) {
return ;
}
else {
throw new IllegalCastException ();
}
}
Quite a lot of code, this little cast! And this here is a rosy picture
-using a matrix to represent class relationships takes up a lot of memory and no
sane compiler out there would do that. Instead, they will either
use a map or walk the inheritance hierarchy – both of which will slow things down even further.

3. Increased Memory Use

Java programs use about double the memory of comparable C++ programs
to store the data. There are three reasons for this:

Programs that utilize automatic garbage collection typically use
about 50% more memory that programs that do manual memory management.
Many of the objects that would be allocated on stack in C++ will
be allocated on the heap in Java.
Java objects will be larger, due to all objects having a virtual table
plus support for synchronization primitives.
A larger memory footprint increases the probability that parts of the
program will be swapped out to the disk. And swap file usage kills the
speed like nothing else.

4. Lack of Control over Details

Java was intentionally designed to be a simple language. Many of the
features available in C++ that give the programmer control over details were
intentionally stripped away.

For example, in C++ one can implement schemes that improve the locality
of reference. Or allocate and free many objects at once. Or play pointer
tricks to make member access faster. Etc.

None of these schemes are available in Java.

5. No High-Level Optimizations

Programmers deal with high-level concepts. Unlike them, compilers deal
exclusively with low-level ones. To a programmer, a class named Matrix
represents a different high-level concept from a class named Vector.
To a compiler, those names are only entries in the symbol table.
What it cares about are the functions that those classes contain,
and the statements inside those functions.

Now think about this: say you implement the function exp (double x, double y)
that raises x to the exponent y. Can a compiler,
just by looking at the statements in that function, figure out that exp (exp (x, 2), 0.5)
can be optimized by simply replacing it with x? Of course not!

All the optimizations that a compiler can do are done at the statement level,
and they are built into the compiler.
So although the programmer might know that two functions are symmetric and
cancel each other now, or that the order of some function calls is irrelevant
in some place,
unless the compiler can figure it out by looking at the statements,
the optimization will not be done.

So, if a high-level optimization is to be done, there has to be a way
for the programmer to specify the high-level optimization rules for the compiler.

No popular programming language/system does this today. At least not
in the totally open sense, like what the Microsoft’s Intentional
Programming project promises.
However, in C++ you can do template metaprogramming to implement
optimizations that deal with high-level objects. Temporary elimination,
partial evaluation,
symmetric function call removal and other optimizations can be implemented
using templates. Of course, not all high-level optimizations can be done this way.
And implementing some of these things can be cumbersome. But a lot can be done,
and people have implemented some snazzy libraries using these techniques.

Unfortunately, Java doesn’t have any metaprogramming facilities, and thus high-level
optimizations are not possible in Java.

So…

Java, with the current language features, will never be as fast as C++. This pretty much means that it’s not a sensible choice for high-performance software and
the highly competitive COTS arena. But its small learning curve, its forgiveness, and its large standard library make it a good choice for some small and
medium-sized in-house and custom-built software.

Nested-Inner class in java

It is possible to define a class within another class.
The scope of the nested class is within the enclosing class.
There are two type of nested classes in Java.
The nested classes which are static are simply called the Nested classes
while the non-static ones are called Inner classes.
Example of Inner Classes.

class outer_class{
public static void main(String args[]){
outer_class outer_object=new outer_class();
}

inner_class inner_object=new inner_class();
int ffff=inner_object.z;

private int x;
public int y;
class inner_class{
void fn(){
x=10;
y=9;
}
private int z;
}

}

In inner classes even the private members of the enclosing class are
directly accessible to the enclosed class.And also the private members
of the enclosed class is accessable through the object of the enclosed class
in the enclosing class.
Note:Inner classes cannot have static members. Static declarations are
for top-level entities,or for the class as a whole, not an instance.
And also we cannot declare any static variable in any function.
Example of Static Classes.

class outer_class{

static class inner_class{

}

}

As it is the static class, we cannot access the members of the outer class directly.

So we have to access them using the object.

Note:There is no such modifier static for the class which is not enclosed
in another class

class dev{
public static void main(String args[])
{
deven.fn();//non-static variable this cannot be referenced
//from the static context
}
}

static class deven{ //Modifier static not allowed here

void fn(){
System.out.println("Deven");
}
}