【建议收藏】面试官会问的位运算奇淫技巧

往期热门文章：
1、到底可不可以用 kill -9 关闭程序？
2、IDEA 2021首个大版本发布，新增了这几个超实用功能！
3、Optional 是个好东西，你真的会用么？
4、Java 8 ConcurrentHashMap源码中竟然隐藏着两个BUG
5、我在国企当程序员！

前言

认识位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

• 对于左移运算符<<没有悬念右侧填个零无论正负数相当于整个数乘以2。

• 而右移运算符就有分歧了，分别是左侧补0>>>和左侧补原始位>>，如果是正数没争议左侧都是补0，达到除以2的效果；如果是负数的话左侧补0>>>那么数值的正负会发生改变，会从一个负数变成一个相对较大的正数。而如果是左侧补原始位(负数补1)>>那么整个数还是负数，也就是相当于除以2的效果。

位运算小技巧

判断奇偶数

if( n % 2 == 1)
    // n 是个奇数
}

if(n & 1 == 1){
    // n 是个奇数。
}

交换两个数

int team = a;
a = b;
b = team;

a=a^b;//a=a^b
b=a^b;//b=(a^b)^b=a^0=a
a=a^b;//a=(a^b)^(a^b^b)=0^b=0

二进制枚举

for(int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
{
  for(int j = 0; j < n; j++) //遍历二进制的每一位 共n位
  {
    if(i & (1 << j))//判断二进制数字i的第j位是否存在
    {
      //操作或者输出
    }
  }
}

位运算经典问题

不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

对于加法的一个二进制运算。如果不进位那么就是非常容易的。这时候相同位都为0则为0，0和1则为1.满足这种运算的异或(不相同取1，相同取0)和或(有一个1则为1)都能满足.但事实肯定有进位的运算啊！看到上面操作的不足之后，我们肯定还需要解决进位的问题对于进位的两数相加，这种核心思想为：

• 用两个数，一个正常m相加(不考虑进位的)。用异或a^b就是满足这种要求，先不考虑进位(如果没进位那么就是最终结果)。另一个专门考虑进位的n。两个1需要进位。所以我们用a&b与记录需要进位的。但是还有个问题，进位的要往上面进位，所以就变成这个需要进位的数左移一位。
• 然后就变成m+n重新迭代开始上面直到不需要进位的(即n=0时候)。

public class Solution {
     public int Add(int num1,int num2) {
  /*
   *  5+3   5^3(0110)   5&3(0001) 
   *  0101    
   *  0011 
   */
  int a=num1^num2;
  int b=num1&num2;
  b=b<<1;
  if(b==0)return a;
  else {
   return Add(a, b);
  }        
  }
}

二进制中1的个数

首先要知道：

public int NumberOf1(int n) {
  int va=0;
  for(int i=0;i<32;i++)
  {
    if((n&(1<<i))!=0)
    {           
      va++;
    }
  }
  return va;       
}

public class Solution {
    public int NumberOf1(int n) {
    int count=0;
    while (n!=0) {
     n=n&(n-1);
     count++;
    }
    return count;
 }
}

只出现一次的(一个)数字①

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

• 0和任意数字进行异或操作结果为数字本身.
• 两个相同的数字进行异或的结果为0.

class Solution {
    public int singleNumber(int[] nums) {
        int value=0;
        for(int i=0;i<nums.length;i++)
        {
            value^=nums[i];
        }
        return value;
    }
}

只出现一次的(一个)数字②

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

class Solution {
    public int singleNumber(int[] nums) {
        int value=0;
        for(int i=0;i<32;i++)
        {
            int sum=0;
            for(int num:nums)
            {
                if(((num>>i)&1)==1)
                {
                    sum++;
                }
            }
            if(sum%3==1)
                value+=(1<<i);
        }
        return value;
    }
}

只出现一次的(两个)数字③

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

public int[] singleNumbers(int[] nums) {
    int value[]=new int[2];
    if(nums.length==2)
        return  nums;
    int val=0;//异或求的值
    for(int i=0;i<nums.length;i++)
    {
        val^=nums[i];
    }
    int index=getFirst1(val);
    int num1=0,num2=0;
    for(int i=0;i<nums.length;i++)
    {
        if(((nums[i]>>index)&1)==0)//如果这个数第index为0 和num1异或
            num1^=nums[i];
        else//否则和 num2 异或
            num2^=nums[i];
    }
    value[0]=num1;
    value[1]=num2;
    return  value;
}

private int getFirst1(int val) {
    int index=0;
    while (((val&1)==0&&index<32))
    {
        val>>=1;// val=val/2
        index++;
    }
    return index;
}

结语

往期热门文章：
1、《历史文章分类导读列表！精选优秀博文都在这里了！》
2、七种方式教你在Spring Boot初始化时搞点事情
3、ConcurrentHashMap有十个提升性能的地方，你都知道吗？
4、程序员等级图鉴
5、Java 中的 Switch 都支持 String 了，为什么不支持 long？
6、为什么数据库字段要使用NOT NULL？
7、CTO 说了，用错 @Autowired 和 @Resource 的人可以领盒饭了
8、程序员离职事件始末
9、别总写代码，这130个网站比涨工资都重要
10、程序员养生指北