【数据结构与算法】位运算
位运算符
& ：与| ：或^ ：异或~ ：非（取反）>> << ：右移（补符号位），左移（补0）>>> ：右移（0补充高位）
对于int型，1<<35与1<<3是相同的，而左边的操作数是long型时需要对右侧操作数模64
异或：
可以理解为不进位加法：1+1=0，0+0=0，1+0=1
性质：
1、交换律：a ^ b = b ^ a
2、结合律：(a ^ b) ^ c = a ^ (b ^ c)
3、对于任何数x，都有x ^ x = 0，x ^ 0 = x
4、自反性：a ^ b ^ b = a ^ 0 = a，连续和同一个因子做异或运算，最终结果为自己
应用
判断奇偶数
x & 1 = 1 x是奇数x & 1 = 0 x是偶数
核心是判断二进制数最后一位是1还是0
交换两个整数变量的值
使用前提：a，b不相等
a = a^b;
b = a^b;
a = a^b;
不用判断语句求整数绝对值
(num^(num>>31))+(num>>>31)
11111111 11111111 11111111 11110111：num
11111111 11111111 11111111 11111111：num>>31
00000000 00000000 00000000 00001000：num^(num>>31)
00000000 00000000 00000000 00000001：num>>>31
00000000 00000000 00000000 00001001：num^(num>>31))+(num>>>31
正数显然满足
负数的相反数是原码含符号位取反加一
消除最低位的1
x&(x-1) ：可以使二进制数x的最低位的1变成0；
例题
找出唯一成对的数
1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来;不用辅助存储空间，能否设计一个算法实现?
核心：x^x=0
可以强行配凑消去其他元素：这1001个元素连续异或，再异或上1-1000这1000个数。
其他元素都出现2次，异或后变成0.而唯一的一个元素值出现3次，连续异或后值不变。
public static void main(String[] args) {
int []arr = new int[]{1,2,3,4,4,5};
int ans = 0;
for(int i=1;i<=5;i++){
ans^=i;
}
for(int i=0;i<6;i++){
ans^=arr[i];
}
System.out.println(ans);
}
找出落单的数
一个数组里除了某一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。
public static void main(String[] args) {
int []arr = new int[]{1,1,3,4,4};
int ans = 0;
for(int i=0;i<arr.length;i++){
ans^=arr[i];
}
System.out.println(ans);
}
二进制中1的个数
请实现一个函数，输入一个整数，输出该整数二进制表示中1的个数。
例：9的二进制表示为1001，有2位是1
法一：
该二进制数不断无符号右移并与1做与运算，结果为1则count++，直到该数变为0
public static void main(String[] args) {
int n=-1;
int count = 0;
while (n!=0){
int tmp = n&1;
if(tmp == 1) count++;
n = n >>> 1 ;
}
System.out.println(count);
} //32
法二：
每次使该二进制数的一个为1的二进制位变成0，count++，直到该数变成0；x&(x-1) ：可以使二进制数的最低位的1变成0；
public static void main(String[] args) {
int n=-1;
int count = 0;
while (n!=0){
n = n&(n-1);
count++;
}
System.out.println(count);
}
是不是2的整数次方
用一条语句判断一个整数是不是2的整数次方
也就是一个整数的二进制形式中为1的二进制位是不是只有一个。联系上一题，也就是count是不是为1
public static void main(String[] args) {
int n=65536;
System.out.println((n&(n-1))==0);
}
整数的二进制奇偶位交换
先取出偶数位和奇数位，偶数结果右移一位，奇数结果左移一位，最后异或
abababab abababab abababab abababab
a0a0a0a0 a0a0a0a0 a0a0a0a0 a0a0a0a0（ou）
0b0b0b0b 0b0b0b0b 0b0b0b0b 0b0b0b0b（ji）
0a0a0a0a 0a0a0a0a 0a0a0a0a 0a0a0a0a（ou>>>1）
b0b0b0b0 b0b0b0b0 b0b0b0b0 b0b0b0b0（ji<<1)
babababa babababa babababa babababa
public static void main(String[] args) {
int a = 0b01000000_00000000_00000000_00000000;
System.out.println(a);
int b = m(a);
System.out.println(b); //0b10000000_00000000_00000000_00000000
}
private static int m(int i) {
int ou = i & 0xaaaaaaaa;//和1010 1010 1010 。。。。做与运算取出偶数位
int ji = i & 0x55555555;//和0101 0101 0101 。。。。做与运算取出奇数位
return (ou >>> 1) ^ (ji << 1); // 连起来
}
0~1直接的浮点实数的二进制表示
给定一个介于0和1之间的实数，（如0.625)，类型为double,打印它的二进制表示(0.101，因为小数点后的二进制分别表示0.5,0.25.0.125……) 。
如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”
public static void main(String[] args) {
double num = 0.625;
StringBuilder sb = new StringBuilder("0.");
while (num > 0) {
//乘2：挪整
double r = num * 2;
//判断整数部分
if (r >= 1) {
sb.append("1");
//消掉整数部分
num = r - 1;
} else {
sb.append("0");
num = r;
}
if (sb.length() > 34) {
System.out.println("ERROR");
return;
}
}
System.out.println(sb.toString());
}
出现k次与出现1次
数组中只有一个数出现了1次，其他的数都出现了k次，请输出只出现了1次的数。
2个相同的2进制数做不进位加法，结果为0
10个相同的10进制数做不进位加法,结果为O
k个相同的k进制数做不进位加法，结果为0
public static void main(String[] args) {
int[] arr = {2, 2, 2, 9, 7, 7, 7, 3, 3, 3, 6, 6, 6, 0, 0, 0};
int len = arr.length;
char[][] kRadix = new char[len][];
int k = 3;
int maxLen = 0;
//转成k进制字符数组
//对于每个数字
for (int i = 0; i < len; i++) {
//求每个数字的k进制字符串并翻转，然后转为字符数组
kRadix[i] = new StringBuilder(Integer.toString(arr[i], k)).reverse().toString().toCharArray();
if (kRadix[i].length > maxLen)
maxLen = kRadix[i].length;
}
//不进位加法
int[] resArr = new int[maxLen];
for (int i = 0; i < len; i++) {
// 不进位加法
for (int j = 0; j < maxLen; j++) {
if (j >= kRadix[i].length)
resArr[j] += 0;
else
resArr[j] += (kRadix[i][j] - \'0\');
}
}
int res = 0;
for (int i = 0; i < maxLen; i++) {
res += (resArr[i] % k) * (int) (Math.pow(k, i));// 8%3=2,
}
System.out.println(res);
}