异或逻辑的关系是:当AB不同时,输出P=1;当AB相同时,输出P=0。
特性:
运算规则:0&0=0;0&1=0;1&0=0;1&1=1;即:两位同时为“1”,结果才为“1”,否则为0。另,负数按补码形式参加按位与运算。
特性:
运算规则:0|0=0; 0|1=1; 1|0=1; 1|1=1,参与运算的位,只要有一个为1,其值为1。负数按补码形式按位运算。
特性:
运算规则:~1=0; ~0=1;对一个二进制数按位取反,将0变1,1变成0
特性:
二进制位全部左移若干位,左边的二进制位丢弃,右边补0。 特性:
二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。 注意,这里与>>>有些不同,>>>表示无符号位右移,运算符所作的是无符号的位移处理,它不会将所处理的值的最高位视为正负符号。>>>右移,左边空出的位以0填充。
特性:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?
示例1: 输入:[2,2,1] 输出:1
示例2: 输入:[4,1,2,1,2] 输出:4
/** * 异或的性质是,任何一个数字异或它自己都等于0,所以用start=0来处理 * @param nums * @return */ private static int getUniqueNum(int[] nums){ int start = 0; for (int num : nums){ start ^= num; } return start; }
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗? 示例1: 输入: [ 2,2,3,2] 输出: 3
示例2: 输入: [0,1,0,1,0,1,99] 输出:99
/** * 用两个数one=0、two=0分别记录bits位上1出现的次数, * 把相同的数放在前面一起排列时: * 如果一个数出现一次,则one等于这个数,two=0; * 如果一个数出现两次,则two等于这个数, one等于0; * 如果一个数出现第三次,则one = 0, two = 0 ,three等于这个数。 * * @param nums * @return */ private static int getUniqueNum(int[] nums) { int ones = 0;//记录二进制1只出现过1次的bits int twos = 0;//记录二进制1只出现过两次的bits int threes;//出现三次的 for (int num : nums) { twos ^= ones & num;//要在更新ones前面更新twos ones ^= num;//更新ones threes = (ones & twos);//ones和twos中都为1即出现了3次 System.out.println("ones:" + ones + " twos:" + twos + " threes:" + threes); ones &= ~threes;//抹去出现了3次的bits twos &= ~threes; System.out.println("清零后 ones:" + ones + " twos:" + twos + " threes:" + threes); } return ones; }
在main方法中运行如下代码:int[] nums = {15, 15, 15, 5};System.out.println(getUniqueNum(nums));
输出结果为:ones:15 twos:0 threes:0清零后 ones:15 twos:0 threes:0ones:0(15与15取异或为0) twos:15(先是15与15取并集为15,然后0与15取异或为15) threes:0(0与15取并集) 清零后 ones:0 twos:15 threes:0ones:15(0与15异或为15) twos:15(先是0与15取并集为0,然后15与0取异或为15) threes:15(15与15取并集为15)清零后 ones:0 twos:0 threes:15ones:5(0与5取异或为5) twos:0(先是0与5取并集为0,然后0与0取异或为0) threes:0(0与5取并集为0)清零后 ones:5 twos:0 threes:05
运行:int[] nums = {15, 5, 15, 15};System.out.println(getUniqueNum(nums));
输出:ones:15 twos:0 threes:0清零后 ones:15 twos:0 threes:0ones:10(15与5取异或为10) twos:5(15与5取并集为5,0与5取异或为5) threes:0(10与5取并集为0)清零后 ones:10 twos:5 threes:0ones:5 twos:15 threes:5清零后 ones:0 twos:10 threes:5ones:15 twos:10 threes:10清零后 ones:5 twos:0 threes:105
这道题只能自己慢慢琢磨。找了几遍博客,对这点说的都不是十分清楚。
给定一个整数数组nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。找出只出现一次的那两个元素。
示例: 输入:[1,2,1,3,2,5]
输出: [3,5]
注意: 1.结果输出的顺序并不重要,对于上面的例子,[5,3]也是正确答案。 2.你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?
/** * 在这里把所有元素都异或,那么得到的结果就是那两个只出现一次的元素异或的结果。 * 然后,因为这两个只出现一次的元素一定是不相同的,所以这两个元素的二进制形式肯定至少有某一位是不同的,即一个为 0 ,另一个为 1 ,现在需要找到这一位。 * 根据异或的性质 任何一个数字异或它自己都等于 0 ,得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。 * 再然后,以这一位是 1 还是 0 为标准,将数组的 n 个元素分成两部分。 * 1. 将这一位为 0 的所有元素做异或,得出的数就是只出现一次的数中的一个 * 2. 将这一位为 1 的所有元素做异或,得出的数就是只出现一次的数中的另一个。 * 这样就解出题目。忽略寻找不同位的过程,总共遍历数组两次,时间复杂度为O(n)。 * * @param nums * @return */ private static int[] getUniqueNum(int[] nums) { int diff = 0; for (int num: nums){ diff ^= num; } // 得到最低的有效位,即两个数不同的那一位 diff &= -diff; int[] result = new int[2]; for (int num:nums){ if ((num & diff) == 0){ result[0] ^= num; }else { result[1] ^= num; } } return result; }
利用与运算中,2&1=0,4&3=0,利用2的幂-1与2的幂的与运算结果为0,2的幂的二进制形式一定只有一位为1,其他为0,而他的减一形式一定是这一位为0,其他为1.
boolean istwores(int n){ return n&(n-1)==0?True:False;}
a = a ^ b;b = a ^ b;a = a ^ b;
if(number <= 0)return false; if(number & (number - 1))return false; //这里一定要注意,== 的优先级大于 &,所以如果不加括号的话,结果会变成return number & (0x55555555 == number); return (number & 0x55555555) == number;
参考: