java - xor operator find the number which appears once explain -
i don't understand algorithm.
for array given in program, if
i = 0, num = num ^ arr[0] => num = 0 ^ 3 = 3 = 1, num = num ^ arr[1] => num = 3 ^ 1 = 2 = 2, num = num ^ arr[2] => num = 2 ^ 5 = 7 ...etc...and last result in num printed. what's going on here? how did delete numbers same value?
this algorithm finds element appears in array once, how?
class ideone { public static int a() { int arr[] = {3,1,5,1,5,3,4,7,7}; int num = 0; for(int = 0; < arr.length; i++){ num ^= arr[i]; } return num; } public static void main (string[] args) throws java.lang.exception { system.out.println(a()); } }
the other answers completely right, think have nice way think i'll share thoughts you.
this long read, super simple , think understand algorithm ,
^, or xor, does.
the easy way!
remember these rules!
n ^ n = 0
n ^ 0 = n
and n can any number.
for example:
1 ^ 1 = 0 1 ^ 0 = 1 6 ^ 6 = 0 6 ^ 0 = 6 12345 ^ 12345 = 0 12345 ^ 0 = 12345 0 ^ 1 = 1 0 ^ 6 = 6 see rule commutative.
so these 2 rules, can this:
n ^ n ^ n ^ n ^ n ^ n = 0 why? because:
n ^ n ^ n ^ n ^ n ^ n is same as:
(n ^ n) ^ (n ^ n) ^ (n ^ n) and we've seen n ^ n = 0 right?
so saying:
0 ^ 0 ^ 0 and since 0 ^ 0 = 0, get:
0 ^ 0 and since 0 ^ 0 = 0, get:
0 we can this:
n ^ n ^ n ^ n ^ n ^ n ^ n = n why? because:
n ^ n ^ n ^ n ^ n ^ n ^ n is same as:
(n ^ n) ^ (n ^ n) ^ (n ^ n) ^ n and we've seen n ^ n = 0 right?
so saying:
0 ^ 0 ^ 0 ^ n we have case of n ^ n = 0 here since n can number, 0! 0 ^ 0 = 0. let's replace our 0 ^ 0 equal to, 0. @ same time, see rule can use: n ^ 0 = n
0 ^ 0 ^ 0 ^ n == (0 ^ 0) ^ (0 ^ n) == 0 ^ n and of course, we've seen rule before: n ^ 0 = n.
we know finish with:
0 ^ n = n if had 1 more n when started, have carried down point , have: 0 ^ n ^ n become either n ^ n or 0 ^ 0, both of become 0.
now, can see example above when perform ^ on number of number (like 7 n's or 20 n's, etc), can pair these numbers , cancel them out.
we group pairs of number, n, , become 0. no matter how many pairs there are!
this
n ^ n ^ n ^ n ^ ......... ^ n ^ n becomes
(n ^ n) ^ (n ^ n) ^ ......... ^ (n ^ n) which becomes
0 ^ 0 ^ .......... ^ 0 which becomes
0 if had odd number of n's however, here:
n ^ n ^ n ^ n ^ ......... ^ n ^ n it become
(n ^ n) ^ (n ^ n) ^ ......... ^ (n ^ n) ^ n which become
0 ^ 0 ^ .......... ^ 0 ^ n which becomes
0 ^ n which of course, we've said many times:
n what mean?
this means number of given number, n, when ^'d together, either n, or 0, depending on if had or odd number of n's.
an number of n's ^'d give 0, while odd number of n's ^'d give n.
we saw earlier when had
and again when had 7 n's. made 3 pairs out of first 6 n's, , had 1 left over. ended lot of 0's , 1 n. of course n ^ 0 = n.
so odd number of n's, you'll end lot of 0's pairs, , 1 single n left over. you'll have 0 ^ n or n ^ 0 (same thing), of course, n.
with number of n's, you'll pair every 2 together, each become 0. have bunch of 0 of course going end being 0.
applying these rules algorithm
now can make 2 new rules deduced:
n ^ n ^ n ^ n ^ ..... ^ n ^ n = 0 number of n's
n ^ n ^ n ^ n ^ ..... ^ n = n odd number of n's
if working bunch of different numbers, rules still apply.
let's @ real numbers now. have:
3, 1, 5, 1, 5, 3, 4, 7, 7 if ^ them this:
3 ^ 1 ^ 5 ^ 1 ^ 5 ^ 3 ^ 4 ^ 7 ^ 7 we can skip of math, , not worry doing hard work! able because have noticed something: each of numbers appear either odd number of times or number of times (duh!). , know pretty cool rules numbers appear number of times, , numbers appear odd number of times.
we can rearrange list make easier count number of occurrences of each particular number:
1 ^ 1 ^ 3 ^ 3 ^ 4 ^ 5 ^ 5 ^ 7 ^ 7 remember can rearranging because ^ commutative.
now see have 2 1's, 2 3's, 1 4, 2 5's, , 2 7's.
let's use our above rules simplify our long list of math:
1 ^ 1 becomes 0 so:
0 ^ 3 ^ 3 ^ 4 ^ 5 ^ 5 ^ 7 ^ 7 3 ^ 3 becomes 0 so:
0 ^ 0 ^ 4 ^ 5 ^ 5 ^ 7 ^ 7 5 ^ 5 becomes 0 so:
0 ^ 0 ^ 4 ^ 0 ^ 7 ^ 7 7 ^ 7 becomes 0 so:
0 ^ 0 ^ 4 ^ 0 ^ 0 0 ^ 0 becomes 0 (twice), so:
0 ^ 4 ^ 0 0 ^ 4 becomes 4 (because 0 ^ n = n) so:
4 ^ 0 becomes 4 (because `n ^ 0 = n) so:
4
we didn't actual math!
now, if had more 1 number in list odd number of times, have had math.
but if have list of numbers , each number included number of times (be 2 times, or 4, or 6, or number), break down 0.
if have list of numbers , each number included number of times, except 1 number, break down 1 number.
that how algorithm works. cancels out pairs of same numbers, , left 1 oddball.
the algorithm works because list guaranteed have 1 number appear once, , rest appear twice. still works long 1 number appears odd number of times, , every other number appears number of times.
you can see math section below see what's going on numbers.
after ^'ing each number together, pairs of same numbers cancelled out , became 0, while single numbers couldn't paired stayed same.
since had 1 number appear once, rest paired became 0.
the 1 odd number stayed , rest became 0 had: n ^ 0 n number appeared once.
and we've said time or 2 before, n ^ 0 = n!
so took our list had 1 number, n, appeared odd number of times, , found using ^ operator... , slick rules.
explanation of math
the ^ operator, or xor operator, works binary representations of numbers.
every number in binary 1's , 0's.
let's @ number, 5, , number, 3:
5 = 101 , 3 = 11 if don't know how got these binary representations, read this guide introduction.
now, our binary numbers 101 , 11.
we can different operations & or | essentials mean , and or.
if , operation on 101 , 11, this:
101 11 &____ 001 we got 001 because looked @ digit in each spot (the "ones" spot, "tens" spot, , "hundreds" spot). compare them in each number. if both 1, result "spot" 1. otherwise, it's 0.
so in far left spot, or column, compared 1 in 101 blank in 11 , since both weren't 1, got 0.
in middle, compared 0 in 101 1 in 11, , got 0 since both weren't 1. in right column, compared 1 in 101 1 in 11, , finally! got match! both 1 1 in spot.
no if did |, or operation, this:
101 11 &____ 111 that's because | operator gives 1 column if number in either number 1 in column. if both 1, still 1.
now ^ operator
now we've seen how & , | work, let's talk ^ operator.
it's called xor, , similar , and or operators. gives 1 in column if either number has 1 in column, not both numbers.
for example, 1 ^ 0 = 1 1 ^ 1 = 0. important!!!
the algorithm above clever, , isn't particularly intuitive thinkers. takes advantage of something. if number ^'d itself, 0 since have same 0's , 1's both have 1 in column , therefore come out 0.
like number:
1010110110 1010110110 ^___________ 0000000000 see how each column never have 1 , 0, either both 1's or both 0's.
now hard show, if play enough numbers, realize can add in number ^'ing , take out same way. don't mean add value of total, add in.
imagine making set!
we can add numbers set, strange custom set, if add in number twice.. disappears!
the ^ operator allows make strange set!
from on, i'll refer strange weird "set" set. not equivalent real set, think it's convenient way think ^. don't confused when word "set", referring made definition use.
let's @ numbers: 1, 2, 3.
if take binary representations get:
1 = 1 2 = 10 3 = 11 if start 0 our set, binary representation 0. let's ^ our 0 1 of numbers. let's 3.
0 #our set 11 ^____ 11 now have 11 our set, or our binary representation.
remember if ^ 2 of same numbers together, 0. true here too. have 11 right , if ^ 11 that, we'll 0.
now crazy part is, can ^ more 2 numbers together, , our fact remains same.
right have added 3 our set. our set looks this:
{3} the binary representation of our set is:
11 let's ^ number it. how 1?
11 #our set 1 #1 ^____ 10 so our set looks this:
{3, 1} binary representation is: 10 our rule still applies ^ 1 number ^ 0. let's see happens when try ^ 3 our set.
10 #our set 11 #3 ^____ 01 #our new set we took our set of {3, 1} or 10 , ^'d 3 , in essence popped 3 right out! remember our set take out number if try add twice.
the old set:
{3, 1} we tried add 3, existed set popped out:
{1} we can see in our binary representation because went from:
10 to
01 that's same 1!!! added 3, added 1, added 3, , got 1! ^ does! cancel out pair of same number.
we can see more , more numbers:
the list: 3, 1, 5, 1, 5, 3, 4, 7, 7 the algorithm gave starts 0, , ^'s each number onto has.
it this:
0 ^ 3 ^ 1 ^ 5 ^ 1 ^ 5 ^ 3 ^ 4 ^ 7 ^ 7 but make math more algorithm, show happens.
start num = 0
num = 0 num in binary = 0 going through list, ^ each number. let's started!
num ^= 3
0 #num 11 #3 ^____ 11 #new value num num = 3 num in binary = 11 num ^= 1
11 #num 1 #1 ^____ 10 #new value num num = 2 num in binary = 10 num ^= 5
10 #num 101 #5 ^____ 111 #new value num num = 7 num in binary = 111 num ^= 5
111 #num 1 #1 ^____ 110 #new value num num = 6 num in binary = 110 num ^= 5
110 #num 101 #5 ^____ 011 #new value num num = 3 num in binary = 011 num ^= 3
11 #num 11 #3 ^____ 00 #new value num num = 0 num in binary = 0 num ^= 5
0 #num 10 #4 ^____ 10 #new value num num = 4 num in binary = 10 num ^= 7
10 #num 111 #7 ^____ 101 #new value num num = 5 num in binary = 101 num ^= 7
101 #num 111 #7 ^____ 010 #new value num num = 4 num in binary = 010 after ^'ing each number together, pairs of same numbers cancelled out , became 0, while single numbers couldn't paired stayed same.
since had 1 number appear once, rest paired became 0.
the 1 odd number stayed , rest became 0 had: n ^ 0 n number appeared once.
and we've said time or 2 before, n ^ 0 = n!
so took our list had 1 number, n, appeared odd number of times, , found using ^ operator... , slick rules.
so know simple rules, , know how math works!
thanks reading!
Comments
Post a Comment