【数据结构与算法】一、位运算

前言

大家好，我是春风。

因为之前对于数据结构与算法，都是零零散散的学习，学完之后，发现自己掌握的也不牢靠，所以从今天开始，准备完整的系统性的学习数据结构与算法。（所看视频：左神的数据结构与算法课程）

算法追求的就是解决问题的效率，要效率高，就一定要先了解位运算！

一、Java中的int

打印int的二进制数：

我们知道Java中int型整数在二进制中是32位，那怎么打印我们这个32位的二进制整数呢？

解：循环32次，每次将1左移i位，然后与上整数本身。

整型的范围：

无符号整数的最大值是：2^32 - 1

我们知道有符号整数的范围是-2^31 ~ 2^31-1，怎么来的？

有符号整数，也就是我们Java中的int，最高位0、1表示符号，1就是负数，0就是非负数。

那最大值就是0 ~ 30这31个位置都是1，也就是2^31 - 1。

而int中的负数用32位二进制表示比较特殊：除了第32位上用1来表示符号负数外，剩下的31个位置上，取反+1才是最终那个负数，所以-1就是32位全部为1（除符号位其他全部取反就为0，然后+1）

而最小值，就是0~30位全部为0，取反后全为1，然后+1，也就是-2^31

为什么负数要做成取反？

因为所有计算到了计算机都是位运算，而为了位运算时不用区分正负，所以就设计为取反。

异或 ^：

冒泡排序中交换两个数a,b 即可以用异或操作：

a = a^b;
b = a^b;
a = a^b;

为什么会这样？

（但是交换的两个对象一定不能指向同一个地址）

异或操作，和乘法一样，满足交换律和结合律；

设 a = b ^ c; 已知a、c的情况下

则得到 b = a ^ c

异或运算 = 无进位相加

例题：

找出现奇数次的数，不管几个，都可以用hashSet处理，第一次加进去，遇见第二次就剔除来，这样最后剩下的就一定是出现奇数次的数

1、一个数组中，有一个数出现了奇数次，其他都出现偶数次，找到该数？

直接将数组中所有数异或起来，出现偶数次的都会两两相同，抵消为0，剩下的结果就是出现奇数次的那个数。

2、一个数组中，有两个数出现了奇数次，其他都出现偶数次，找到这两个数？

先和上面一样，所有数异或，得到的就是两个出现奇数次的数异或的结果，然后通过与运算找到不同的位置，再将所有的数通过与运算 a、b不同的那个位置，就会把数分为 a和其中一部分数，b和其中一部分数，然后在每一部分数中再异或去找这部分唯一出现奇数次的那个数。

int [] arr = {1,1,0,0,3,5};
int res = 0;
for (int i=0; i<arr.length; i++) {
res ^= arr[i];
}
// 得到的res = 3^5的结果；
/**
* 3 ^5结果一定不为0，他们不同，他们异或的结果，至少有一个位置是1
* 通过将1一次次左移，如果与的结果是1，那就说明左移到的这个位置是1
*/
int separator = 1;
while ((res & separator) == 0) {
separator = separator << 1;
}
/**
* 上面这个位置，a和b两个数不一样，那所有的数与上这个位置
* 就会把数分为 a和其中一部分数，b和其中一部分数
* 然后在每一部分数中再异或去找这部分唯一出现奇数次的那个数
*/
int result[] = new int[2];
for (int i=0; i<arr.length; i++) {
if ((arr[i] & separator) == 0) {
result[0] = result[0] ^ arr[i];
} else {
result[1] = result[1] ^ arr[i];
}
}

上面找某个数最右侧的那个1的位置，除了将1依次左移做与运算，还可以直接将该数与上自己取反加一的值，这样只有计算一次，如下：

右侧第一个为1的数 = n & (~n + 1)

n ---- 1100

~n ---- 0011

~n+1 ---- 0100

n & (~n + 1) ---- 0100 即 原来 1100的左侧第一个1的数

取反加一其实就是第一个进位的1

3、 乘除2的计算

乘2，转换为位运算的方式是左移一位；

除2，转换为位运算的方式是右移一位；

可以用于二分或归并中计算中间下标的计算，提升性能。

这里注意区分有符号位移>> 和无符号位移 >>>

4、判断一个整数的奇偶性

就是看最后一个位置是0还是1，所以直接与上1，结果等于1就是奇数，否则就是偶数;

3 -- 11

1 -- 01 &

结果==01 奇数

4、判断一个整数是不是2的幂次方

一个数是2的幂次方，则它减一得到的二进制数全部位数一定都是1，比如8，二进制为1000，减一对应的二进制为0111，他们与上的结果一定是0，所以判断一个数是2的幂次方的数可以这样：

num & （num-1） == 0

顺便可以复习一下hashmap中的容量计算就是类似的思路。

5、求一个数二进制表示中1的个数

第一种解法是和前面找最右侧的1的位置一样，循环的将1无符号左移一位，然后与上该数，就能遍历出所有的1；

第二种解法：因为第一种需要遍历所有的位数，第二种优化一下。

我们会发现一个规律，就是一个整数num，与上num-1，则得到的结果一定会把num最后那个位置上的1抹去，比如： 7 --- 0111

6 --- 0110 &

得到6- 0110

5 --- 0101 &

得到4 0100 &

3 --- 0011 &

得到 0000 则说明7有三个1

public int countA(int n){
int res = 0;
while(n != 0){
n &= (n - 1);
res++;
}
return res;
}

最后的最后，求点赞！非常感谢！

我是春风，春风和煦，不负归期！ 公H：程序员春风

最后

以上就是呆萌心情为你收集整理的【数据结构与算法】一、位运算的全部内容，希望文章能够帮你解决【数据结构与算法】一、位运算所遇到的程序开发问题。

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