java算法OJ（1）位运算
目录
1.前言
2.正文
2.1位运算符号
2.1俩数相除
2.1.1题目
2.1.2示例
2.1.3题解
2.2二进制求和
2.2.1题目
2.2.2示例
2.2.3题解
2.3只出现一次的数字
2.3.1题目
2.3.2示例
2.3.3题解
2.4只出现一次的数字（进阶版）
2.4.1题目
2.4.2示例
2.4.3 题解
2.6颠倒二进制位
3.小结
1.前言
今天来刷一点算法题，今天上手的是一些稍微基础的位运算练习题，关于位运算呢有许多类似于脑筋急转弯的逻辑思路，还是饶有趣味的，废话不多说，直接开始。
2.正文
2.1位运算符号
在算法题目开始之前，我们先基础盘点下位运算的各种操作。
按位与（AND）：
&
- 两个操作数的对应位都为1时，结果才为1。
- 例如：
5 & 3，二进制表示为101 & 011，结果是101，即5。
按位或（OR）：
|
- 两个操作数的对应位中至少有一个为1时，结果为1。
- 例如：
5 | 3，二进制表示为101 | 011，结果是111，即7。
按位异或（XOR）：
^
- 两个操作数的对应位相同则结果为0，不同则结果为1。
- 例如：
5 ^ 3，二进制表示为101 ^ 011，结果是110，即6。
按位非（NOT）：
~
- 反转操作数的每一位，将1变为0，0变为1。
- 例如：
~5，二进制表示为11111011（32位补码表示）。
左移（Left Shift）：
<<
- 将操作数的二进制表示向左移动指定的位数，右边空出的位补0。
- 例如：
5 << 1，二进制表示为101 << 1，结果是1010，即10。
右移（Right Shift）：
>>
- 将操作数的二进制表示向右移动指定的位数，左边空出的位补符号位（正数补0，负数补1）。
- 例如：
5 >> 1，二进制表示为101 >> 1，结果是5，即0。
2.2俩数相除
2.2.1题目
2.2.2示例
2.2.3题解
毕竟刚开始上手位运算算法，很多基本的技巧很不是很熟悉，这里借鉴了评论区一位大哥的思路，非常厉害。
我们先来思考，不通过加减乘除直接运算得到结果，而是通过位运算来解决这个问题，有什么思路呢？
我们可以先拿dividend除以2的31次方开始，此时被除出来的是非常小的数，一步一步向下逼近，直到出现一个n（即循环中的i），使得n>=divisor， 表示我们找到了一个足够大的数，这个数乘以divisor是不大于dividend的，所以我们就可以减去2^n个divisor，依此类推，直到余数小于除数。
下面罗列代码实现思路：
- 先处理特殊情况：
- 当除数或者被除数一个为0，则返回。
- 当被除数是范围内最小数且除数为-1，返回答案（该特殊处理的原因是按照以下算法会越界）。
- 通过用异或来计算是否符号相异。
- 接着for循环来实现核心思路，当找到n时，对ans以及被除数进行处理。
- 最后判断正负输出即可。
class Solution {
public int divide(int dividend, int divisor) {
if(divisor==0||dividend==0){
return 0;
}
//处理特殊情况，处理掉会溢出得情况
if(dividend==Integer.MIN_VALUE&&divisor==-1){
return Integer.MAX_VALUE;
}
boolean judge = (dividend^divisor)<0;//判断负数
long a = Math.abs((long)dividend);
long b = Math.abs((long)divisor);
int ans = 0;
for(int i = 31;i >= 0;i--){
if(a>>i>=b){
ans+=(1<<i);
a-=b<<i;
}
}
return judge ? -ans : ans;
}
}2.3二进制求和
2.3.1题目
2.3.2示例
2.3.3题解
这道题可以采用比较朴素的思路，将二进制数先转化为十进制数，相加后再转化为二进制数，但这样就没有利用位运算的思想。在正式讲解之前，先让我分享一个Java 中的一个类，
StringBuilder。
StringBuilder用于创建可变的字符序列。它提供了一个可变长度的字符序列，可以高效地添加、插入和删除字符。append 方法的使用append(int i): 将一个整数追加到StringBuilder对象的末尾。
接下来就是模拟二进制在做加法运算时的代码思路是：
创建一个
StringBuilder对象ans来存储结果。初始化一个变量
ca为0，用于存储进位。使用一个
for循环遍历两个字符串a和b，从它们的末尾开始逐位相加。循环条件是i >= 0 || j >= 0，确保至少有一个字符串还没有遍历完。在每次迭代中，计算当前位的和
sum，包括前一次迭代的进位ca，以及当前位的值（如果索引有效的话）。通过a.charAt(i) - '0'和b.charAt(j) - '0'将字符转换为整数。将
sum除以2得到新的进位值，并将sum对2取余得到当前位的结果，追加到ans中。在循环结束后，检查是否有剩余的进位（即
ca是否为1），如果有，则追加到ans中。最后，使用
ans.reverse().toString()将StringBuilder中的字符序列反转并转换为字符串，因为二进制加法是从最低位到最高位进行的，而字符串是从最高位到最低位存储的。
class Solution {
public String addBinary(String a, String b) {
StringBuilder ans = new StringBuilder();
int ca = 0;
for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
int sum = ca;
sum += i >= 0 ? a.charAt(i) - '0' : 0;
sum += j >= 0 ? b.charAt(j) - '0' : 0;
ans.append(sum % 2);
ca = sum / 2;
}
ans.append(ca == 1 ? ca : "");
return ans.reverse().toString();
}
}2.4只出现一次的数字
2.4.1题目
2.4.2示例
2.4.3题解
这道题如果抛开题目中对线性时间复杂度的要求，其实有许多实现思路，比如对出现过的数字都进行标记，哪个数字仅标记一次则为答案。但既然咱们是位运算主题，那咱们就来分享这道题利用位运算的神奇操作。
我们知道，当一个数a与0异或操作时，则返回a；当a与a异或操作时，则返回0。那么我们就有一个大胆的想法，将数组中所有的数字进行异或操作，但凡出现过俩次的数经过异或全部变为0，最终保留下来的数即为最终答案。当时我看完题解的时候，也被这个思路深深的震撼到了。接下来附上代码：
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for(int num:nums){
ans^=num;
}
return ans;
}
}还是再感叹一句，这思路绝了。
2.5只出现一次的数字（进阶版）
2.5.1题目
2.5.2示例
2.5.3 题解
这道题是上一道题的进阶版，我们也是按照位运算的思路进行解决问题。
核心思路是我们只需要累计计算各个数字每一位的加和，可以很轻松的出一个结论是，当末位之和取模3时如果正好为0，则仅出现一次的数的该二进制位置也为0；同理如果取模3为1，则仅出现一次的数的该二进制位置也为1.
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for(int i = 0;i<=31;i++){
int total = 0;
for(int num : nums){
total+=(num>>i)&1;
}
if(total%3!=0){
ans|=(1<<i);
}
}
return ans;
}
}2.6颠倒二进制位
2.6.1题目
2.6.2示例
2.6.3 题解
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int ans = 0;
for(int i = 0;i <= 31;i++){
int num = (n & 1);
ans |=num << ( 31 - i );
n>>>=1;
}
return ans;
}
}3.小结
今天的分享到这里就结束了哦，喜欢的小伙伴们点点赞点点关注，你的支持就是对我最大的鼓励！