首页 > 代码库 > Single Number II位运算解析
Single Number II位运算解析
本题最机巧的O(n)解法最早由1337c0d3r于2013.11.26发布在leetcode。之后看到类似的,都系转载、引用或抄袭。(原文:https://oj.leetcode.com/discuss/857/constant-space-solution)
大多数转载都写得语焉不详,有的甚至据为己有。本帖旨在全面解析该算法。
如下:
int singleNumber(int A[], int n) { int ones = 0, twos = 0, threes = 0; for (int i = 0; i < n; i++) { twos |= ones & A[i]; ones ^= A[i]; threes = ones & twos; ones &= ~threes; twos &= ~threes; } return ones; }只看这几行代码,很难得其要领,如很多人的转载。原文解释如下:
ones
as a bitmask to represent the ith bit had appeared once.twos
as a bitmask to represent the ith bit had appeared twice.threes
as a bitmask to represent the ith bit had appeared three times.
When the ith bit had appeared for the third time, clear the ith bit of both ones
and twos
to 0. The final answer will be the value of ones
.
twos |= ones & A[i]; // ones代表1出现一次的位元,如果A[i]对应位是1则&后为1代表出现两次了,否则为0;结果就是twos中为1的位,表示该位出现两次1第二句:
ones ^= A[i]; // 出现偶数则为0,出现奇数则为1,本题没有出现偶数的情况,所有ones代表出现1,3,5,……等位;但后面的语句会将其它情况去掉第三句:
threes = ones & twos;// 相当与三进制加法。第四、五句:
ones &= ~threes; //加完之后要清理,如果three为1则ones和twos对应位清0;如果为0,则ones twos和1相与保持不变。 twos &= ~threes; //这两句处理第二句中Ones其它奇数次情况,即ones如果为大于1的奇数,则此处必然被清0如果你还不明白该算法,没关系下面还有一段等价的python代码:
class Solution: # @param A, a list of integer # @return an integer def singleNumber(self, A): ones=0 twos=0 threes=0 for i in A: #(threes&(~i)):if a bit we get three times and it occured in new element, then clear it. (twos&i): if a bit we get twice and it occured again, add to threes. threes=(threes&(~i))|(twos&i) #the same with threes twos=(twos&(~i))|(ones&i) #if a bit occured in odd times and it not in threes, we can sure it occured once ones=(ones^i)&(~threes) return ones | twos解释的很清楚,当然最后一句可以改成return ones,没有任何问题。
位运算的形式大多很简洁,但内涵很丰富,需要字斟句酌方能得其真意。所有的算法必然都是简单的,如果你觉得难以理解,只能说你还没有理解,或者它本身就一堆垃圾。
Single Number II位运算解析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。