数据结构与算法-位运算
2021-06-19 23:06
标签：作用 转换 正数 函数返回 持续更新 出现 size 十进制 void 位运算 不用额外变量交换两个整数的值 如何判断一个整数是不是2的整数次方 数据结构与算法-位运算 标签：作用 转换 正数 函数返回 持续更新 出现 size 十进制 void 原文地址：https://www.cnblogs.com/hiyoung/p/9689659.html
位运算是把数字用二进制表示之后，对每一位上的0或者1的运算。理解位运算的第一步是理解二进制。二进制是指数字每一位都是0或者1，如十进制的2转换为二进制之后是10，而十进制的10转换为二进制之后是1010。在程序员圈子里有一个流传了很久的笑话，说世界上有10种人，一种人知道二进制，另一种人不知道二进制。 下面是几个常见的关于位运算的算法题：
基本位运算
位运算总共只有5种运算：与&，或|，异或^，左移>.
与，或，异或的运算规则：
左移，右移运算规则：
左移运算m
00001010
右移运算m > > n 表示把m右移n位，右移n位时，最右边的n位被丢弃，最左边根据该数字的类型决定，如果该数是一个无符号数值，则用0填补最左边的n位。如果该数是一个有符号数值，用数字的符号位填补最左边的n位，也就是如果该数是正数，则用0填补最左边的n位。如果该数是负数，则用1填补最左边的n位(补充知识点：一个有符号的数字，它的二进制最高位如果是1，则表明该数字为负数，如果是0则为正数)。如对有符号8位数字进行右移：00001010 >> 2 = 00000010
10001010 >> 3 = 11110001
整数的二进制中1的个数
题目：实现一个函数，输入一个整数，输出该数二进制表示中1的个数。如输入9，9的二进制表示是1001，有两个1，因此输入9该函数返回2.public int count (int n) {
int res = 0;
while (n!=0) {
n = n&(n-1);//该语句的作用是将二进制数中最右边的1变为0
res++;
}
return res;
}
只需要如下三行代码：a = a^b;
b = a^b;
a = a^b;
如果一个整数是2的整数次方，则它的二进制表示中应该只有一位是1，其它位都为0，如 2 的二进制表示为0010，4的二进制表示为0100。所以把这个整数减去1，再与自身作&运算（如求整数中1的个数的方法），这样该整数中唯一的一个1就变为0。public boolean isIntPower(int n) {
return (n&(n-1)) == 0;
}
两个整数m和n,计算需要改变m二进制表示中多少位，才可以得到n.
如4的二进制表示为0100,2的二进制表示为0010，4需要改变2位才可以变成2.分两步求解：第一步求两个整数的异或，第二步统计异或结果中1的个数。public int count (int m,int n) {
int a = m^n;
int res = 0;
while (a!=0) {
a = a&(a-1);//该语句的作用是将二进制数中最右边的1变为0
res++;
}
return res;
}
在其他数都出现偶数次的数组中找出出现奇数次的数
给定一个数组arr,其中只有一个数出现了奇数次，其他数都出现了偶数次，打印这个数。public void getOddTimesNumber(int[] arr) {
int eO = 0;
for (int cur : arr) {
eO = eO ^ cur;
}
System.out.println(eO+"");
}
学习算法的记录和整理，如有错误或意见请帮忙指出，以后会持续更新。。。。
参考书籍：
《程序员代码面试指南：IT名企算法与数据结构题目最优解》—左程云
《剑指Offer》 —何海涛