前提知识：
- <<表示左移移，不分正负数，低位补0；
- >>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
- >>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0
异或运算性质：
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
- 任何数和其自身做异或运算，结果是 0，即 a ⊕ a = 0
- 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
231. 2 的幂
题解1：首先想到的是判断这个数是否为偶数，如果是偶数，就一直除以2 ， 直到是奇数为止， 最后在判断这个奇数是否等于1，但是会发现超过时间限制，所以我们换一种思路， 其实n 就只能是1 ，2 ， 4 ， 8 ， 1 6 … … 这样的数字，他们都有一个特点，二进制位中只有一个1，也就是说满足这个条件，那么这个数肯定是2 的幂次方。
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0){
return false;
}
int count = 0;
for (int i = 0; i < 32; i++) {
if (((n >>> i) & 1) == 1){
count++;
}
}
return count == 1;
}
}
题解2：剑指 Offer 15. 二进制中1的个数中通过(n & (n-1))可以消去二进制位中最右边的1，如果n 的二进制位中只有一个1 ， 那么n & ( n - 1 ) 的结果肯定是0 ， 所以我们只需要判断n 大于0 的时候， n & ( n - 1 ) 是否等于0 即可， 一行代码搞定。
class Solution {
public boolean isPowerOfTwo(int n) {
if (n <= 0){
return false;
}
return (n & (n-1)) == 0;
}
}
题解3：n 和- n 在二进制位中的区别， 因为- n 是n 每一个都取反然后再加上1 的结果， 所以n 和- n 的区别就是n 原来右边第一个1 以及他右边的都不变，所以在确定n大于0的情况下，只需要判断(n&-n)==n即可，也是一行代码搞定。
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n;
}
}
剑指 Offer 15. 二进制中1的个数
题解：18种解法，这个帖子讲了18种解法。列出常用的两种：
题解1：把n往右移32次，每次都和1进行与运算
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if (((n >>> i) & 1) == 1) {
count++;
}
}
return count;
}
题解2：这个是最常见的，每次消去最右边的1，直到消完为止
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
136. 只出现一次的数字
异或运算性质：
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
- 任何数和其自身做异或运算，结果是 0，即 a ⊕ a = 0
- 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}
260. 只出现一次的数字 III
该题滑动窗口专题有讲解，本专题位运算解法。
位运算，异或运算有性质如下：
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
- 任何数和其自身做异或运算，结果是 0，即 a ⊕ a = 0
- 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
题解：基于位运算性质
- 先将数组的所有元素异或得到的一个结果，这个结果为不存在重复的两个元素异或的结果，因为相同的都已经抵消掉了，同时也不为0，因为这两个元素是不同的。
- 然后我们需要将来数组分为两组，一组包含其中一个我们需要的结果，另外一组包含另外一个我们需要的结果，同时相同的元素必须分到一组，这样，我们对每一组的所有元素分别进行异或，就可以在每一组中得到一个我们想要的结果，怎么做呢？
- lab &= ‑lab得到出 lab最右侧的1,因为异或值为1，说明我们需要的两个值里面其中一个为0，另外一个为1，这样才能异或为1
- 然后遍历，分组，每一组分别异或就可以了
class Solution {
public int[] singleNumber(int[] nums) {
int[] res = new int[2];
int lab = 0;
for(int num : nums){
lab ^= num;
}
lab &= -lab;
for(int num : nums){
if ((num & lab) != 0){
res[0] ^= num;
}else {
res[1] ^= num;
}
}
return res;
}
}
剑指 Offer II 004. 只出现一次的数字
137. 只出现一次的数字 II
题解：在java中int类型是32位，我们需要统计所有数字在某一位置的和能不能被3整除，如果不能被3整除，说明那个只出现一次的数字的二进制在那个位置是1……把32位全部统计完为止。
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int i = 0; i < 32; i++) {
int oneCount = 0;
for (int j = 0; j < nums.length; j++) {
oneCount += (nums[j] >>> i) & 1;
}
if (oneCount % 3 != 0){
res |= 1 << i;//按位或，给相应的位置赋1
}
}
return res;
}
}
位运算部分小结
类似的题：136. 只出现一次的数字、260. 只出现一次的数字 III、剑指 Offer II 004. 只出现一次的数字
一，如果只有一个数字出现一次，其他数字都出现偶数次，我们只需要把所有数字异或一遍即可。例如：136题目Leetcode连接
因为异或有下面几条性质
- a^a=0 任何数字和自己异或结果是0
- a^0=a 任何数字和0异或还是他自己
- abc=acb 异或运算具有交换律
二，如果只有一个数字出现一次，其他数字都出现奇数次，我们可以用下面代码来解决。例如：剑指 Offer II 004. 只出现一次的数字
class Solution {
public int singleNumber(int[] nums,int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
int oneCount = 0;
for (int j = 0; j < nums.length; j++) {
oneCount += (nums[j] >>> i) & 1;
}
if (oneCount % n != 0){
res |= 1 << i;//按位或，给相应的位置赋1
}
}
return res;
}
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
题解：把所有数字都跟自己对应的下标异或，最后将结果与长度异或就可以得到结果，因为如果是正常顺序的话，所有数字都跟自己对应的下标相等，异或后结果为0，最后与长度异或就可以得到最终的结果，以[0,1,2,3,4,5,6,7,9]为例，异或到最后一个数字时res=98,然后异或长度9，即res=98^9=8。
异或性质：
- a^a=0 任何数字和自己异或结果是0
- a^0=a 任何数字和0异或还是他自己
- abc=acb 异或运算具有交换律
class Solution {
public int missingNumber(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; i++) {
res ^= nums[i] ^ i;
}
return res ^ nums.length;
}
}
389. 找不同
题解一：与136. 只出现一次的数字几乎一模一样的题目。
class Solution {
public char findTheDifference(String s, String t) {
char res = 0;
String str = s + t;
for (int i = 0; i < str.length(); i++) {
res ^= str.charAt(i);
}
return res;
}
}
题解二：既然字符串s 比t 少一个字符， 我们先统计字符串s 中每个字符的数量， 然后减去字符串t中的每个字符， 如果小于0 ， 说明字符串s 比t 少的就是这个字符， 直接返回即可。
class Solution {
public char findTheDifference(String s, String t) {
int[] count = new int[26];
for(int i = 0; i < s.length();i++){
count[s.charAt(i) - 'a']++;
}
for(int i = 0; i < t.length(); i++){
int val = --count[t.charAt(i) - 'a'];
if(val < 0){
return t.charAt(i);
}
}
return 'a';
}
}
题解三：用t 中所有字符的和减去s 中所有字符的和， 最后结果就是要求的那个字符。
class Solution {
public char findTheDifference(String s, String t) {
char res = 0;
for(int i = 0; i < t.length();i++){
res += t.charAt(i);
}
for(int i = 0; i < s.length(); i++){
res -= s.charAt(i);
}
return res;
}
}
1442. 形成两个异或相等数组的三元组数目
题解：a 的值是数组[ i … … j - 1 ] 中所有元素的异或结果， b 的值是数组[ j … … k ] 中所有元素的异或结果， 并且a 中异或的元素和b 中异或的元素是连续的并且没有重叠。如果要让a = = b，那么就是a ^ b = 0 ， 也就是arr[i]^arr[i+1]^……^arr[j]^……^arr[k]=0;所以问题就转化成了从数组a r r 中找到一些连续的元素， 他们的异或结果等于0 即可。
i<j，并且j可以等于k，这个k我们不需要管，所以至少需要2个元素。也就是说从数组arr中找到至少2个以上的连续的元素他们的异或结果是0即可成立三元组(i,j,k)。另外连续n 个元素的异或结果是0 ， 那么可能的组合就有n - 1 种。这样就很容易解这道题了。
class Solution {
public int countTriplets(int[] arr) {
int ret = 0;
for (int i = 0; i < arr.length; i++) {
int res = arr[i];
for (int j = i+1; j < arr.length; j++) {
res ^= arr[j];
if (res == 0){
ret += (j-i);
}
}
}
return ret;
}
}
461. 汉明距离
题解：先异或，然后求异或后结果中1的个数就行。
class Solution {
public int hammingDistance(int x, int y) {
int res = 0;
int num = x ^ y;
for (int i = 0; i < 32; i++) {
if (((num >>> i) & 1) == 1){
res++;
}
}
return res;
}
}
1356. 根据数字二进制下 1 的数目排序
题解：从题中可以看到0<=arr[i]<=10^4，所以我们可以将原来数中1的个数乘100000 + 原来的数值，然后再排序，排序完后在逐个还原。
class Solution {
public int[] sortByBits(int[] arr) {
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.bitCount(arr[i]) * 100000 + arr[i];
}
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
arr[i] = arr[i] % 100000;
}
return arr;
}
}
693. 交替位二进制数
题解：一个数的二进制位如果是0和1交替，那么把这个数往右移一位然后再和原来的数进行异或运算，就会让他全部变为1，然后加上1，那么原来的位置就都变成了0，再跟原来的数异或，判断是否为0即可。
class Solution {
public boolean hasAlternatingBits(int n) {
n ^= (n >>> 1);
return (n & (n + 1)) == 0;
}
}
网友评论