位运算的实际应用
流程信息
- 付款成功
- 出库
- 物流节点信息
是否签收
如果我们为每个节点设置值，那我们的流程必须要记住上一个节点的值
- 那我们该如何记住上一个节点
其实这时候选择位运算
付款成功出库物流节点是否签收如果付款成功 就用 1 否则 0如果出库成功 就用 1 否则 0如果每个地点的物流信息成功 就用 1 否则 0如果签收成功 就用 1 否则 0用 1111来表示全流程跑完使用或更新流程信息public updateStatus(nowStatus, comingStatus){nowStatus = newStatus| comingStatus;}例如1100 到 物流节点跑通 00101100 | 0010 结果 1110
位操作（Bit Manipulation）是程序设计中
对位模式或二进制数的一元和二元操作。
在许多古老的微处理器上，
位运算比加减运算略快，通常位运算比乘除法运算要快很多。
在现代架构中，情况并非如此：
位运算的运算速度通常与加法运算相同（仍然快于乘法运算）。
位操作包括：
¬¬ 取反（NOT）
∩∩ 按位或（OR）
⊕⊕ 按位异或（XOR）
∪∪ 按位与（AND）
移位
移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，
而空缺的部分填入一定的值。
移位又分为:
算术移位
逻辑移位
1 基本原理
- 0s 表示一串 0，1s 表示一串 1。
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
- 利用 x ^ 1s = ~x 的特点，可以将位级表示翻转；
利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。
一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。
- 一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。
1 位与运算技巧：
n&(n-1) 去除 n 的位级表示中最低的那一位。例如对于二进制表示 10110100，减去 1 得到 10110011，这两个数相与得到 10110000。
n&(-n) 得到 n 的位级表示中最低的那一位。-n 得到 n 的反码加 1，对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
- n-n&(~n+1) 去除 n 的位级表示中最高的那一位。
2 不用额外变量交换两个整数
a = a ^ b;
b = a ^ b;
a = a ^ b;
2
1 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
利用 x ^ x = 0 的特点，可以将数组中重复的两个数去除，只留下出现一次的数
利用 x ^ x = 0 的特点，可以将数组中重复的两个数去除，只留下出现一次的数
class Solution {
public int singleNumber(int[] nums) {
int len = nums.length;
if(len == 1) return nums[0];
int ans = nums[0];
for(int i = 1; i<len; i++){
ans ^=nums[i];
}
return ans;
}
}
2 找出数组中缺失的那个数
268. Missing Number (Easy)
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
Input: [3,0,1]
Output: 2
public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret = ret ^ i ^ nums[i];
}
return ret ^ nums.length;
}
3 位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 **00000000000000000000000000001011** 中，共有三位为 '1'。
- idea: n$(n-1) 消去低位的1， n为零为止。
class Solution{ public int hammingWeight(int n) { int sum = 0; while (n != 0) { sum++; n &= (n - 1); } return sum; } }
4 数字范围按位与
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0
class Solution {
public int rangeBitwiseAnd(int m, int n) {
while(n>m)
n = n&(n-1);
return n;
}
}
5 比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
class Solution {
public int[] countBits(int num) {
int[] arr = new int[num+1];
for(int i =0; i<=num; i++){
arr[i] = pop(i);
}
return arr;
}
private int pop(int x){
int count= 0;
while(x != 0){
count++;
x&=(x-1);
}
return count;
}
}
6 两整数之和
不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
无进位加法使用异或运算计算得出
进位结果使用与运算和移位运算计算得出
循环此过程，直到进位为 0
class Solution {
public int getSum(int a, int b) {
//进位
int jw = a & b;
//相加位
a = a ^ b;
while(jw != 0){
//左移进位作为新的b
b = jw << 1;
//进位
jw = a & b;
//相加位
a = a ^ b;
}
return a;
}
}
7 2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1
输出: true
解释: 2 = 1
示例 2:
输入: 16
输出: true
解释: 2 = 16
class Solution {
public boolean isPowerOfTwo(int n) {
if(n <= 0) return false;
return (n & (n-1)) == 0;
}
}
- 类型题， 3的幂， 4的幂等。
class Solution {
public boolean isPowerOfTwo(int n) {
if(n == 0) return false;
while(n%2==0){
n = n/2;
}
return n == 1;
}
}
若有收获，就点个赞吧
0 人点赞
