• 售前

  • 售后

热门帖子
入门百科

快速幂 + 位运算 --->倒霉用 * ÷ 号实现 乘除法运算

[复制链接]
云端午节 显示全部楼层 发表于 2022-1-15 23:27:11 |阅读模式 打印 上一主题 下一主题
小小知识点:盘算中值的尺度写法(防止了溢出)

  1. int mid = left + ((right - left) >> 1);
复制代码
快速幂的利用:

求 5^16(即求x的n次方):
通例解法:以初始值为1,一连乘n次x
弊端:当n非常大的时间就特殊耗时间


快速幂解法: 把n当作二进制(即把16当作10000,如许就从16次运算淘汰到5次运算)
运算过程:
1.以初始值res为1
2.判断n的二进制数最右位,1的话 res *= x;
判断代码:


  1. n & 1
复制代码
3.迭代x: x *= x; (二进制位数的界说8421所对应的值都不一样)
4. n >>= 1 (去除最右一位,即16的二进制10000>>1 为 1000)
长处:将时间大大的低落


标题:leetcode50
实现 pow(x, n) ,即盘算 x 的 n 次幂函数(即,xn )
  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         if(x == 0.0f) return 0.0d;
  4.         long b = n;
  5.         double res = 1.0;
  6.         if(b < 0) {
  7.             x = 1 / x;
  8.             b = -b;
  9.         }
  10.         while(b > 0) {
  11.             if((b & 1) == 1) res *= x;
  12.             x *= x;
  13.             b >>= 1;
  14.         }
  15.         return res;
  16.     }
  17. }
复制代码
快速幂的详细讲授:
leetcode的大佬讲授
迁徙:
不利用 * ÷ 号完成乘除法
例 5 x 16 (Y x Z)
通例解法: 以0为初始值,最大的数Z当 被加数, 最小的数Y当加的次数
即一连加5次16,当Y非常大的时间也是相当耗时
以是可以利用快速幂:把Y当作二进制数
流程:
1.效果res初始值0
2.Y & 1用来判断最右位是否为1,是的话res += Z, 不是就不做运算
3.迭代Z: Z = 1 去除最右位
5.当Y为0时竣事,不为0就重复 234步调的运算


标题:leetcode29
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不利用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的效果应当截去(truncate)其小数部门,比方:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
  1. class Solution {
  2.     public int divide(int dividend, int divisor) {
  3.         // 考虑被除数为最小值的情况
  4.         if (dividend == Integer.MIN_VALUE) {
  5.             if (divisor == 1) {
  6.                 return Integer.MIN_VALUE;
  7.             }
  8.             if (divisor == -1) {
  9.                 return Integer.MAX_VALUE;
  10.             }
  11.         }
  12.         // 考虑除数为最小值的情况
  13.         if (divisor == Integer.MIN_VALUE) {
  14.             return dividend == Integer.MIN_VALUE ? 1 : 0;
  15.         }
  16.         // 考虑被除数为 0 的情况
  17.         if (dividend == 0) {
  18.             return 0;
  19.         }
  20.         
  21.         // 一般情况,使用二分查找
  22.         // 将所有的正数取相反数,这样就只需要考虑一种情况
  23.         boolean rev = false;
  24.         if (dividend > 0) {
  25.             dividend = -dividend;
  26.             rev = !rev;
  27.         }
  28.         if (divisor > 0) {
  29.             divisor = -divisor;
  30.             rev = !rev;
  31.         }
  32.         
  33.         int left = 1, right = Integer.MAX_VALUE, ans = 0;
  34.         while (left <= right) {
  35.             // 注意溢出,并且不能使用除法
  36.             int mid = left + ((right - left) >> 1);
  37.             boolean check = quickAdd(divisor, mid, dividend);
  38.             if (check) {
  39.                 ans = mid;
  40.                 // 注意溢出
  41.                 if (mid == Integer.MAX_VALUE) {
  42.                     break;
  43.                 }
  44.                 left = mid + 1;
  45.             } else {
  46.                 right = mid - 1;
  47.             }
  48.         }
  49.         return rev ? -ans : ans;
  50.     }
  51.     // 快速乘
  52.     public boolean quickAdd(int y, int z, int x) {
  53.         // x 和 y 是负数,z 是正数
  54.         // 需要判断 z * y >= x 是否成立
  55.         int result = 0, add = y;
  56.         while (z != 0) {
  57.             if ((z & 1) != 0) {
  58.                 // 需要保证 result + add >= x
  59.                 if (result < x - add) {
  60.                     return false;
  61.                 }
  62.                 result += add;
  63.             }
  64.             if (z != 1) {
  65.                 // 需要保证 add + add >= x
  66.                 if (add < x - add) {
  67.                     return false;
  68.                 }
  69.                 add += add;
  70.             }
  71.             // 不能使用除法
  72.             z >>= 1;
  73.         }
  74.         return true;
  75.     }
  76. }
  77. 作者:LeetCode-Solution
  78. 链接:https://leetcode-cn.com/problems/divide-two-integers/solution/liang-shu-xiang-chu-by-leetcode-solution-5hic/
  79. 来源:力扣(LeetCode)
  80. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复制代码
官方二分法解答,自行观看,条记做着方便梳理


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作