-
Notifications
You must be signed in to change notification settings - Fork 55
/
Power of XOR in Programming
50 lines (41 loc) · 3.48 KB
/
Power of XOR in Programming
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Power of XOR in Programming: http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/xor.html
PLEASE READ THE CONTENT IN THE ABOVE LINK BEFORE SOLVING THE BELOW MENTIONED QUESTIONS:
ALWAYS REMEMBER NUMBERS ARE STORED IN REGISTERS IN PROGRAMMING
XOR Properties: (Source: http://en.wikipedia.org/wiki/Exclusive_or)
I. Commutative: YES (i.e. a XOR b XOR c = b XOR a XOR c = c XOR a XOR b and all possible combinations are true for
any number of operands)
PRACTICAL APPLICATION: Because of this property, we could solve the "find missing number" problem mentioned below in point(3).
II. Associative: YES (i.e. a XOR (b XOR c) = (a XOR b) XOR c
1. Swap two numbers without using temp variable:
http://www.geeksforgeeks.org/swap-two-numbers-without-using-temporary-variable/
2. Detect if two numbers have different signs
http://www.geeksforgeeks.org/detect-if-two-integers-have-opposite-signs/
3. Find a SINGLE MISSING NUMBER in an array where array elements are SEQUENTIAL STARTING FROM 1 to n
(PLEASE note, only applicable for SINGLE missing number in an array where array elements are SEQUENTIAL STARTING FROM 1 to n)
http://www.geeksforgeeks.org/find-the-missing-number/
My Implementation: https://github.com/nkatre/Opearations-Variants-in-an-array/blob/master/Find%20Single%20Missing%20Number
4. Compute absolute value of integer
http://www.geeksforgeeks.org/compute-the-integer-absolute-value-abs-without-branching/
BEFORE YOU GO AHEAD WITH THE ABOVE PROBLEM, PLEASE UNDERSTAND THE FOLLOWING:
a. https://github.com/nkatre/Learning-Java/blob/master/Left%20Right%20Shift%20in%20Java
b. How are positive numbers, negative numbers and characters represented in computer ?
Ans. http://www.tldp.org/HOWTO/Unix-and-Internet-Fundamentals-HOWTO/core-formats.html
https://www.youtube.com/watch?v=HhtecBhM_oA
c. How are negative numbers represented in computer ? (Ans. 2's complement)
Ans. https://www.rit.edu/~w-asc/documents/services/resources/handouts/DM3%20Two's%20Complement.pdf
d. Why are negative numbers represented as 2's complment in computer ?
Ans. VERY NICELY EXPLAINED HERE:
http://stackoverflow.com/questions/1125304/why-is-twos-complement-used-to-represent-negative-numbers
5. Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers
are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.
Source: http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/
Solution: https://github.com/nkatre/Opearations-Variants-in-an-array/blob/master/Find2NonRepeatingNumbers
OR
The above question can also be given for String, where we need to find any two characters which are non-repeating in the String.
Solution: https://github.com/nkatre/Opearations-Variants-in-an-array/blob/master/Find2NonRepeatingCharacters
6. Given an array in which all numbers except 1 is repeated once. (i.e. we have 2n+1 numbers and n numbers
are occurring twice and remaining one number have occurred once). Find the non-repeating number in the most efficient way.
OR
Given an array in which all characters except 1 is repeated once. (i.e. we have 2n+1 characters and n characters
are occurring twice and remaining one character have occurred once). Find the non-repeating character in the most efficient way.
Solution: https://github.com/nkatre/Opearations-Variants-in-an-array/blob/master/Find1NonRepeatingNumberORChracter