文章目录
- Java位运算
- [剑指 Offer 65. 不用加减乘除做加法](https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/)（腾讯二面）
- 1.n&1(与运算)
- 2.位移操作
- [剑指 Offer 15. 二进制中1的个数](https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/)
- [剑指 Offer 16. 数值的整数次方](https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/)
- 3.朴素的贪心算法暴力求解（超时）
- 位运算基础
Java位运算
位运算比较抽象，面试中可能会出现简单的考察，比如位运算求两数之和。
剑指 Offer 65. 不用加减乘除做加法（腾讯二面）
这道题在腾讯二面中出现过。虽然很代码简单，但是位运算掌握不到位就会被挂。
class Solution {
public int add(int a, int b) {
while(b != 0) {
// 当进位为 0 时跳出
// c = 进位
&可以判断是否需要进位 （a&b）其中被置为1的位 需要进位 然后c进一位
int c = (a & b) << 1;
// a = 非进位和
a ^= b;
// b = 进位
b = c;
}
return a;
}
}
1.n&1(与运算)
n与1，&是与操作，可以判断 整数n的最右侧一位是不是为1；
计算机组成原理中的相关知识
运算规则如下：
1&1=1
1&0=0
0&0=0
[0000 1001] = 9;
package com.leetcode.demo;
public class TwoByteCul {
public static void main(String[] args) {
//0000 1001
int n = 9;
if((n&1)==1) {
System.out.println("0000 1001的二进制数最右位为1");
}
//0000 1000
int m = 8;
if((m&1)==1) {
System.out.println("m的二进制数最右位为1");
}else if((m&1)==0){//执行
System.out.println("m的二进制数最右位为0");
}
}
}
0000 1001的二进制数最右位为1
m的二进制数最右位为0
int temp = 1&1;
System.out.println("1&1="+temp);
temp = 1&0;
System.out.println("1&0="+temp);
temp = 0&0;
System.out.println("0&0="+temp);
1&1=1
1&0=0
0&0=0
2.位移操作
2.1右移运算符>>
删除二进制最后一位（向右移动一位）
//n = 9
//0000 1001 =9
//0000 0100 =4
temp = n>>1;//简写 n>>=1
System.out.println("n>>1="+temp);
结果为n>>1=4
2.2左移运算符<<
temp = n<<1;
//0000 1001 = 9
//0001 0010 = 18
System.out.println("n<<1="+temp);
n<<1=18
2.3无符号位右移
temp = n>>>1;
//0000 1001 = 9
//0000 0100 = 4
System.out.println("n>>>1="+temp);
temp = (0-n)>>>1;
//1000 1001 =-9
//0000 0100 =4
System.out.println("(0-n)>>>1="+temp);
n>>>1=4
(0-n)>>>1=2147483643
由运行结果可以看出负数的无符号位右移结果是不同的；这个知识点涉及计算机组成原理的反码和补码知识，不进行深入。
剑指 Offer 15. 二进制中1的个数
public class Solution {
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
if ((n & 1) == 1) {
count++;
}
n >>>= 1;
}
return count;
}
}
剑指 Offer 16. 数值的整数次方
实现Math.pow;就是求x的n次方
3.朴素的贪心算法暴力求解（超时）
class Solution {
public double myPow(double x, int n) {
double res = 1;
if(n==0){
return 1;
}else if(n>0){
for(int i = 1;i<=n;i++){
res = res*x;
}
}else if(n<0){
n = 0-n;
double ans=1;
for(int i = 1;i<=n;i++){
ans = (ans*x);
res =1/ans;
}
}
return res;
}
}
##4.快速幂思想
x^4 = x * x * x * x ; 正常的乘积需要四次运算。
x^4 = x^(2^2); 快速幂一次即可。
myPow(double x, int n)
这里n为幂
判断(b & 1) == 1 b的最后一位是不是1，如果是的话，res = res * x;
如果不是那么就不对结果运算，而是x = x *x;
b >>= 1; b进行右移位运算。这样的话如果是末位为0就跳过。达到减少运算的目的。
11 = 0000 1011
0000 1011 res=1 * x^(2 ^0) ； x = x * x = x ^ 2；
0000 0101 res= x ^1 * x ^ 2 = x ^ 3 ; x= x ^ 2 * x ^ 2 =x ^ 4;
0000 0010 末尾为0 不对res操作 x= x ^ 4 * x ^ 4 = x ^ 8;
0000 0001 res = x ^1 * x ^ 2 * x ^ 8
0000 0000 结束
x^11 = x ^(2^0) + x ^ (2^1) + x ^ (2 ^ 3 )
class Solution {
public double myPow(double x, int n) {
if(x == 0) return 0;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
}
位运算基础
一、复习
1）&, |
1&1=1
1&0=0
0&0=0
1|1=1
1|0=1
0|0=0
2）/ >> ,<<
1<<1=2;
1<<2=4;
1<<3=8;
2<<1=4;
2<<2=8;
3<<1=6;
异或运算^
1^1=0
1^0=1
0^0=0
371. 两整数之和
两数之和-位运算
class Solution {
/***
数学转化法 转化为乘除
1+0 =1
1+1 =0 等价于异或^ 相当于进位
1&1=1
1&0=0
0&0=0 &可以判断是否需要进位 （a&b）其中被置为1的位 需要进位
*/
public int getSum(int a, int b) {
while(b!=0){
//用carry记录需要进位的位置 carry = (a&b)
// carry<<1 进一位
int carry = (a&b) <<1;
/*
1^1=0
1^0=1
0^0=0
*/
a=a^b;
b=carry;
}
return a;
}
}
两数之和-数学方法解题
class Solution {
/***
数学转化法 转化为乘除
*/
public int getSum(int a, int b) {
double temp=Math.pow(2, a)*Math.pow(2, b);
double sum=Math.log(temp)/Math.log(2);
return (int)sum;
}
}
补一道贪心算法的练习
1877. 数组中最大数对和的最小值
输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。
class Solution {
public int minPairSum(int[] nums) {
Arrays.sort(nums);
int max = 0;
int len = nums.length;
for(int i = 0;i<len;i++){
int j = len - i-1;
max = Math.max(max,nums[i]+nums[j]);
}
return max;
}
}
和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。
```java
class Solution {
public int minPairSum(int[] nums) {
Arrays.sort(nums);
int max = 0;
int len = nums.length;
for(int i = 0;i<len;i++){
int j = len - i-1;
max = Math.max(max,nums[i]+nums[j]);
}
return max;
}
}