常见的位运算

1.位操作实现乘除法

​ 数a向右移一位，相当于将a除以2；数a向左移动一位，相当于将a乘以2。

2.位操作交换两个数

void swap(int a,int b){
a=a+b;
b=a-b;
a=a-b;
}
void swap(int a,int b){
a^=b;
b^=a;
a^=b;
}

3.位操作判断奇偶

​ 只需要将数a和1进行&（与）运算即可，如果结果是1那么说明是奇数，反之为偶数。

if(0==(a&1)){
//偶数的操作
}

4.位操作交换符号

​ 正数取反+1，正好变成其对应的负数，负数取反+1，正好变成它的原码，即正数。

int reversal(int a){
return ~a+1;
}

5.位操作求绝对值

​ 正数的绝对值就是本身，负数的绝对值是对它进行取反+1得到。首先判断正负数，然后再分别做操作。

​ 判断符号：正数右移31位得到0，负数右移31位得到-1。

int abs(int a){
int i=a>>31;
return i==0?a:(~a+1);
}
//简化一下
int abs(int a){
int i=a>>31;
return ((a^i)-i);
}

6.位操作进行高低位交换

​ 给定一个16位的无符号整数，交换高八位和低八位，给出交换后的值。注意，Java中没有无符号整数类型。

unsigned short a=34520;
a=(a>>8)|(a<<8);

7.位操作进行二进制逆序

​ 将无符号数的二进制表示进行逆序，求逆序后的结果。

unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);

8.位操作统计二进制中1的个数

int count(int a){
int cnt=0;
while(a){
a=a&(a-1);
cnt++;
}
return cnt;
}

​ 这个关键在于a&(a-1)这个操作，可以消除掉a最后一位的1。

9.a^ b ^b=a

相关题目

231. 2的幂

class Solution {
public boolean isPowerOfTwo(int n) {
return n>0&&(n&(n-1))==0;
}
}

762. 二进制表示中质数个计算置位

class Solution {
public int countPrimeSetBits(int L, int R) {
int ans=0;
for(int i=L;i<=R;i++){
int cnt=0,a=i;
while(a!=0){
a=a&(a-1);
cnt++;
}
if(isPrime(cnt))
ans++;
}
return ans;
}
boolean isPrime(int num){
if(num<2) return false;
if(num==3) return true;
for(int i=2;i<=Math.sqrt(num);i++){
if(num%i==0)
return false;
}
return true;
}
}

136. 只出现一次的数字

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

137. 只出现一次的数字 II

​ 给定一个数组，只有一个数字出现了一次，剩下的数组都是3次。

​ **第一种：**时间复杂度为$O(n)$，按位来做。

class Solution {
public int singleNumber(int[] nums) {
int ans=0;
for(int bit=0;bit<=31;bit++){
int cnt=0;
for(int i=0;i<nums.length;i++)
cnt+=(nums[i]>>bit)&1;
ans+=(cnt%3)<<bit;
}
return ans;
}
}

​ 第二种：状态机 时间复杂度$O(1)$

​ 因为数字是出现三次的，换言之对于每一个二进制位，如果出现一次的数在该二进制位为1，那么这个二进制位再在全部数字中出现的次数没有办法被3整除。

​ $ones$表示出现1次的数的抑或结果，$twos$表示所有出现两次数的抑或结果。

class Solution {
public int singleNumber(int[] nums) {
int ones=0,twos=0;
for(int x:nums){
ones=(ones^x)& ~twos;
twos=(twos^x)& ~ones;
}
return ones;
}
}

260. 只出现一次的数字 III

​ 这个题说的是给定一个数字，其中只有两个数出现了一次，剩下的数都出现了两次，让我们找到出现一次的两个数字。

​ 我们知道a^B^B=a，我们首先将数组中的每一个元素都进行异或，那么最终得到结果必然是两个只出现了一次的数字异或的结果，假设出现一次的数字是$x$和$y$，那么异或结果我们表示为$xor=x$^$ y$。

​ $xor$肯定不是0，我们只需要找到$xor$中表示1的最低位是哪一位就行了，比如说$xor=12$，表示成二进制就是1010，那么就可以通过从右往左数第二位上的1来区别$x$和$y$。根据该位置是不是1可以把数组分成两个部分，$x$和$y$肯定在不同的两个部分中，又因为其他数字都是成对出现的，再次通过a^b^b=a可以消除掉每一部分中出现两次的数，所以两个部分剩下的结果就是$x$和$y$.

class Solution {
public int[] singleNumber(int[] nums) {
int xor=0,flag=1;
for(int x:nums){
xor^=x;
}
while((xor&flag)==0) flag<<=1;
int res[]=new int[2];
for(int x:nums){
if((flag&x)==0)
res[0]^=x;
else
res[1]^=x;
}
return res;
}
}

476. 数字的补数

class Solution {
public int findComplement(int num) {
int ans=0,move=0;
while(num!=0){
//得到num二进制的最后一位
int last=num&1;
if(last==0)
ans+=1<<move;
//移动位数+1
move++;
//num的最后一位已经判断过，不需要再使用了，所以无符号右移一位
num>>>=1;
}
return ans;
}
}

371. 两整数之和

​ 注意运算符的优先级：先算术运算，后移位运算，最后位运算。b=(a&b)<<1;需要加括号，否则会先进行移位操作然后再位操作，这样得到的结果是错误的。

/*
以a=5，b=7为例，a和b的二进制分别是101、111.
- 1.a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)，一般来说无进位的加法可以用异或实现
有进位的加法可以通过&运算实现。对于5+7来说，就是无进位结果2和进位结果10相加。
- 2.无进位加法使用异或运算计算得出：a^b
- 3.进位结果使用与运算和移位运算计算得出：a&b<1
- 4.循环此过程，直到进位结果为 0
*/
class Solution {
public int getSum(int a, int b) {
while(b!=0){
//无进位的加 tmp=101^111=010,也就是2.
int tmp=a^b;
//a&b=101&111=101 左移一位得到1010，也就是10 
b=(a&b)<<1;
a=tmp;
}
return a;
}
}

201. 数字范围按位与

考虑范围[m, n]，如果n比m二进制位数高的话，在累计按位与的过程中，数字的每一个二进制位数必然都出现过0，所以一旦出现位数不同的情况，结果必然为0。

程序中，m, n在向右移位的过程中，如果m, n相等了，就说明累计按位与的左边肯定等于m, n此时的状态，这时候就可以向左移回来了，相当于右边所有位数都补0，相等的部分照旧。

如果m, n位数不相等，肯定会移到底，两者都为0时才会相等停止循环，这时候再向左移多少结果都是0。

class Solution {
public int rangeBitwiseAnd(int m, int n) {
int ans = 0;
while(m!=n){
m>>=1;
n>>=1;
ans+=1;
}
return n << ans;
}
}

477. 汉明距离总和

​ 2个数比较二进制对应位不同，就是比较每一位的情况然后把各个位上的情况相加组成最后的答案。假设$nums$数组一共有4个数，这四个数的每一位不是0就是1，先看最低位，假设这四个数的最低位分别是：1 0 1 0。显而易见，0有两个个，1也有两个，从四个数中任意挑选2个数，我们先只比较这两个数最低位不同的情况，从四个数里面任意挑选两个有6种情况，但实际上最后一位不同的情况只有4种，为啥呢，从最低位为1的数里挑一个有两种情况，从最低位为0的数里挑一个也有两种情况，$2\ast 2=4$，所以最低位不同的情况有4种，以此类推算得每一位不同的情况进行累加就是答案。

​ 所以这个题实际上与0的个数和1的个数有关系。

class Solution {
public int totalHammingDistance(int[] nums) {
int res=0;
//10^9是31位，所以循环位数是31位
for(int i=0;i<=30;i++){
int ones=0;
for(int x:nums)
if((x>>i&1)==1)
ones++;
//1的个数*0的个数
res+=ones*(nums.length-ones);
}
return res;
}
}

421. 数组中两个数的最大异或值

public class Solution {
public int findMaximumXOR(int[] nums) {
int res = 0;
int mask = 0;
for (int i = 30; i >= 0; i--) {
mask = mask | (1 << i);
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num & mask);
}
int temp = res | (1 << i);
for (Integer prefix : set) {
if (set.contains(prefix ^ temp)) {
res = temp;
break;
}
}
}
return res;
}
}

参考

位运算有什么奇技淫巧？

最后

以上就是矮小小蜜蜂为你收集整理的常见位运算总结及LeetCode相关题目常见的位运算相关题目参考的全部内容，希望文章能够帮你解决常见位运算总结及LeetCode相关题目常见的位运算相关题目参考所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。